CSC153 2004S, Class 16: Higher-Order Procedures

Admin:
* I hope you stay healthy!
* Note-taking seminar at 4:15
* Choosing a major Wednesday at 4:15
* Questions on the exam?
* When we use a library on an exam or homework, should we submit it?
  * Certainly.

Overview:
* Patterns
* Procedures as parameters
* Anonymous procedures
* Procedures as results
* Lab

Much of the Scheme code you've written to date has had some commonalities

* Find the largest number in a list
* Find the longest string in a list
* Find the smallest number in a list
(define find-BEST
  (lambda (lst)
    ; If the list has only one element
    (if (null? (cdr lst))
        ; That's the best
        (car lst)
        ; Otherwise, use the better of the first element and the
        ; best remaining element.
        (BEST (car lst) (find-BEST (cdr lst))))))

(define find-smallest
  (lambda (lst)
    ; If the list has only one element
    (if (null? (cdr lst))
        ; That's the best
        (car lst)
        ; Otherwise, use the better of the first element and the
        ; best remaining element.
        (min (car lst) (find-smallest (cdr lst))))))

* The first time a student writes a procedure like this, (s)he learns a lot.
* The second and third times a student writes a procedure like this, (s)she learns about subtleties.
* The remaining times are needless typing.

* In some programming languages, you live with it.  (Copy and paste the pattern.)
* In Scheme, you can turn the pattern in to a procedure by making other procedures *parameters* to the pattern
(define find-best
  (lambda (better lst)
    ; If the list has only one element
    (if (null? (cdr lst))
        ; That's the best
        (car lst)
        ; Otherwise, use the better of the first element and the
        ; best remaining element.
        (better (car lst) (find-best better (cdr lst))))))
* Important idea: Procedures can be parameters to other procedures

* Sometimes it's a lot of extra effort to define the "parameter procedures"; in particular, if you're only going to use it once, why name it?
  * E.g., to find the number closest to zero in a list, I need to define a procedure that finds the closer-to-zero of two numbers.  Do I really need to name it?
  * Solution: Anonynmous procedures (lambda (params) body)

* Observation: If you can build anonymous procedures and you can take procedures as parameters, you can also build new procedures *and return them*

* Time to puzzle yourself on the lab
  * Don't you wish "iota" or "count-between" were in your library ?
	(iota n) => (0 1 2 3 4 .... n-1)

SAUL: If you're watching, the examples are in best.scm  (Sorry for not
telling you earlier.)