;; PROBLEM
;; Given a non-empty list of numbers, find the biggest number in the list

;; A NELON is one of: 
;; - (cons Number empty)
;; - (cons Number NELON)

;; biggest : NELON -> Number
;; find the biggest number in nelon

;; #comparisons is exponential in size of input list
(define (biggest.slow nelon)
  (cond [(empty? (rest nelon)) (first nelon)]
        [else (if (> (first nelon) (biggest.slow (rest nelon)))
                  (first nelon)
                  (biggest.slow (rest nelon)))]))

;; #comparisons is linear in size of input list
(define (biggest.fast nelon)
  (cond [(empty? (rest nelon)) (first nelon)]
        [else 
         (local ((define b (biggest.fast (rest nelon))))
           (if (> (first nelon) b)
               (first nelon)
               b))]))

;; implementing biggest using foldr. 
;; Is this the same as biggest.slow or biggest.fast?
(define (biggest nelon)
  (foldr (lambda (n b) (if (> n b) n b))
         (first nelon) 
         (rest nelon)))




(check-expect (biggest '(1)) 1)
(check-expect (biggest '(10 40 13)) 40)
(check-expect 
   (biggest '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20))
   20)

(time (biggest '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23)))