;; 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 my-max) (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

|#



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

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



;;;;;;;;;;;;;;; my-max
;(check-expect (my-max '()) ...)
(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 (cons -5 (cons -4 (cons -3 (cons -2 (cons -1 '()))))))
              -1)



; 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 : list-of-number -> number 
; Return the largest element of `a-lon`, or ____ if it's empty.
;
#;(define (my-max nums)
   (cond [(empty? nums)  -inf.0]
         [(cons? nums)   (if (> (first nums) (my-max (rest nums)))
                             (first nums)
                             (my-max (rest nums)))]))

; 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`






; 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
                         -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*` 


; Example of using `let*`:
(let* ([a 17]
       [b 23]
       [c (sqrt (+ 99 b))])
  (+ a (cos c)))






#;(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 '())))))


#|
Syntax for let*

<LetStmt> -> (let* (<Bindings>)
                <Expr>)

<Bindings> -> ϵ | <Binding> <Bindings>
<Binding> -> [ <Id> <Expr> ]


Semantics of let:
   An expression whose value is: the value of the (last, "body") expression,
   except that we substitute any of the introduced variables with their
   right-hand-side.

   (This is, like 90% true ... read about `let` vs `let*` for the whole story.)
|#


; Btw, that's all the racket I'll teach:
; - call a function
; - `define` for functions
; - `define` for flat values
; - `cond`
; - `define-struct`
;
; Certainly racket has other things (a class-system, macros, a module system, ...)
; but we're not teaching racket; we're teaching a few fundamental concepts
; (and a language where we don't need to bring in extra concepts to just use the basics).
;
; Note that technically, `if` `and` `or` aren't functions
; (since they short-cut!); but I'll sweep that under the rug
; and pretend they're just library-functions and not separate syntax.




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

; We can convert the following `let`...
 (let {[a 17]
       [b 99]}
   (if (> a 20)
       (sqrt (+ a b))
       (expt a b)))

;; into the folloowing `let`-free version:
(define (conversion-helper a b)
    (if (> a 20)
        (sqrt (+ a b))
        (expt a b)))

(helper 17 99)

;; And if we want to avoid a top-level define, 
;; we can use an anonymous function (see
;; upcoming lecture on functions-as-values):

((lambda (a b) (if (> a 20)
                   (sqrt (+ a b))
                   (expt a b)))
 17
 99)





;  - 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
|#