我在 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。
因此,每个入队都包装了一层闭包,使其成为 O(1),每个 peek 只需检索一个使其成为 O(1) 的值,每个出队检索并评估一个闭包,使其成为 O(1)。
我在其他地方没见过这个;例如,在 Okasaki 的 Purely Functional Data Structures 中,最简单的队列是银行家队列,它比这复杂得多,并且只有分期 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。