#lang racket

; cons and rest let you push onto and pop off of the head of a list.
; these are constant time operations.

; suppose you want to push onto and pop off of the tail of a list
; what are the time and space requirements for this?

; get the element at the end of list L if L is non-empty
; this function uses constant stack space because rtop is
; in tail recursive position

(define rtop
  (lambda (L)
    (if (null? (rest L))
        (first L)
        (rtop (rest L))
        )
    )
  )
             
(rtop '(1 2 3 4))

; push an element e onto the end of list L
; this implementation causes the call stack to grow, why?
; because the result of the recursion is used in constructing
; the final return value.

(define rpush 
  (lambda (L e)
    (if (null? L) 
        (cons e '())
        (cons (first L) (rpush (rest L) e))
            )
        )
    )
  

(rpush '() '())
(rpush '(()) '())
(rpush '(1) '())
(rpush '(1 2 3 4) '())
(rpush '(1 2 3 4) '(5 6))
(rpush '(1 2 3 4) 5) 


                  
; pop an element e off the end of list L
; this implementation causes the call stack to grow, why?
(define rpop 
  (lambda (L)
    (if (null? (rest L)) 
        '()
        (cons (first L) (rpop (rest L)))
        )
    )
  )

(rpop '(1 2 3 4))

; observing that (rpop L) = (lreverse (rest (lreverse L)))
; and 
; that (rpush e L) = (lreverse (cons e (lreverse L)))
; gives a constant stack size algorithm

; are there tail recursive versions of rpush and rpop simular to lreverse?