;; 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-11) (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: ; '() ("empty" or "the empty list"), OR ; (cons [number] [list-of-number]) ; "constructed list" ; Examples of data: '() (cons 3 '()) (cons 4 (cons 3 '())) (cons 5 (cons 4 (cons 3 '()))) ; '() 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) ; <-- this is a number ... (func-for-list (rest a-lon)))])) ; sum : list-of-num -> num ; return the sum of all the numbers inside a list. (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 (= (first a-lon) 93) (contains-93? (rest a-lon)))] #;[(cons? a-lon) (cond [(contains-93? (rest a-lon)) #true] [(= (first a-lon) 93) #true] [else #false])])) ; inventory-with-values: ; what if `a-lon` were: (cons 55 (cons 44 (cons 93 (cons 7 '())))) ; (check-expect (contains-93? '()) #f) (check-expect (contains-93? (cons 93 '())) #t) (check-expect (contains-93? (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 3 (cons 7 '()))) #f) (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 55 (cons 44 (cons 93 (cons 7 '()))))) #t) #| truth-table: first 2nd desired-answer input input #f #f | #f #f #t | #t #t #f | #t #t #t | #t |# #| ; contains? : list-of-number, number -> boolean ; Does `alon` contain `target`? ; #;(define (contains? a-lon target) #false) ; Alternately: we can simplify `(if true )` ; to `(or )` (check-expect (contains? '() 4) false) (check-expect (contains? (cons 4 '()) 4) true) (check-expect (contains? (cons 4 '()) 99) false) (check-expect (contains? (cons 2 (cons 4 '())) 99) false) (check-expect (contains? (cons 2 (cons 4 '())) 2) true) (check-expect (contains? (cons 2 (cons 4 '())) 4) true) (check-expect (contains? (cons 93 (cons 2 (cons 4 '()))) 93) true) (check-expect (contains? (cons 93 (cons 2 (cons 4 '()))) 4) true) (check-expect (contains? (cons 93 (cons 2 (cons 4 '()))) 77) false) (check-expect (contains? (cons 93 (cons 2 (cons 93 '()))) 93) true) ; contains? : list-of-number, number -> boolean ; Does `alon` contain `target`? ; (define (contains? a-lon target) #false) #| Quiz: - give a list containing 17, -4, 2 (in that order) - write a function which takes in a list-of-number, and (mumblemumble...) |# |# ; 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)) (tee (rest a-lon)))] #;[(cons? a-lon) (cons (if (even? (first a-lon)) (* 3 (first a-lon)) (first a-lon)) (tee (rest a-lon)))])) ; I'm thinking of: a-lon is (cons 93 (cons 2 (cons 4 '())) ;;; Reminder, of the data-def'n: ;;; ; list-of-number is: ; '(), or ; (cons number list-of-number) ; "constructed list" ; 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) ; Double.NEGATIVE_INFINITY (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 7 (cons 4 '()))) 7) (check-expect (my-max (cons 2 (cons 7 (cons 4 '())))) 7) (check-expect (my-max (cons 9 (cons 7 (cons 4 '())))) 9) (define l74 (cons 7 (cons 4 '()))) (check-expect (my-max l74) 7) (check-expect (my-max (cons 2 l74)) 7) (check-expect (my-max (cons 9 l74)) 9) ;(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) (cond [(empty? a-lon) -inf.0] [(cons? a-lon) (if (> (first a-lon) (my-max (rest a-lon))) (first a-lon) (my-max (rest a-lon)))])) (define (my-max a-lon) (cond [(empty? a-lon) -inf.0] [(cons? a-lon) (let* {[max-o-the-rest (my-max (rest a-lon))] [ ..some-id.. ..some-expr..] [ ..some-id.. ..some-expr..] } (if (> (first a-lon) max-o-the-rest) (first a-lon) max-o-the-rest))])) ; syntax for `let*`: (use angle-brackets for non-terminals) -> (let* {} ) -> ε | -> [ ] ; semantics for `let*`: ; for each identifier (in order), evaluate it's right-hand-side expression, ; and bind that identifier to the result. ; Then, evaluate the body-expression (using the new identifiers), ; and its result is the result of the entire `let*` expression. ; suppose, for some list 'blah', `(my-max blah)` takes 0.1s to complete, and ; returns 100. ; How long does it take for `(my-max (cons 50 blah))` to run? 0.2s ; How long does it take for `(my-max (cons 45 (cons 50 blah)))` to run? 0.4s ; Each we add a (small) item to the front, the running-time doubles. #| (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 '()))))) ; 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 |#