2013年5月21日火曜日

lispでenqueueとdequeueを実装

lispでenqueuとdequeueを書こうと思ってはまってしまった。
なまってるな・・・

参考にしたのは竹内本。



下のような構造にすると効率がいいですね。
                              -------
                             | L |   |
                              -------
                                   ↓
 -------   -------   -------   -------
| H |   |→|   |   |→|   |   |→| T |   |
 -------   -------   -------   -------

※L : Length
  H : Head
  T : Tail


(defun  enqueue (new queue)
(cond ((cdr queue)
(rplacd (cdr queue) (cons new (cddr queue)))
(rplacd queue (cddr queue)))
(t (rplacd queue (cons new nil))
(rplacd (cdr queue) (cdr queue)) ))
(rplaca queue (1+ (car queue)))
new )
(defun dequeue (queue)
(cond
((cdr qqueue)
(prog1 (caddr queue)
(if (eq (cdr queue) (cddr queue))
(rplacd queue nil)
(rplacd (cdr queue) (cdddr queue)) )
(rplaca queue (1- (car queue))) ))
(t (error 'empty-queue queue)) ))


久しぶりに竹内本を読み返したのですが、はやりいい。
lispコードを書くことがなくても、lispの精神に触れられるように編纂された文章。

『道はnilを生ず。nilはアトムを生じ、アトムはS式を生じ、S式は万物を生ず』

久方ぶりに文法設計から離れた必要最小限のlispの純粋なココロに魅力を感じてしまった今日。



0 件のコメント:

コメントを投稿