PAIP: queue

このブログでは毎月、月の日数より多く記事を書くことを軽く目標にしてきましたが、ここ2ヶ月停滞気味です。
で、気づけば次の記事で365 記事目ということで、年単位で見れば目標達成ですかね。去年は2ヶ月間まったく書かないことがあったので、320 記事でした。

PAIP も購入してから継続的に読んできて、1～11・22～25・17～18章と読みましたが、これも現在停滞気味。7～8割くらいは読んだことになりますが、例題や演習はほとんど書いてないので、むしろ「これから」といったところです。

で、結構いまさらですが、10章の queue の実装がおもしろかったので、gauche で書いてみました。cons の cdr 部に queue 本体を、car 部に queue の末尾の cons のポインタを突っ込んだ形です。この car と cdr を逆にした tconc も紹介されていますが割愛。

P.322 ～

(define (queue-contents q)
  (cdr q))

(define (make-queue)
  (rlet1 q (cons '() '())
         (set! (car q) q)))

(define (enqueue item q)
  (set! (car q)
        (rlet1 f (cons item '())
               (set! (cdr (car q)) f)))
  q)

(define (dequeue q)
  (pop! (cdr q))
  (when (null? (cdr q))
    (set! (car q) q))
  q)

(define (front q)
  (car (queue-contents q)))

(define (empty-queue? q)
  (null? (queue-contents q)))

(define (queue-append! q ls)
  (set! (cdr (car q)) ls)
  (set! (car q)
        (last-pair q))
  q)



(define q (make-queue))

(queue-contents q)
;; ()

(empty-queue? q)
;; #t

(enqueue 'a q)
;; (#0=(a) . #0#)
(enqueue 'b q)
;; (#0=(b) a . #0#)
(enqueue 'c q)
;; (#0=(c) a b . #0#)

(empty-queue? q)
;; #f

(front q)
;; a

(queue-contents q)
;; (a b c)

(queue-append! q '(d e f))
;; (#0=(f) a b c d e . #0#)

(dequeue q)
;; (#0=(f) b c d e . #0#)
(dequeue q)
;; (#0=(f) c d e . #0#)
(dequeue q)
;; (#0=(f) d e . #0#)

追記

• vallog: consでqueue