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