; Lecture 7 Notes
; Functional Abstraction
;
; Functions are values.
;
; Set comprehensions
; S = {0, 1, ..., 9}
; T = {i^2 | i #epsilon S}
;
; In Haskell:
; s = [0..9]
; t = [i * i | i <- s]
;
; sqr x = x * x
;
; map f [] = []
; map f (x:xs)
;  = f x : map f xs
;
; t = map sqr [0..9]
;
; Intermediate Student with Lambda
;

; map: (x -> y) (listof x) -> (listof y)
(define (map_function f lst)
  (cond
    [(empty? lst) empty]
    [else
     (cons (f (first lst))
           (map_function f (rest lst)))]))

(map_function sqr (list 0 1 2))

; S = {0, 1, ..., 9}
; T = {i | i #epsilon S, i even}
;
; S = [0..9]
; t = [i | i <- s, even i]
;
; filter p [] = []
; filter p (x:xs)
;    | p x
;      = x : filter p xs
;    | otherwise
;      = filter p xs
;
; t = filter even [0..9]

; filter: (x -> boolean) (listof x) -> (listof x)
(define (filter p lst)
  (cond
    [(empty? lst) empty]
    [(p (first lst))
     (cons (first lst) (filter p (rest lst)))]
    [else
     (filter p (rest lst))]))

; Funcitons are values.
; (3 + 4) + 5
;
; #lambda x . x^2
;
; sqr x = x * x
;
; sqr = \x -> x * x

(define (sqr x)
  (* x x))

(define sqr
  (lambda (x)
    (* x x)))

; A definition is a name-value binding.

(sqr 4)
=> ((lambda (x) (* x x)) 4)
=> (* 4 4)
=> 16

; New grammar rules:
; expr = (expr expr expr ...)
;      | (lambda (id id ...) expr)
;
; New reduction rules:

(define (f x1 ... xn) exp)
=> (define f (lambda (x1 ... xn) exp))

((lambda (x1 .. xn) exp) v1 ... vn)
=> modexp

; where modexp is exp wiht vi substituted for xi.
;
; Abstracting structural recursion on lists
;
; f [] = ?
; f (x:xs) = ? x ? f xs
;
; c is a combine function, b is a base value, and [] is a list
; foldr c b [] = b
; foldr c b (x:xs)
;    = c x (foldr c b xs)

(define (foldr c b lst)
  (cond
    [(empty? lst) b]
    [else
     (c (first lst)
        (coldr c b (rest lst)))]))

(foldr cons empty lst)

; Contract?
; foldr: (x y -> y) y (listof x) -> y

(foldr + 0 lst)

(define (make-adder x)
  (lambda (y)
    (+ x y)))

(define make-adder
  (lambda (x)
    (lambda (y)
      (+ x y))))

; Contract?
; make-adder: number -> (number -> number)
;
; Remember that the contract for + is
; +: number number -> number

(make-adder 3)
=> ((lambda (x) (lambda (y) (+ x y))) 3)
=> (lambda (y) (+ 3 y))

; plus :: Num a => a -> (a -> a)
; plus x y = x + y
;
; sumlist xs = foldr (+) 0 xs
; sumlist = foldr (+) 0