delayed complexity -- http://stackoverflow.com/questions/17417110/is-this-simiple-purely-functional-queue-valid

decdr.scm

(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)))))
---------------------------------------------------------------------------

;; test:  (app (wrap 1) (app (wrap 2) (app (wrap 3) (wrap 4))))        -- 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
---------------------------------------------------------------------------

;; test:  (app (app (app (wrap 1) (wrap 2)) (wrap 3)) (wrap 4))        -- 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
            == ...