;; 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-lambda-reader.ss" "lang")((modname lect12c) (read-case-sensitive #t) (teachpacks ((lib "universe.ss" "teachpack" "2htdp") (lib "image.ss" "teachpack" "2htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "universe.ss" "teachpack" "2htdp") (lib "image.ss" "teachpack" "2htdp")))))
;;;; lect12c, 2012fall:  skip the `fold` and loops; search for 'higher-order' ;;;;
;;;;;;;;;;;


;;; We have seen list-processing functions
;;; that follow the template.
;;; Many commonly-used functions are maps and filters;
;;; we defined those functions `map` and `filter`
;;; that take in function.
;;;
;;; There is one more: fold,
;;; The mother of all(*) list-processing functions.
;;;
;;; (*) Well, all *structurally recursive* functions,
;;; that is, those whose answer just depends on the fields
;;; (and a recursive call, if the field's data type is recursive). 
;;;
;;; Consider: what is repeated in each the following functions?:

(define (sum-all data)
  (cond [(empty? data) 0]
        [(cons?  data) (+ (first data)
                          (sum-all (rest data)))]))
    
(define (my-length data)
  (cond [(empty? data) 0]
        [(cons?  data) (add1 
                        (my-length (rest data)))]))

(define (remove99s data)
  (cond [(empty? data) empty]
        [(cons?  data) (if (= 99 (first data))
                           (remove99s (rest data))
                           (cons (first data) (remove99s (rest data))))]))

(define (contains99? data)
  (cond [(empty? data) false]
        [(cons?  data) (or (= 99 (first data))
                           (contains99? (rest data)))]))
  
  
(define thresh 17)
(define (count-bigs nums)
  (cond [(empty? nums) 0]
        [(cons?  nums) (+ (if (> (first nums) thresh) 1 0)
                          (count-bigs (rest nums)))]))
    
; similarly, reverse, etc.


;;; We'll do what we always do when we have repeated code:
;;; We'll factor out the common parts into a function,
;;; and pass in (as an argument) the little bits that differ:

;; We hate writing all the above, because so much
;; of it is rote, repeated boilerplate:
;; the natural list-processing template:
#;(define (f data)
  (cond [(empty? data) ...]
        [(cons?  data) (... (first data)
                            (f (rest data)))]))

; sum a list:
(check-expect (my-fold +
                       0 
                       (list 1 9 2 8 3 7))
              30)

; N.B. Another (long-winded) way of saying "+"
; is "(λ (f rr) (+ f rr))"


; SELF-CHECK (fill in the ...s):
; length of a list:   
(check-expect (my-fold (λ (f rr) (add1 rr))
                       0
                       (list 'a 'b 'c 'd))
              4)



    
; remove99s from list:
(check-expect (my-fold (λ (f rr) (if (= 99 f)  rr  (cons f rr)))
                       empty
                       (list 23 99 17 99 99 5 99 3 99))
              (list 23 17 5 3))

    
; SELF-CHECK (fill in the ...s):
; Count the items bigger than thresh:
#;(check-expect (my-fold ...
                       ...
                       (list 23 99 17 99 99 5 99 3 99))
              6)

;;; Challenge: write a loop using my-fold, that does 'contains99?'.
;;; Discuss the difference in how the my-fold version runs
;;; differently from the version we defined above.




; my-fold : (alpha beta -> beta) beta (list-of alpha) -> beta
; Given `combiner`, a *rule* for combining the first item of a list
;  with the *result* of the recursive call,
; along with the base case and the list to process,
; process that list as instructed:
;
(define (my-fold combiner base-case data) 
  (cond [(empty? data) base-case]
        [(cons?  data) (combiner (first data)
                                 (my-fold combiner base-case (rest data)))]))

 
 




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;; rolling your own loops ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; How to write our own loop?:
; We *wish* we could write something like:

; (while-v1 string-short? "hello" append-dot)
;    =>   "hello............"
;; (suppose I'm building a table of contents, and want to right-pad a string.)

; Let's turn our wishes into check-expects.
; We'll use lambdas, rather than name the helper functions:
(check-expect
  (while-v1 (lambda (ssf) (< (string-length ssf) 15)) 
            (lambda (ssf) (string-append ssf "."))
            "hello")
  "hello..........")

(check-expect
  (while-v1 (lambda (s) (< (string-length s) 3))
            (lambda (s) (string-append s "."))
            "hello")
  "hello")



;;; Hey, since we can pass around functions like that,
;;; we can combine notions from writing 'fold' and from
;;; writing tail-recursive functions, and do this!

; while-v1 : (alpha->boolean), (alpha->alpha), alpha   ->  alpha
; Starting with `so-far`, as long as `(continue? so-far)` returns
; true, we update `so-far` to be `(body so-far)`.
;
(define (while-v1 continue? body so-far)
  (if (continue? so-far)
      (while-v1 continue? body  (body so-far))
      so-far))

#|  The Java equivalent loop:
  soFar = [initial value passed in];                   
  while (continue?(soFar)) {
    soFar = body(soFar);
    }
|#



; OPTIONAL:
; We could also avoid having to continually re-pass
; the same continue-condition and body each time:
;
(define (while-v1b continue? body init)
  (letrec {[my-loop (λ (so-far) (if (continue? so-far)
                                 (my-loop (body so-far))
                                 so-far))]}
  (my-loop init)))

; (*** N.B. in full `#lang racket` you can use internal defines.)


; OPTIONAL:
; We could also combine having to define the function
; and make the initial call to it by using "named let",
; (a construct invented for exactly this sort of situation).
;   (***requires `#lang racket` for named-let)
;
#|
(define (while-v1c continue? body init)
  (let my-loop {[so-far init]}
    (if (continue? so-far)
        (my-loop (body so-far))
        so-far)))
|#
;
; Remember that regular `let` can be re-written as a function call,
; so this variant "named-let" is actually pretty natural.



; Note that the code for while-v1 does *not* come from the design recipe!
; It is "generative recursion" -- it recurs on a new thing it just generated,
; rather than a sub-structure of its input.
; Nothing wrong with generative recursion, but notice that
; there's no longer any *guarantee* of termination.
; (If we used the design-recipe and onlyl recurred on substructures,
;  we were guaranteed termination for free.)
;
; For example: will this terminate?
;   http://en.wikipedia.org/wiki/Collatz_conjecture
;
(define (>1? n) (> n 1))  ; is n bigger than 1?
    
(define (collatz n)
  (if (even? n) 
      (/ n 2)
      (+ (* 3 n) 1)))

(while-v1  >1?  collatz  2345)



;;; Check out a Java version:
;;; http://www.radford.edu/itec380/2011fall-ibarland/Lectures/LoopDemo/FunctionalWhile.java
    

; self-check: write a version of while, where you
; provide both an index *and* an accumulator variable.
;
#;(while-v2 positive? 15 sub1
          (lambda (s) (string-append s "hi")) "")

; To think about:
; What if we had three variables to update each time through the loop?
; What might a general-purpose 'while' look like?

; Can we write a 'for' loop, similar to while-v1?


#;(check-expect
 (for 1 12 
      ???
      "blastoff!")
 "11..10..9..8..7..6..5..4..3..2..1..blastoff!")
 
#| First:
How to complete the Java code?:

  String asf = "blastoff!";  // asf="answer so far"
  for (int i=1;  i < 12;  ++i) {
     asf = i + ".." + asf;
     }
|#

; Now we can figure out the body we'd want to use for our loop:

(check-expect
 (for 1 12 
      (λ (i asf) (string-append (number->string i) ".." asf))
      "blastoff!")
 "11..10..9..8..7..6..5..4..3..2..1..blastoff!")

; Task:
; (a) What is the signature of `for`?
; (b) Now, write the code for it.
; (answers below the next block comment)


#|

By the way: what is Java's rationale for having
both a loop 'while', and a loop 'for'?
After all, either can be re-written into the other.
The answer is in a `hile` loop, the control flow
is scattered/commingled throughout the rest of the code;
in a for-loop the control-flow logic is all grouped
together in a single line,
letting you focus on the loop-body entirely by itself.
(However, `while` is more natural in some settings, so
it's not entirely superceded by `for`.)

map, filter, fold take this a step further:
When I look at a for-loop, 90% of the time it's
 "int i=0;  i < N;  ++i", and I know that idiom well.
But I still have to pore over the body, to see if it's
doing mapping, filtering, or folding (or something else).
When I see code written with map,filter (and to a lesser
 extent, fold) I can even more quickly tell what the
code is doing, knowing those idioms.

|#



; for : number number (number, alpha -> alpha) alpha -> alpha
;
(define (for start stop body so-far)
  (if (< start stop)
      (for (add1 start) stop body (body start so-far))
      so-far))
;
; Again, if you really hated how we pass `limit` and `body`
; in each recursive call even though they don't change,
; you can use `let`
; to make a helper function that only takes in the two
; changing arguments, and uses `limit` and `body` from
; its closure.




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;; higher-order functions ;;;;;;;;;;;;;;;;;;;;;;;;;
#|
 
So: map,filter,fold (and the safe-for-space foldl) replace 99% of all my loops.
  (N.B. the full racket lang extends map and fold to all collections.
   It also includes some syntactic sugar to help get rid of the lambda,
   with their `for` forms:
  (define data (list 17 23 99))
  (for/list {[itm data]}
      (+ (* itm 5) 3))
  is equivalent to `(map (lambda (itm) (+ (* itm 5) 3)) data`.
  The for/ forms also let you collect the results not *just* into a list,
  but instead you can collect them into a vector or a string or a hash-table or ...
  )


But to use them effectively, you need to be able to easily create the
functions you want to pass in to map, while, etc.


- higher-order functions (functions that return functions):

(filter even? data)
(filter positive? data)
; How to get all the even, positive numbers?
; One way would be to make two passes:

???

; But this won't work if replace 'and' with 'or' (at least not easily).
; Another way (and one that generalizes better) is to make a `positive-even?`:


 (λ (astr) (or (too-small? astr) (off-screen? astr))


(filter  (λ (n) (and (even? n) (positive? n)))  data)

In fact, we find ourselves doing this a lot: combining two predicates with `and`:  e.g.
(filter (λ (astr) (or (too-small? astr) (off-screen? astr)) all-astrs)

We'd like something shorter.
Why won't this work?:

(filter (and even? positive?) data)
(filter (or too-small? off-screen?) all-astrs)  

What would you need to write instead of each of these?

Can you generalize this to an "and for functions", called, say, `and/f`?

(filter (and/f even? positive?) data)

;That is:
(and/f even? positive?)  =  (λ (n) (and (even? n) (positive? n)))

(check-expect (and/f even? postive?)
              (λ (n) (and (even? n) (positive? n))))

(define (and/f f1 f2)
        (λ (n) (and (f1 n) (f2 n)))

(define (and/f f1 f2)
  (define (the-func n) (and (f1 n) (f2 n)))
  the-func)


 (or/f too-small? off-screen?)


|#


; and/f : (alpha->boolean), (alpha->boolean)  ->  (alpha->boolean)
;
(define (and/f  f1  f2) 
  (λ (itm) (and (f1 itm) (f2 itm))))


#|
hw problem: Write "non"
Example:  (non positive?) returns a function that takes
  in a number, and returns true iff(*) it's non-positive.


(*) iff = "if and only if"

;  What is `non`s signature?
;  `non` is also very handy with filters.

;;; Self-check:
;;; 'compose' is handy:
;;; example: (compose string-length number->string)

; What is the type of `compose`?
; compose : (string -> number) (number -> string) -> (number -> number)
; compose : (β -> γ), (α -> β) -> (α -> γ)




;;; If interested in more: read about
;;;   andmap
;;;   apply   (apply + (map string-length (list "hi" "bye" "etc"))) = 8
;;;   Write filter, using fold
;;;   


- Curried functions

Suppose I have a list of strings, and want to add a prefix to each of them:

(map (λ (nm) (string-append "Ms. " nm)) names)
(map (λ (nm) (string-append "Name: " nm)) names)
(map (λ (nm) (string-append ">>> " nm)) names)
(map (λ (nm) (string-append "Dear Sir/Madam " nm)) names)

; I'd like to abstract away the repeated code:

(map (make-prepender "Ms. ") names)
(map (make-prepender "Name: ") names)
(map (make-prepender ">>> ") names)
(map (make-prepender "Dear Sir/Madam ") names)

; make-prepender : string -> (string->string)
;
(define (make-prepender pref)
  (λ (str) (string-append pref str))

Of course, `make-prepender` doesn't *have* to have its result used by `map`;
you can use the result wherever you like:
((make-prepender "equi") "lateral")

(define friend-maker (make-prepender "Howdy, "))
(friend-maker "Amy")
(map friend-maker names)

; You might have a gui, where the user enters the desired prefix,
; and then you pass the result of make-prepender into a bunch
; of other code for doing maps etc.


Similarly, I often want to go through and adjust everybody's hw score:
Rather than
   (map (λ (gr) (+ gr 7)) hw-scores)
I'd like to say
   (map (make-adder 7) hw-scores)
   ((make-adder 7) 19)             ; = 26


>>> Your task: Write make-adder.


make-adder is "curried" version of +.
And make-prepender is a curried version of string-append.
That is: instead of a two-argument function that needs both its inputs immediately,
  we have a variant where we give the first argument to the curried version,
  getting back a function.  Then later, we can give the second argument to that function.
Curried versions are often handy when used w/ map, filter.


[In O.O., this is related to the "builder pattern", and (when talking about constructors in particular), the "factory pattern".]
 

(Haskell Curry, logician; in the language Haskell (named in his honor),
*every* function is a function of one argument -- everything is auto-curried!
(Or: if you ever call a function but don't give it enough arguments,
  you automatically get back a function that just needs to be handed 
  the remaining arguments.))

An exercise to blow your mind:
- "curry" itself is a function!
  (curry +) = make-adder
  (curry string-append) = make-prepender
- What is (curry <) ?
  Give an example of using (curry <).
- What is the signature of `curry`?
- Write `curry` !


;;;; Another example of *using* curried function:
;;;; we saw in lect12b, quicksort:
;
(define (qsort nums)
  (cond [(empty? nums) empty]
        [else
         (define pivot  (first nums))
         (define smalls (filter ((curry >) pivot) nums))
         (define equals (filter ((curry =) pivot) nums))
         (define bigs   (filter ((curry <) pivot) nums))
         (append (qsort smalls) equals (qsort bigs))]))

;;; Remember, `((curry >) 3)` = `(λ (x) (> 3 x))`.



Another example of currying a function (slight digression):
Imagine the definite-integral of x^2 from 4 to 7.
The answer is 7^3/3 - 4^3/3, some particular number.
But if you left off the top integration bound (7),
and just took the integral from 4 to some "b" to be determined later,
you'd get back
   λ b . b^3/3 - 4^3/3
That's a curried version of the definite-integral
  (and it's awfully handy on its own!).
In fact, no matter what the lower bound was, you get
   λ b . b^3/3 + C
(where the exact C depends on the lower bound; really
we're getting
   λb,a . b^3/3 - a^3/3
but in calc the exact value of C is unimportant,
so they tend to gloss over the second input, a.)


;;; More on currying:


+ : number, number -> number
make-adder:  number -> (number -> number)

What is the signature for string-append, vs make-prepender?


For example, we had
  has-prefix? : string, string -> boolean
What would you call a curried version, that takes in the first string (the prefix)
and returns a function that always checks for that prefix?

(filter (prefix-checker "The ") band-names)
(filter (prefix-checker "A ") band-names)



ex: Write truncate-to : n, string -> string
ex: Write make-truncater : n -> (string -> string)



For hot-shots only:
  Write `curry`:
  (curry +) = make-adder
  (curry has-prefix?) = prefix-checker

(map ((curry +) 7) all-grades)
(map ((curry string-append) "Dear ") names)



Sometimes, you still need to use lambda just to switch the
order of the arguments:
  (map ((curry string-times) 2) (list "hello" "anybody home? " "echo"))
  (map (λ (n) (string-times n "hello")) (list 4 7 3))

Tip: when defining new fnctions (like `has-prefix?`), you
have to choose the order of the arguments.
Think about which version makes the default 'curry' helpful:
have the first arg be one that might be the same in a loop (like "Dear "),
and the second one that might be looped over (like a list of names).
The 'correct' choice usually more clear in retrospect, when you stumble
 across a need for a particular version.

If interested in yet more: see 'cut':  
  http://doc.racket-lang.org/srfi-std/srfi-26.html



CONGRATS TO...UPE inductees Brendan Conniff, Gerald Ottman


|#