recitation 6: higher order procedures & types

--------------------------------------------

higher order procedures
types, type notation, type checking

--------------------------------------------

lambda toy:  student, problem -> solution

student:  problem -> solution

lambda toy:  (problem -> solution), problem -> solution

--------------------------------------------

rights & privileges of the
"first-class elements" in a language:

1. may be named by variables
2. may be passed as arguments to procedures
3. may be returned as the results of procedures
4. may be included in data structures

* numbers, cons cells, ..., & even procedures all have first 
  class status in scheme.  this is where scheme really stands 
  out from other languages you may know.

--------------------------------------------
* every expression has a value & a type
* a type desribes a set of scheme values  
* some exressions can have multiple types
* choose the type which describes the largest set

(define foo (lambda (x) x))

(foo 4) -> 4
foo: a -> a

(define (foo) (lambda (x) x))

((foo) 4) -> 4
foo: void -> (a -> a)

(define foo
  (lambda (f) 
    (lambda (x) (f x))))

((foo string-length?) "hello")
foo: (a->b) -> (a->b)

(define (foo f)
  (lambda (x) (f (f (f x)))))
foo:  (a -> a) -> (a -> a)

((foo inc) 0)
((lambda (x) (inc (inc (inc x)))) 0)
(inc (inc (inc 0)))
3

((foo (foo inc)) 0)
((foo (lambda (x) (inc (inc (inc x))))) 0)
((lambda (x) (inc (inc (inc   (inc (inc (inc   (inc (inc (inc x)))))))))) 0)
(inc (inc (inc   (inc (inc (inc   (inc (inc (inc 0)))))))))
9

(((foo foo) inc) 0)

<lots of steps>

27

--------------------------------------------

(define backwards-cons (swap-arg cons))
(backwards-cons 1 2) -> (2 . 1)

((swap-args cons) 1 2) -> (2 . 1)

swap-args:  (a,b->c) -> (b,a->c)

(define (swap-args f)
  (lambda (x y) (f y x)))

--------------------------------------------
map/filter/fold-right

(define (map proc lst)
   (if (null? lst) nil
       (cons (proc (car lst))
             (map proc (cdr lst)))))

map:  (a->b,list(a)) -> list(b)
(map square (list 1 2 3 4)) -> (1 4 9 16)

(define (filter pred lst)
    (cond ((null? lst) nil)
          ((pred (car lst))
           (cons (car lst) (filter pred (cdr lst))))
          (else (filter pred (cdr lst)))))

filter:  (a->boolean,list(a)) -> list(a)
(filter even? (list 1 2 3 4 5 6)) -> (2 4 6)

(define (fold-right op init lst)
   (if (null? lst)
       init
       (op (car lst)
           (fold-right op init (cdr lst)))))

fold-right:  ((a,b->b),b,list(a)) -> b
(fold-right + 0 (list 1 2 3)) -> 6

--------------------------------------------