CSC151, Class 31: Higher-Order Procedures, Continued

Overview:
* Review
* Returning procedures from procedures
* Examples: Building new predicates from old
* Example: Building recursive predicates
* Why bother?
* Labs

Notes:
* Don't forget: Extra credit for attending convo tomorrow.
* Note: Yesterday's group work went well.  Why not try it
  regularly?
* Have a great break!

Important morals from yesterday's class
* Figuring out a standard form for standard kinds of
  problems is a good programming strategy
* Work in groups
* Procedures can be parameters

In Scheme, there are standard procedures that (1) expect
other procedures as parameters; (2) encode common programming
techniques.

Important confusions from yesterday's class
* map
* apply

map, version 1: Do something to each element of a list

square each element of a list

(define square-each-element
  (lambda (lst)
    (if (null? lst) null
        (cons (square (car lst)) (square-each-element (cdr lst))))))

(define square (lambda (x) (* x x)))

(define square-each-element
  (lambda (lst) (map (lambda (x) (* x x)) lst)))

f(x) = x^2

  x^2 o 2*x

o = "compose", a function from two functions to one
    (f o g)(x) = f(g(x))

map, version 2: given a procedure and lots of lists
 apply the procedure to the first element of each list (as a group)
 apply the procedure to the 2nd element of each list (as a group)
 apply the procedure to the 3rd element of each list (as a group)
  ...
 and then shove all the results together in a list

(map + (list 1 2 3) (list 4 5 6))

What does apply do?
Given a list of elements, applies the operation to all of them
*as a group*
Intuition: Shove the operation after the open paren.

(apply + (list 1 2 3)) => (+ 1 2 3)

(apply + 4 (list 1 2 3)) => 10
  Sam doesn't know why.
  He'll try to think about it during ****break****

Difference between map and apply
* map can work with multiple lists
* map works between, apply works within
* map works with each element of the list individually,
  apply works with all the elements as a group
(map + (list 1 2 3)) => (1 2 3)
(apply + (list 1 2 3)) => 6

(map list (list 1 2 3)) => ??? ((1) (2) (3))
(apply list (list 1 2 3)) => (1 2 3)

(map list (list 1 2 3) (list 3 4 5)) => ((1 3) (2 4) (3 5))

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

All of these procedures take procedures as parameters
Would you ever return a procedure as a result?
* Certainly

Compose

(define compose
  (lambda (f g)
    (lambda (x) (f (g x)))))

Others?

Negation of predicates

odd?

(define even? (not odd?))
  BOOM

We want something a lot like not that negates predicates

(define even? (negate odd?))

We have to implement negate

(define negate
  (lambda (pred?)
    (lambda (x) (not (pred? x)))))

CRITICISM: This will say that "apple" is even.

We would also like a "both" procedure that combines predicates
  "both" is to "and" as "negate" is to "not"

(define even? (both integer? (negate odd?)))

(define both
  (lambda (pred1? pred2?)
    (lambda (x) (and (pred1? x) (pred2? x)))))

(define either
  (lambda (pred1? pred2?)
    (lambda (x) (or (pred1? x) (pred2? x)))))

It's possible to write procedures that return other procedures.

Why do we care?

Does it let us write programs that do things we couldn't do
  before?
No

It's more elegant!  

If we make a mistake, we can fix the mistake in one place

(define square-each-element
  (lambda (lst)
    (if (null? (cdr lst)) null
        (cons (square (car lst)) (square-each-element (cdr lst))))))