;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-reader.ss" "lang")((modname rev) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
;; A LON is either empty or (cons Number LON). 

;; LON -> LON 
;; reverse the order of the numbers on the list 

; (check-expect (rev '(1 2 3)) '(3 2 1))

(define (rev l)
  (local (;; LON -> LON 
          (define (rev l)
            (cond
              [(empty? l) l]
              ;; (first l) = 1
              ;; (rest l) = '( 2 3)
              ;; (rev (rest l)) = '(3 2)
              ;; how to combine lines 1 and 3 to get the real result: '( 3 2 1 )
              [else (add-at-end (rev (rest l)) (first l))]))
          
          ;; LON Number -> LON  
          ;; add n to the end of l
          (define (add-at-end l n)
            (cond
              [(empty? l) (list n)]
              [else (cons (first l) (add-at-end (rest l) n))])))
    (rev l)))

#| stress tests  

(define (main n)
  (throw-away (time (rev (make-list n 0)))))
(define (throw-away x) 10)

(main 10)

; (main 100)

; (main 1000)

; (main 10000)

|#
;; ---------------
;; why is it slow? 
;; ---------------











;; step through, after commenting out check-expect (though that works, too)
(rev '(1 2 3))