;; The first three lines of this file were inserted by DrRacket. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(lib "htdp-beginner-reader.ss" "lang")((modname lect16-list-intro-sect01) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ()))) (require "let-for-bsl.rkt") #| Follow the design recipe (the final version!): ---- Per data type: 1. Choose data definition 2. Give some examples of the data 3. Template: a. If handling a union type, include a cond w/ one branch per option. b. If handling a product-type, pull out each piece (field). c. Add the natural recursive call (as appropriate) d. Inventory: In all cases, think about what *type* (each piece) is, and think of some functions that process that type. ---- Per function: 4. write test cases 5. (a-d): header, purpose, contract/type, copy the template, and stub it. 6. Inventory with values: Consider a particular test case, and think about what *specific* *value* of each sub-expression. 7. complete the body 8. run tests |# #| Definition: argument: the value passed into a function parameter: a function's local variable/identifier which is initialized from the arguments (each time the function is *called*). |# #| Today's+Tomorrow's outline: 1. Design recipe (recall, v.quickly). 2. data def'n for: list (including the non-built-in-way) 3. processing a list: sum write: length write: contains? (return a bool) write: triple-every-even (return a *list*) write: my-max (note bad run-time) learn: let* |# ; Data Definition: ; list-of-number is: ; '(), OR ; (make-cons [number] [list-of-number]) ; "constructed list" ; Examples of data: ; '() is the empty list; there is also the named-constant `empty`. ; cons is a built-in structure with two fields: first, rest ;(define-struct cons (first rest)) ; The constructor isn't *actually* `make-cons`, but instead just `cons`. ; The selectors aren't *actually* `cons-first`, but instead just `first` ; and not `cons-rest`, but instead just `rest`. ; ; There *is* a predicate `cons? : ANY -> boolean`. ; Also, there is a predicate to test for the empty-list: `empty? : ANY -> boolean` ;; template: ; func-for-list : list-of-num -> ??? ; (define (func-for-list a-lon) (cond [(empty? a-lon) ...] [(cons? a-lon) (... (first a-lon) ... (func-for-list (rest a-lon)))])) ; sum : list-of-num -> num (check-expect (sum '()) 0) (check-expect (sum (cons 3 '())) 3) (check-expect (sum (cons 4 (cons 3 '()))) 7) (check-expect (sum (cons 5 (cons 4 (cons 3 '())))) 12) ; sum : list-of-number -> number ; Return the sum of all the numbers in `a-lon`. ; (define (sum a-lon) (cond [(empty? a-lon) 0] [(cons? a-lon) (+ (first a-lon) (sum (rest a-lon)))])) ; inventory with values: suppose that `a-lon` stands for ; (cons 5 (cons 4 (cons 3 '()))). ; So what is (first a-lon) in this case? 5 <--- ; So what is (rest a-lon) in this case? ; (cons 4 (cons 3 '())) <--- ; So what is (sum (rest a-lon)) in this case? 7 <--- ; sub-question: what is (rest a-lon) in this case? (cons 2 (cons 4 '())) ; So what should my answer be in this case? 12 (check-expect (sum '()) 0) (check-expect (sum (cons 4 '())) 4) (check-expect (sum (cons 2 (cons 4 '()))) 6) (check-expect (sum (cons 3 (cons 2 (cons 4 '())))) 9) (check-expect (my-length '()) 0) (check-expect (my-length (cons 4 '())) 1) (check-expect (my-length (cons 2 (cons 4 '()))) 2) (check-expect (my-length (cons 99 (cons 2 (cons 4 '())))) 3) ; my-length : list-of-number -> natnum ; Return the length of `a-lon`. ; (define (my-length a-lon) (cond [(empty? a-lon) 0] [(cons? a-lon) (add1 (my-length (rest a-lon)))])) ; contains-93? : list-of-number -> boolean ; Return whether `a-lon` contains 93. ; (define (contains-93? a-lon) (cond [(empty? a-lon) #false] [(cons? a-lon) (or (= 93 (first a-lon)) (contains-93? (rest a-lon))) ])) (check-expect (contains-93? '()) #f) (check-expect (contains-93? (cons 93 '())) #true) (check-expect (contains-93? (cons 17 '())) #false) (check-expect (contains-93? (cons -3 (cons 93 '()))) #true) (check-expect (contains-93? (cons 93 (cons 17 '()))) #true) (check-expect (contains-93? (cons -3 (cons 17 '()))) #false) (check-expect (contains-93? (cons 93 (cons 93 '()))) #true) (check-expect (contains-93? (cons 93 (cons -3 (cons 17 '())))) #true) (check-expect (contains-93? (cons 17 (cons -3 (cons 93 '())))) #true) (check-expect (contains-93? '()) #f) (check-expect (contains-93? (cons 93 '())) #t) (check-expect (contains-93? (cons 7 '())) #f) (check-expect (contains-93? (cons 3 (cons 7 '()))) #f) (check-expect (contains-93? (cons 7 (cons 93 '()))) #t) (check-expect (contains-93? (cons 93 (cons 7 '()))) #t) (check-expect (contains-93? (cons 93 (cons 93 '()))) #t) (check-expect (contains-93? (cons 44 (cons 93 (cons 7 '())))) #t) (check-expect (contains-93? (cons 44 (cons 3 (cons 7 '())))) #f) (check-expect (contains-93? (cons 17 (cons 44 (cons 93 (cons 7 '()))))) #t) #| truth-table: inputA inputB desired-answer #f #f | #f #f #t | #t #t #f | #t #t #t | #t |# ; Functions *returning* a list: ; triple-every-even (and leave odd numbers untouched) ; (check-expect (tee '()) '()) (check-expect (tee (cons 4 '())) (cons 12 '())) (check-expect (tee (cons 7 '())) (cons 7 '())) (check-expect (tee (cons 2 (cons 4 '()))) (cons 6 (cons 12 '()))) (check-expect (tee (cons 93 (cons 2 (cons 4 '())))) (cons 93 (cons 6 (cons 12 '())))) ; tee : list-of-number -> list-of-number ; "triple-every-even" -- return another list like `a-lon`, ; but every even number is tripled (and odd numbers are unchanged). ; (define (tee a-lon) (cond [(empty? a-lon) '()] [(cons? a-lon) (cons (* (if (even? (first a-lon)) 3 1) (first a-lon)) #;(if (even? (first a-lon)) ; alternately, non-factored version. (* 3 (first a-lon)) (* 1 (first a-lon))) (tee (rest a-lon)))])) ; suppose a-lon were: (cons 7 (cons 9 (cons 2 '()))) ; then (first a-lon) would be: 7 ; and (rest a-lon) would be: (cons 9 (cons 2 '())) ; and (tee (rest a-lon)) would be: (cons 9 (cons 6 '())) ; and the answer I need to give back is: ; (cons 7 (cons 9 (cons 6 '())) ; suppose a-lon were: (cons 7 (cons 9 (cons 2 '()))) ; then (first a-lon) would be: 7 ; and (my-max (rest a-lon)) would be: 9 ; and the answer I need to give back is: 9 ;;;;;;;;;;;;;;; my-max ;(check-expect (my-max '()) -inf.0) (check-expect (my-max (cons 7 '())) 7) (check-expect (my-max (cons 7 (cons 7 '()))) 7) (check-expect (my-max (cons 4 (cons 7 '()))) 7) (check-expect (my-max (cons 4 (cons 7 '()))) 7) ;(check-expect (my-max '()) -inf.0) ; Um, this *claims* to fail (check-expect (my-max (cons -5 (cons -4 (cons -3 (cons -2 (cons -1 '())))))) -1) #;(define (func-for-list a-lon) (cond [(empty? a-lon) ...] [(cons? a-lon) (...(first a-lon) ... (func-for-list (rest a-lon)) ....)])) ; my-max : list-of-number -> number ; (define (my-max a-lon) -999) #| (define (my-max a-lon) (cond [(empty? a-lon) -inf.0] [(cons? a-lon) (max-of-two (first a-lon) (my-max (rest a-lon)))])) ; max-of-two : num, num -> num ; Return the larger of `a`, `b`. ; (define (max-of-two a b) (if (< a b) b a)) (check-expect (max-of-two 4 7) 7) (check-expect (max-of-two 7 4) 7) (check-expect (max-of-two 7 7) 7) (check-expect (max-of-two -2 -3) -2) |# ; This passes all our tests! ; However, this implementation does have a problem, ; only revealed under stress tests: ; #;(check-expect (my-max (cons -18 (cons -17 (cons -16 (cons -15 (cons -14 (cons -13 (cons -12 (cons -11 (cons -10 (cons -9 (cons -8 (cons -7 (cons -6 (cons -5 (cons -4 (cons -3 (cons -2 (cons -1 '()))))))))))))))))))) -1) #;(check-expect (my-max (cons -23 (cons -22 (cons -21 (cons -20 (cons -19 (cons -18 (cons -17 (cons -16 (cons -15 (cons -14 (cons -13 (cons -12 (cons -11 (cons -10 (cons -9 (cons -8 (cons -7 (cons -6 (cons -5 (cons -4 (cons -3 (cons -2 (cons -1 '())))))))))))))))))))))))) -1) #| ; The problem is the repeated computation: ; every time the result-of-recursive call is bigger than the first, ; we *re*calculate the recursive call. ; (Worst case is ascending list, where the recursive result is always bigger). ; Solution: use a variable, to remember the result of the recursive call: ; Use `let*` #;(define (my-max a-lon) (cond [(empty? a-lon) -inf.0] [(cons? a-lon) (let {[max-of-rest (my-max (rest a-lon))] } (if (< (first a-lon) max-of-rest) max-of-rest (first a-lon)))])) (my-max (cons 3 (cons 7 (cons 2 (cons 9 '()))))) ; `let*`: ; syntax: ; semantics: ; The Law of Scheme (and, Racket): ; An Expr is: ; ... ; (eval an-expr) is: ; cond ; ...lambda, so that 'define' meets the above ; ...'let' as 'lambda'. ; First: `let*`: use a variable(?) to avoid repeated computation. ; (Hey, could we do this with a helper function instead of `let*`?) ; (Does that trick ALWAYS work?) ; Some points: ; The +inf.0 trick doesn't work for (say) min-string. ; Really, the contract is wrong: should be non-empty-list. ; (To think about: what is Data def'n, for non-empty-list?) ; Later: We'll see a sol'n: a helper-function, w/ an accumulator: ; `max-helper : number, list-of-number -> number` ; - another data-def'n: natnum ; - ! ; - nums-up-to-zero ; Return a list of `i` numbers leading up to 0 (e.g. -3,-2,-1). ; (define (nums-below-0 i) (cond [(zero? i) '()] [(positive? i) (cons (- i) (nums-below-0 (sub1 i)))])) (check-expect (nums-below-0 2) (cons -2 (cons -1 '()))) (check-expect (nums-below-0 0) '()) (check-expect (nums-below-0 1) (cons -1 '())) ; `lambda` ; w/ an add'l argument: ; deltas; cumulate |#