;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname lectures2) (read-case-sensitive #t) (teachpacks ((lib "world.ss" "teachpack" "htdp") (lib "testing.ss" "teachpack" "htdp"))) (htdp-settings #8(#t constructor repeating-decimal #f #t none #f ((lib "world.ss" "teachpack" "htdp") (lib "testing.ss" "teachpack" "htdp")))))
;; Lecture 1: Design Recipe, Higher Order Functions, Accumulators
;; Lecture 2: Programmer-Defined Loops vs. Built-In Loops
;; September 5 and 6, 2007

#|
Our goal is to recall the design of programs in Scheme-like language
focusing on the Design Recipe.

We start with a simple problem: find the largest number in a list of
numbers.

Problem Anaysis and Data Definition:
------------------------------------

We realize that there is no answer to the problem if the list is empty,
and so we reword the problem to specify that we only work with nonempty
lists. The function max-num will consume a nonempty list of numbers and 
produce a number.

We add the needed data definition - to help us in designing the solution
especially the template/inventory:

A nonempty list of numbers Nelon is one of
-- (cons Number empty)
-- (cons Number Nelon)

Purpose, Contract, Function Header:
-----------------------------------

;; to produce the largest number in an nonempty list of numbers
;; max-num: Nelon -> Number
(define (max-num nelon) ...)

Examples:
---------

(define list1 (list 1 2 3))
(define list2 (list 3))
(define list2 (list 3 8 56 12))

(max-num list1) -- should be 3
(max-num list2) -- should be 3
(max-num list3) -- should be 12

Template/Inventory:
-------------------

We compare the function header with the data definition.
We will need a 'cond' with two clauses to follow the shape of the
data definition. We cannot distinguish between the two clauses by 
asking: (empty? nelon) - as the listt will never be empty. The correct
way to make the choice is to look at the nature of the (rest nelon).
We get the following template:

;; to produce the largest number in an nonempty list of numbers
;; max-num: Nelon -> Number
(define (max-num nelon) 
  (cond
     [(empty? (rest nelon)) ...]
     [(cons?  (rest nelon)) ... (first nelon) ...           -- Number
                            ... (rest nelon) ...            -- Nelon 
                            ... (max-num (rest nelon)) ...  -- Number

We see that the meanig of the (max-num (rest nelon)) is the largest number 
in the rest of ths list of numbers.


Function Body:
--------------

;; to produce the largest number in an nonempty list of numbers
;; max-num: Nelon -> Number
(define (max-num nelon) 
  (cond
     [(empty? (rest nelon)) ...]
     [(cons?  (rest nelon)) 
         (get-bigger (first nelon) 
                     (max-num (rest nelon)))]))

where get-bigger is a function we put on the wish list:

;; get-bigger : Number Number -> Number
;; produce the bigger of the two given numbers
(define (get-bigger num1 num2) ...)

Tests:
------

We finish with converting our examples into executable tests:

(check-expect (max-num list1) 3)
(check-expect (max-num list2) 3)
(check-expect (max-num list3) 12)

Tracing how the program derives the answer we see the following:

(max-num (list 3 8 56 12)) --->
(get-bigger 3 (max-num (list 8 56 12))) --->
(get-bigger 3 (get-bigger 8 (max-num (list 56 12))))) --->
(get-bigger 3 (get-bigger 8 (get-bigger 56 (max-num (list 12))))) --->
(get-bigger 3 (get-bigger 8 (get-bigger 56 12))) --->
(get-bigger 3 (get-bigger 8 56))) --->
(get-bigger 3 56)) --->
56

|#

(define list1 (list 1 2 3))
(define list2 (list 3))
(define list3 (list 3 8 56 12))


;; get-bigger : Number Number -> Number
;; produce the bigger of the two given numbers
(define (get-bigger num1 num2)
  (cond 
    [(> num1 num2) num1]
    [else num2]))

;; max-num1 : [NonemptyListof Number] -> Number
;; produce the maximum number in the given nonempty list of numbers
(define (max-num1 nelon)
  (cond
    [(empty? (rest nelon)) (first nelon)]
    [(cons? (rest nelon))  (get-bigger (first nelon) 
                                       (max-num1 (rest nelon)))]))


#|

We realize that we could keep track of the 'knowledge' about the result
that we find as we traverse the list, and aviod waiting to compute the
final answer until we get the replies from the 'far end of the list':

If the list has only one element - it is the largest in the list.
Otherwise, we keep the largest element so far, and as we find each new
item, we choose whether to keep the previous value (if it is larger that
the one we see now) or replace it with the current value (if it is larger
than the previous maximum). We get:
|#


;; max-num2 : Nelon -> Number
;; produce the maximum number in the given nonempty list of numbers
(define (max-num2 nelon)
  (max-num-acc (first nelon) (rest nelon)))

;; max-num2 : [Listof Number] -> Number
;; produce the maximum number in the given list of numbers or the given acc
;; acc: the largest number seen so far
(define (max-num-acc acc alon)
  (cond
    [(empty? alon) acc]       ;; at the end acc is the desired largest value
    [(cons? alon)             ;; replace acc with the larger of the acc
                              ;; and the current first element
                              ;; and invoke max-num-acc on the rest of the list
     (max-num-acc (get-bigger acc (first alon))
                                (rest alon))]))

;; --- See the examples below

#|
We trace this computation:

Tracing how the program derives the answer we see the following:

(max-num2 (list 3 8 56 12)) --->
(max-num-acc 3 (list 8 56 12)) --->
(max-num-acc (get-bigger 3 8) (list 56 12)) --->
(max-num-acc 8 (list 56 12)) --->
(max-num-acc (get-bigger 8 56) (list 12)) --->
(max-num-acc 56 (list 12)) --->
(max-num-acc (get-bigger 56 12) '()) --->
(max-num-acc 56 '()) --->
56

We see that we carry over each intermediate result and at the end just
provide the answer.

;;-----------------------------------------------------------------------------

We now recall the Scheme loops from page 313 in HtDP:

;; foldr : (X Y -> Y) Y (listof X) -> Y
;; (foldr f base (list x-1 ... x-n)) = (f x-1 ... (f x-n base)...)
(define (foldr f base alox) ...)

and

;; foldl : (X Y -> Y) Y (listof X) -> Y
;; (foldl f base (list x-1 ... x-n)) = (f x-n ... (f x-1 base)...)
(define (foldl f base alox) ...)

To rewrite our two solutions using these two loops we first look at the 
data types. The result in our case is a Number, so Y represents Numbers.
The elements of the list the function consumes are also Numbers, and so
X represents Numbers too.

The function f then has a contract f : Number Number -> Number
and it is used to combine the base with an element of the list.

Our function 'get-bigger' has the correct contract and serves the desired
purpose. We now just need to figure out what should be the base for this
computation. The base is the result we produce if the given list is empty.

We get the following two ways of writing the solution:

|#


;; max-num-left : [NonemptyListof Number] -> Number
;; produce the maximum number in the given nonempty list of numbers
(define (max-num-left nelon)
  (cond
    [(empty? (rest nelon)) (first nelon)]
    [else (foldl get-bigger (first nelon) (rest nelon))]))

;; max-num-right : [NonemptyListof Number] -> Number
;; produce the maximum number in the given nonempty list of numbers
(define (max-num-right nelon)
  (cond
    [(empty? (rest nelon)) (first nelon)]
    [else (foldr get-bigger (first nelon) (rest nelon))]))

;; --- See the tests below

#|
Finally, we want to see what is the difference between the two computations.
Again, we trace the behavior for a specific list:

(max-num-left (list 3 8 56 12)) --->
(foldl get-bigger 3 (list 8 56 12)) --->
(get-bigger 12 (get-bigger 56 (get-bigger 8 3))) --->
(get-bigger 12 (get-bigger 56 8)) --->
(get-bigger 12 56) --->
56

This is the same sequence of operations we have seen in max-num-acc.

(max-num-right (list 3 8 56 12)) --->
(foldl get-bigger 3 (list 8 56 12)) --->
(get-bigger 8 (get-bigger 56 (get-bigger 12 3))) --->
(get-bigger 8 (get-bigger 56 12)) --->
(get-bigger 8 56) --->
56

This is the same sequence of operations we have seen in our original solution
max-num.


|#

;; Tests
(check-expect (max-num1 list1) 3)
(check-expect (max-num1 list2) 3)
(check-expect (max-num1 list3) 56)

(check-expect (get-bigger 3 9) 9)
(check-expect (get-bigger 13 9) 13)
(check-expect (get-bigger 9 9) 9)

(check-expect (max-num1 (list 3 4 9 2 3 8)) 9)
(check-expect (max-num1 (list 3)) 3)

(check-expect (max-num2 (list 3 4 9 2 3 8)) 9)
(check-expect (max-num2 (list 3)) 3)

(check-expect (max-num-left (list 3 4 9 2 3 8)) 9)
(check-expect (max-num-left (list 3)) 3)

(check-expect (max-num-right (list 3 4 9 2 3 8)) 9)
(check-expect (max-num-right (list 3)) 3)

(generate-report)