;; 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-intermediate-reader.ss" "lang")((modname lect14-list-intro) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
#| Follow the design recipe (the practically-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*).
|#


#| Definition (informal): the *signature* for a function is:
 the function's name, it's return-type, and the type of all parameters
 (and the order they appear in).

 Gist: it's the info needed (a) for a user to properly *call* the function, and
 (b) for the compiler/type-checker/interpreter to verify the syntax (and types)
 of a function-call.

 (I'll sometimes accidentally say that parameter-names are part of the signature,
 but that's not technically true;
 it just aligns with the first line of a
 function-declaration in many Algol-like syntaxes (e.g. Java),
 which I'll call the function header.)

 This definition doesn't address overloading, type-hierarchies, auto-conversion,
 keyword-arguments, var-args, dynamically-typed languages, class- vs instance-methods
 ... but the gist is good enough for our purposes.
 (And what about scope, visibility modifiers, and namespaces?
  I suspect those are *not* typically included in peoples' definitions of 'signature';
  the reason is that in language-implementation, determining scope is usually
  done in a different step from verifying a function-call.)
 |#



#|  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
;      (cons number list-of-number)   ; "constructed list"




; Examples of data:
empty                        ; ()
(cons 4 empty)               ; (4)
(cons 2 (cons 4 empty))      ; (2 4)
(cons 3 (cons 2 (cons 4 empty)))   ;(3 2 4)


; empty is a built-in constant
; 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?`.




;; template:
; fun-for-list : list-of-number -> ???
;
(define (fun-for-list a-lon)
    (cond [(empty? a-lon) ...]
          [(cons? a-lon)  (... (first a-lon)
                           ... (fun-for-list (rest a-lon)) ...)]))


; sum: list-of-number -> number
;
(check-expect (sum empty) 0)
(check-expect (sum (cons 4 empty)) 4)
(check-expect (sum (cons 7 (cons 4 empty))) 11)
(check-expect (sum (cons 3 (cons 7 (cons 4 empty))))
              14)


; 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)))]))

(check-expect (my-length empty) 0)
(check-expect (my-length (cons 4 empty)) 1)
(check-expect (my-length (cons 2 (cons 4 empty))) 2)
(check-expect (my-length (cons 93 (cons 2 (cons 4 empty))))
              3)

(define (my-length a-lon)
  (cond [(empty? a-lon) 0]
        [(cons? a-lon)  (add1 (my-length (rest a-lon)))]))




; contains? : list-of-number, number -> boolean
; Does `alon` contain `target`?
;
#;(define (contains? a-lon target)
    false)
; Alternately: we can simplify `(if <cond> true <boolexpr>)`
;                           to `(or <cond> <boolexpr>)`






(check-expect (contains? empty 4) false)

(check-expect (contains? (cons 4 empty) 4) true)
(check-expect (contains? (cons 4 empty) 99) false)

(check-expect (contains? (cons 2 (cons 4 empty)) 99) false)
(check-expect (contains? (cons 2 (cons 4 empty)) 2) true)
(check-expect (contains? (cons 2 (cons 4 empty)) 4) true)

(check-expect (contains? (cons 93 (cons 2 (cons 4 empty))) 93)
              true)
(check-expect (contains? (cons 93 (cons 2 (cons 4 empty))) 4)
              true)
(check-expect (contains? (cons 93 (cons 2 (cons 4 empty))) 77)
              false)
(check-expect (contains? (cons 93 (cons 2 (cons 93 empty))) 93)
              true)

; co
(define (contains? a-lon target)
    (cond [(empty? a-lon) false]
          [(cons? a-lon)  (or (= target (first a-lon))
                              (contains? (rest a-lon) target))]))



#| 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-the-evens (and leave odd numbers untouched)
; 
(check-expect (tee empty) empty)
(check-expect (tee (cons 4 empty))
              (cons 12 empty))
(check-expect (tee (cons 93 (cons 2 (cons 4 empty))))
              (cons 93 (cons 6 (cons 12 empty))))


; 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) empty]
        [(cons?  a-lon) 
         (cons (if (even? (first a-lon))
                                  (* 3 (first a-lon))
                                  (* 1 (first a-lon)))
                              (tee (rest a-lon)))]))


;;; Reminder, of the data-def'n:
;;;
; list-of-number is:
;      empty, or
;      (cons number list-of-number)   ; "constructed list"










#|
We are *always* returning a cons, so factor out the common code: 
           (cons (if (odd? (first a-lon))
                     (* 1 (first a-lon))
                     (* 3 (first a-lon)))
                 (tee (rest a-lon)))]))
         But hey, we we are always multiplying the first by *something*, so factor:
         |#
#|
         (cons (* (if (even? (first a-lon))
                      3
                      1)
                  (first a-lon))
               (tee (rest a-lon)))]))


|#






;;;;;;;;;;;;;;; my-max

(check-expect (my-max (cons 4 (cons 7 empty))) 7)

(check-expect (my-max (cons 4 (cons 7 empty))) 7)
;(check-expect (my-max empty) -inf.0) ; Um, this *claims* to fail

(check-expect (my-max (cons -5 (cons -4 (cons -3 (cons -2 (cons -1 empty))))))
              -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)))
                            (my-max (rest a-lon))
                            (first a-lon))]))

; 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 empty)))))))))))))))))))
              -1)

(check-expect (my-max (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 empty)))))))))))))))))))))))
                -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 empty)))))

; 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) empty]
        [(positive? i) (cons (- i) (nums-below-0 (sub1 i)))]))
(check-expect (nums-below-0 2) (cons -2 (cons -1 empty)))
(check-expect (nums-below-0 0) empty)
(check-expect (nums-below-0 1) (cons -1 empty))




; `lambda`






; w/ an add'l argument:
;   deltas; cumulate