(define l0 empty)
(define l1 (list 'a))
(define l2 (list 'a 'b))
(define l3 (list 'a 'b 'c))

;; reverse-noacc: list-of-[alpha] --> list-of-[alpha]   <a name="reverse-noacc"></a>
;;   (where [alpha] can stand for any type at all)
;; Return a list with the elements of data, but
;; in opposite order.
;;
(define (reverse-noacc data)
  (cond [(empty? data)  empty]
        [(cons?  data)  (add-at-end (first data)
                                    (reverse-noacc (rest data)))]))

;; add-at-end: [alpha], list-of-[alpha]  --> list-of-[alpha]
;; Return a list with all the elements of oldies, plus
;; newbie added as the last element.
;;
(define (add-at-end newbie oldies)
  (cond [(empty? oldies) (cons newbie empty)]
        [(cons?  oldies) (cons (first oldies) (add-at-end newbie (rest oldies)))]))

(add-at-end 'd l0)
(list 'd)

(add-at-end 'd l1)
(list 'a 'd)

(add-at-end 'd l2)
(list 'a 'b 'd)

(add-at-end 'd l3)
(list 'a 'b 'c 'd)


(reverse-noacc l0)
empty

(reverse-noacc l1)
(list 'a)

(reverse-noacc l2)
(list 'b 'a)

(reverse-noacc l3)
(list 'c 'b 'a)





;; reverse-acc: list-of-[alpha] --> list-of-[alpha]   <a name="reverse-acc"></a>
;;   (where [alpha] can stand for any type at all)
;; Return a list with the elements of data, but
;; in opposite order.
;;
(define (reverse-acc data) (reverse-help data empty))


;; reverse-help: list-of-[alpha], list-of-[alpha] --> list-of-[alpha]
;; Return the elements of data in reverse order, followed by
;; the elements of rev-so-far.
;; That is, we return (reverse data) appended to rev-so-far.
;; 
;;  Implementation note: taking the first item off data and
;;    putting at the front of rev-so-far is one step closer to solving
;;    the problem.  That is, for all othrs, rev-so-far, we have the identity:
;;        (reverse-help (cons 'x othrs) rev-so-far)
;;      = (reverse-help othrs (cons 'x rev-so-far))
;;  and the identity
;;        (reverse-help empty rev-so-far) = rev-so-far.
;;
(define (reverse-help data rev-so-far)
  (cond [(empty? data) rev-so-far]
        [(cons?  data) (reverse-help (rest data) (cons (first data) rev-so-far))]))
  

(reverse-help empty empty)
empty

(reverse-help empty (list 'x 'y 'z))
(list 'x 'y 'z)

(reverse-help (list 'a) (list 'x 'y 'z))
(list 'a 'x 'y 'z)

(reverse-help (list 'a 'b) (list 'x 'y 'z))
(list 'b 'a 'x 'y 'z)

(reverse-acc l0)
empty

(reverse-acc l1)
(list 'a)

(reverse-acc l2)
(list 'b 'a)

(reverse-acc l3)
(list 'c 'b 'a)







;;;;;;;;;;; Hand-evaluation ;;;;;;; <a name="hand-eval"></a>

  (reverse-acc l3)
  (reverse-acc (cons 'a (cons 'b (cons 'c empty))))
  (reverse-help (cons 'a (cons 'b (cons 'c empty))) empty)
  (reverse-help (cons 'b (cons 'c empty)) (cons 'a empty))
  (reverse-help (cons 'c empty) (cons 'b (cons 'a empty)))
  (reverse-help empty (cons 'c (cons 'b (cons 'a empty))))
  (cons 'c (cons 'b (cons 'a empty)))

;; It took approx. l+1 steps for a list of length l -- 
;; one call with each element of l being first.