Lecture 27

;; N is one of:
;; -- 0 
;; -- (add1 N)
;; the predicates are: zero?, positive?; the selector is sub1 

;; This is a strange data def. Make examples. 
0 = 0 
(add1 0) = 1 
(add1 (add1 0)) = 2 
(add1 (add1 (add1 0))) = 3 


;; Historical footnote from philosophy: 
;; Natural numbers are abbreviations for these things. 



;; An AList is [Listof 'a] ;; This uses new notation. Make examples. empty (cons 'a empty) (cons 'a (cons 'a empty))
;; Problem 1: design a function that consumes an N (x) ;; and creates an AList of length x. ;; N -> AList (define (copy x) (cond [(zero? x) empty] [else (cons 'a (copy (- x 1)))])) ;; Use the template Luke! (equal? (copy 3) (list 'a 'a 'a))
;; Problem 2: design a function that consumes an N (x) and creates ;; all ALists. ;; N -> [Listof AList] (define (many x) (cond [(zero? x) (list empty)] [else (cons (copy x) (many (sub1 x)))])) (equal? (many 0) (list empty)) (equal? (many 1) (list (list 'a) empty)) (equal? (many 2) (list (list 'a 'a) (list 'a) empty))
;; Problem 3: now abstract over the two functions. Careful, this ;; isn't quite like the usual abstraction stuff. ;; step 1: circle the differences and pair them up ;; step 2: introduce new parameters (use many as template) (define (abstract x base make-an-item) (cond [(zero? x) base] [else (cons (make-an-item x) (abstract (sub1 x) base make-an-item))])) ;; step 3: re-define the old functions: (define (many.v2 x) (abstract x (list empty) copy.v2)) (define (copy.v2 x) (abstract x empty add-an-a)) (define (add-an-a n l) 'a) ;; step 4: rerun the tests from before: (equal? (many.v2 0) (list empty)) (equal? (many.v2 1) (list (list 'a) empty)) (equal? (many.v2 2) (list (list 'a 'a) (list 'a) empty)) (equal? (copy.v2 3) '(a a a))