data-structures - 这个简单的纯功能队列有效吗？

Question

我在 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 s t) 通过尾部的递归暂停将 t 附加到 s。

因此，每个入队都包含一层闭包，使其成为 O(1)，每次 peek 简单地检索一个值，使其成为 O(1)，并且每个出队检索并评估一个闭包，使其成为 O(1)。

我在别处没见过这个；例如，在 Okasaki 的 Purely Functional Data Structures 中，最简单的队列是 Banker's Queue，它比这复杂得多，并且只分摊了 O(1) 入队、窥视和出队。这让我怀疑我的推理有错误。

这个数据结构合理吗？有什么地方可以引用吗？

编辑:
delay-cons 在这里用于延迟追加是错误的；我正在尝试使用像宏这样的函数(感谢 Will Ness)。

我试图用

(define (delay-append s t)
  (if (null? s)
      t
      (cons (delay-car s) (lambda () (delay-append (delay-cdr s) t)))))

但这不适用于 API。

Answer 1

一、delay-cons不能是函数。它必须是一个宏。 For instance ,

(define-syntax s-cons
  (syntax-rules ()
    ((s-cons h t) (cons h (lambda () t))))) 

在麻省理工学院工作。

但是你可以通过不使用 delay-cons 来解决这个问题。在您的 delay-append :

(define (delay-append s t)
  (if (null? s)
      t
      (cons (delay-car s) (lambda () (delay-append (delay-cdr s) t)))))

所以没关系。

至于复杂性，delay-append并非没有代价。它环绕原始队列。想象一下它有 30 个元素；然后你一个接一个地追加 10 个。现在原来是用10层delay-append包裹起来的，必须导航以获取这 30 个元素中的每一个(实际上是 29 个，因为头部被拉到直接 car 中，由 delay-append )。所以对于 n -附加，n -访问使用模式，它看起来像一个二次复杂性。

这个问题在 Haskell 上下文中的经典论文是“Why are difference lists more efficient than regular concatenation?”。您的 delay-append类似于那里的“常规串联”:

[]  ++ t = t
s   ++ t = (head s) : ((tail s) ++ t)

这是一个插图:

(define (wrap x) (cons x (lambda () () ))) 
(define (decdr s) ((cdr s))) 
(define (app s t) (if (null? s) t
                   (cons (car s) (lambda () (app (decdr s) t)))))

;; RIGHT NESTING
(app (wrap 1) (app (wrap 2) (app (wrap 3) (wrap 4))))  == 

(app #A=#[1 . (\->())] 
     (app #B=#[2 . (\->())] 
          (app #C=#[3 . (\->())] #D=#[4 . (\->())] )))  ==

(app #A# (app #B# 
              #E=#[3 . (\-> (app (decdr #C#) #D#)  )]  ))  ==

(app #A# #F=#[2 . (\-> (app (decdr #B#) #E#))] )  ==

#G=#[1 . (\-> (app (decdr #A#) #F#))]     ;; the return value

;; NOW, (car #G#) is O(1), but what about (decdr #G#)?

(decdr #G#) == (app (decdr #A#) #F#) 
            == (app () #F#) 
            == #F#   ;;  O(1) steps as well

;; LEFT NESTING 

(app (app (app (wrap 1) (wrap 2)) (wrap 3)) (wrap 4))  ==

(app (app (app #D=#[1 . (\->())] #C=#[2 . (\->())] ) 
          #B=#[3 . (\->())] ) 
     #A=#[4 . (\->())] )  == 

(app (app #E=#[1 . (\-> (app (decdr #D#) #C#))] #B#) #A#) == 

(app #F=#[1 . (\-> (app (decdr #E#) #B#))] #A#) == 

#G=#[1 . (\-> (app (decdr #F#) #A#))]       ;; the return value

;; NOW, (car #G#) is O(1), but what about (decdr #G#)?

(decdr #G#) == (app (decdr #F#) #A#) 
            == (app (app (decdr #E#) #B#) #A#)
            == (app (app (app (decdr #D#) #C#) #B#) #A#) 
            == ...   ;; O(N) steps, re-creating the left-nesting structure