recitation 6: higher order procedures & types

--------------------------------------------
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 describes a set of scheme values  
* some expressions can have multiple types
* choose the type which describes the largest set

(let ((* /)
      (/ *))
  (/ 12 (* 6 3)))
      
* value: 24
* type: number

(define foo (lambda (x) x))

* example use of foo: (foo 4) => 4
* type of foo: a -> a

(define (bar) (lambda (x) x))

* example use of bar: ((bar) 4) => 4
* type of bar: void -> (a->a)

((lambda (x + y) (+ x y)) 
    3 * 4)

* value: 12
* type: number

(lambda (x + y) (+ x y))

* value: procedure
* type: a,(a,b->c),b -> c

--------------------------------------------
Write a function fmax that takes two functions f and g (that each take
a number) and returns a function, that when called with a number x,
returns the max of f(x) and g(x). For example:
 
(define max-square-sqrt (fmax square sqrt))
(max-square-sqrt 3) => 9
(max-square-sqrt 0.25) => 0.5

(define fmax 
  (lambda (f g) 
    (lambda (x)
      (let ((fx (f x))
	    (gx (g x)))
	(if (> fx gx) fx gx))))

* type of max-square-sqrt: number -> number

* type of fmax: (A->number), (A->number) -> (A->number)

--------------------------------------------
Write swap-args:

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

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

* type of backwards-cons: A, B -> Pair<B,A>

* type of swap-args:  (A,B->C) -> (B,A->C)

--------------------------------------------
Write apply-all:

(apply-all (list abs square cube inc) -4) -> (4 16 -64 -3)

(define apply-all 
  (lambda (procs x)
    (if (null? procs)
	nil
	(cons ((car procs) x)
	      (apply-all (cdr procs) x)))))

* type of apply-all: List<A->B>,A -> List<B>

--------------------------------------------
Write cube-neighbor-diff:

(cube-neighbor-diff (list 1 3 4 7)) => (8 1 27)

(define (cube-neighbor-diff lst)
  (cond ((null? lst) nil)
	((null? (cdr lst)) nil)
	(else (let ((a (- (cadr lst) (car lst))))
		(cons (* a a a)
		      (cube-neighbor-diff (cdr lst)))))))

--------------------------------------------
(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