;; 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 list-intro-after) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #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: '() (cons 5 '()) (cons 1e9 (cons 5 '())) (cons -23 (cons 1e9 (cons 5 '()))) ; '() 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)))])) ; inventory with values: suppose that `a-lon` stands for ; (cons 5 (cons 4 (cons 3 '()))). ; So what is (first a-lon) in this case? _____ ; So what is (rest a-lon) in this case? ___________________ ; So what is (func-for-list (rest a-lon)) in this case? ; __[read answer from your test-cases]__ ; So what should my answer be in this case? __[read answer from your test-cases]__ ; 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__ <--- ; 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)))])) ; inventory with values: suppose that `a-lon` stands for ; (cons 99 (cons 2 (cons 4 '()))). ; So what is (first a-lon) in this case? __99__ ; So what is (rest a-lon) in this case? ___(cons 2 (cons 4 '())__ ; So what is (my-length (rest a-lon)) in this case? ; __2__ ; So what should my answer be in this case? __3__ ; contains? : list-of-number, number -> boolean ; Does `alon` contain `target`? ; (define (contains? a-lon target) (cond [(empty? a-lon) #false] [(cons? a-lon) (or (= target (first a-lon)) (contains? (rest a-lon) target))])) ; we first wrote an `if`, and then ; simplivied it to `or`. ; Inventory with values: ; if a-lon is (cons 93 (cons 2 (cons 4 '())) ; and target is 2: ; - what is (first a-lon) 93 ; - what is (rest a-lon) (cons 2 (cons 4 '()) ; - what is (contains? (rest a-lon) target) #true ; - what is our answer? #true #| In this case, our thinking *starts* with boolean and a number; we readily realize we can make this two booleans; then we can figure out our answer depends on those two bools: truth-table inputA inputB desired-answer #f #f | #f #f #t | #t #t #f | #t #t #t | #t |# (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) ; 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)))])) ; inventory with values: suppose that `a-lon` stands for ; (cons 93 (cons 2 (cons 4 '()))). ; So what is (first a-lon) in this case? __93___ ; So what is (rest a-lon) in this case? ___(cons 2 (cons 4 '())___ ; So what is (tee (rest a-lon)) in this case? ; __(cons 6 (cons 12 '())__ ; So what should my answer be in this case? __(cons 93 (cons 6 (cons 12 '()))__ #| we initially had a less-factored version, in the `cons?` branch: (if (even? (first a-lon)) (cons (* 3 (first a-lon)) (tee (rest a-lon))) (cons (first a-lon) (tee (rest a-lon)))) Noticing that the `cons` and its 2nd arg were repeated, we could factor them out (since the `cons` was in both branches, its presence shouldn't be inside the 'if'): (cons (if (even? (first a-lon)) (* 3 (first a-lon)) (first a-lon)) (tee (rest a-lon))) After that, we noticed that if think of the two branches as being `3*first` vs `1*first`, we can factor out the `...*first`: which is how we arrived at: (cons (* (if (even? (first a-lon)) 3 1) (first a-lon)) (tee (rest a-lon))) But the takeway is not any of that re-factoring: the takeaway is that the inventory-with-values leads us to realize that our answer will be 'cons', some number, and then the result-of-recursive-call. |# ;;; Reminder, of the data-def'n: ;;; ; list-of-number is: ; '(), or ; (cons number list-of-number) ; "constructed list"