LispとQueue

Queue構造

EventStreamを作るにあたってキュー構造は使うので、
SchemeのListでQueueを作ってみます。

Consセルの構造では先頭への要素の追加削除は楽なので、
スタック構造はすぐに考え付きます。

Queueの場合、リスト末尾への操作が必要になるため、
直接proper-listに対して操作すると効率が悪いのですが、
リストの末尾を記録することで効率化できます。

Queueをproper-listの先頭セルと末尾セルのpairであると定義します。
例外的に、NILのpairを空のキューと定義します。

(use srfi-1)

(define (qnull? q)
  (and (null? (car q)) (null? (cdr q))))

(define (qsingle? q)
  (eq? (car q) (cdr q)))

(define (queue? obj)
  (and (pair? obj)
       (or (qnull? obj)
           (eq? (last-pair (car obj)) (cdr obj)))))

キューに対する参照はcar,cdrの組み合わせでできます。

(define qlist car)
(define qfront caar)
(define qlast cadr)

キューへのpushは末尾セルに対して新しいリストを連結させることで実現します。
あわせてキューが記録しているリストの末尾セルも更新します。

(define (qpush-list! l q)
  (cond
    ((qnull? q)
      (set-car! q l)
      (set-cdr! q (last-pair l)))
    (else
      (set-cdr (cdr q) l)
      (set-cdr q (last-pair l)))))

(define (qpush! x q)
  (qpush-list! (list x) q))

キューのpopは先頭セルを一つ取り除くことで実現します。
例外的に要素一つのキューの場合、リスト末尾への参照も取り除く必要があります。

(define (qpop! q)
  (cond
    ((qnull? q)
      (error "pop from null-queue"))
    ((qsingle? q)
      (set-car! q '())
      (set-cdr! q '()))
    (else
      (set-car! q (cdar q)))))

実用

Chicken Scheme にはQueue構造がサポートされているので、
そちらを利用することをお勧めします。

http://wiki.call-cc.org/man/4/Unit%20data-structures#queues

常用されている基本データ構造は、
処理系がサポートしているものを利用することがベターです。

世の中の様々なデータ構造をConsセルのみで実現しようとすることは、
Cons脳の体操になるので、Lisp勘が衰えた時に再びやってみようかと思います。

ただ、レジスタ計算機を実装するときはVector構造が欲しくなりますね。