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