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.

Maybe you should come up with assertions, tests and examples to check what you've done. Especially it is not clear what kind of 'delay' this provides and what 'delay-cons' actually does - given that Scheme does *strict* evaluation. — Rainer Joswig, Jul 02 '13 at 10:03
Thanks Will, it did; I was trying to compensate for getting delay-cons wrong (I was trying to use a function like a macro) - enqueue is O(N) as written. — Edward Ross, Jul 02 '13 at 14:43
nope. broke it again. `delay-cons` does not delay anything, as it is a function so calculates its arguments before eval'ing its body. your new `delay-append` is just plain simple `append`. — Will Ness, Jul 02 '13 at 14:44
the original definition works: `(define x (delay-append (delay-cons 1 ()) (delay-cons 2 ()))) => ;Value: x` -- `(delay-car x) => ;Value: 1` -- `(delay-car (delay-cdr x)) => ;Value: 2` -- `(delay-cdr (delay-cdr x)) => ;Value: ()` — Will Ness, Jul 02 '13 at 14:53

score 5 · Accepted Answer · edited May 23 '17 at 11:48

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

Ok, I sort of get it: Each enqueue takes a constant number of operations, but a dequeue must unwrap a whole layer of appends to push the next number embedded at the bottom of the closures, then rewrap it, so it's O(N). — Edward Ross, Jul 03 '13 at 04:34
@EdwardRoss cf. tangentially related http://ideone.com/Si5axU. It's pure functional O(1) queue (in simple Haskell), but it *pulls* its new elements itself instead of letting you push them onto it. — Will Ness, Jul 21 '13 at 09:18

Is this simiple purely functional queue valid?

1 Answers1