Is this simiple purely functional queue valid?

Question

I have developed a purely functional queue in Lisp (Scheme) as follows:

;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 is similar to cons, but it suspends the evaluation of the tail by wrapping it in a closure. delay-append similarly (delay-append s t) appends t to s by recursive suspensions of the tail.

Consequently each enqueue wraps one layer of closure, making it O(1), each peek simply retrieves a value making it O(1), and each dequeue retrieves and evaluated one closure making it O(1).

I haven't seen this elsewhere; for example in Okasaki's Purely Functional Data Structures the simplest queue is a Banker's Queue which is significantly more complicated than this, and only has amortized O(1) enqueue, peek and dequeue. Which makes me suspicious that there's an error in my reasoning.

Is this data structure sound? Is there a reference for it somewhere?

Edit: delay-cons is the wrong thing to use in delay-append here; I'm trying to use a function like a macro (thanks Will Ness).

I tried to correct it using

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

but this doesn't work with the API.

Answer 1

First, delay-cons can not be a function. It must be a macro. For instance,

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

works in MIT Scheme.

But you get around this by not using delay-cons in your delay-append:

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

So it's OK.

As for complexities, delay-append is not without cost. It wraps around the original queue. Imagine it had 30 elements; then you append 10 more, one by one. Now the original is wrapped in 10 layers of delay-append, which must be navigated to get at each of those 30 elements (29 actually, as the head is pulled out into the immediate car, by the delay-append). So for n-appended, n-accessed use pattern, it looks like a quadratic complexity.

The classic treatise of this problem in Haskell context is "Why are difference lists more efficient than regular concatenation?". Your delay-append is similar to "regular concatenation" there:

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

---

Here's an illustration:

(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