次のように、Lisp (Scheme) で純粋に機能的なキューを開発しました。
;Internal functions
(define (delay-cons x s)
(cons x (lambda () s)))
(define (delay-car s)
(car s))
(define (delay-cdr s)
((cdr s)))
(define (delay-append s t)
(if (null? s)
t
(delay-cons (delay-car s) (delay-append (delay-cdr s) t))))
;API
(define (enqueue x q) (delay-append q (delay-cons x empty)))
(define dequeue delay-cdr)
(define peek delay-car)
(define empty '())
(define empty? null?)
delay-cons は cons に似ていますが、末尾をクロージャでラップすることにより、末尾の評価を一時停止します。同様に、delay-append (delay-append st) は、t を末尾の再帰的な中断によって s に追加します。
したがって、各エンキューはクロージャの 1 つのレイヤーをラップして O(1) にし、各ピークは単純に値を取得して O(1) にし、各デキューは 1 つのクロージャを取得して評価し、O(1) にします。
これは他では見たことがありません。たとえば、Okasaki の Purely Functional Data Structures では、最も単純なキューは Banker's Queue であり、これはこれよりもはるかに複雑で、O(1) のエンキュー、ピーク、およびデキューのみを償却しています。これは、私の推論に誤りがあるのではないかと疑っています。
このデータ構造は健全ですか？どこかにそれに対する参照はありますか？
編集: delay-cons は、ここで delay-append で使用するのは間違っています。マクロのような関数を使用しようとしています (Will Ness に感謝します)。
を使って修正してみました
(define (delay-append s t)
(if (null? s)
t
(cons (delay-car s) (lambda () (delay-append (delay-cdr s) t)))))
しかし、これは API では機能しません。