;; CS U213 Spring 2007 ;; Lecture 1: January 8, 2007 ;; Question ;; --------- ;; Given a list of Number find the maximum number in the list. ;; We go about this following the Design Recipe ;; Data Definition: ;; ---------------- ;; A [Listof Number] is one of ;; ;; -- empty ;; --(cons Number [Listof Number]) ;; Contract, Purpose Statement and Header: ;; --------------------------------------- ;; max-lon: [Listof Number] -> Number (or False) ;; find the maximum number in the input list ;; (define (max-lon lon) ...) ;; Examples: ;; --------- ;; Input Output ;; ----- ------ ;; (list 1 2 3 4) 4 ;; empty false ;; (list 365 1 2) 365 ;; (list 8) 8 ;; (list 5 5) 5 ;; Template: ;; --------- ;; (define (max-lon lon) ;; (cond ;; [(empty? lon) ...] ;; [(cons? lon) ... (first lon) ... ;; Number ;; ... (rest lon) ... ;; [Listof Number] ;; ... (max-lon (rest lon)) ... ])) ;; Number (or False) ;; Function Body: ;; -------------- ;; max-lon: [Listof Number] -> Number (or False) ;; find the maximum number in the input list (define (max-lon lon) (cond [(empty? lon) false] [(cons? lon) (max-acc 0 lon)])) ;; need helper function here! ;; Tests: ;; ------ (= (max-lon (list 1 2 3 4)) 4) (equal? (max-lon empty) false) (= (max-lon (list 365 1 2)) 365) (= (max-lon (list 8)) 8) ;; NOTE: If you are to run this file in DrScheme, move the ;; definition of max-acc before the definition of ;; max-lon. Otherwise you will get an error. ;; Contract, Purpose Statement and Header: ;; --------------------------------------- ;; max-acc Number [Listof Number] -> Number ;; find the maximum of the given number and the list of numbers ;; (define (max-acc curr-max lon) ...) ;; Examples: ;; --------- ;; Input Output ;; ----- ------ ;; 1 (list 2 3 4) 4 ;; 3 empty 3 ;; 365 (list 1 2) 365 ;; 4 (list 5 5) 5 ;; Template: ;; --------- ;; (define (max-acc curr-max lon) ;; (cond ;; [(empty? lon) curr-max] ;; [(cons? lon) ... (first lon) ... ;; ... (rest lon) ... ;; ... (max-acc ... curr-max ...(rest lon)) ... ])) ;; curr-max holds the maximum number we have seen so far in the list ;; Function Body: ;; -------------- ;; max-acc: Number [Listof Number] -> Number ;; find the maximum of the given number and the list of numbers (define (max-acc curr-max lon) (cond [(empty? lon) curr-max] [(cons? lon) (max-acc (max curr-max (first lon)) (rest lon))])) ;; Tests ;; ----- (= (max-acc 1 (list 2 3 4)) 4) (= (max-acc 3 empty) 3) (= (max-acc 365 (list 1 2)) 365) (= (max-acc 4 (list 5 5)) 5)