# Class 16: Higher-Order Procedures (1)

Back to Vectors. On to Higher-Order Procedures (2).

Held: Monday, 16 February 2004

Summary: Today we investigate higher-order procedures; procedures that take other procedures as parameters or return procedures as values. Higher-order procedures are one of the most important design techniques in the functional paradigm (nearly as important as recursion).

Related Pages:

Assignments:

Notes:

• Are there final questions on Exam 1?

Overview:

• Design patterns, revisited.
• Key ideas of higher-order procedures.
• Lab.

## Design Patterns

• As I've mentioned earlier, the more you program, the more you find that there are many problems whose solutions have similar structures.
• We might then want to look more abstractly at those structures and see what kinds of problems they apply to.
• These solution structures are typically called patterns or design patterns.
• In some languages, patterns are simply a guide to the programmer, giving techniques for designing solutions.
• In Scheme, you can actually encode many patterns in procedures.
• We'll also learn about some related issues: procedures as values and anonymous procedures.

## The Short Version

• What you need to know:
• You can make procedures parameters to other procedures.
• You can write and use anonymous procedures (lambda expressions that are not named).
• Procedures can build and return other procedures.
• Some built-in procedures you should learn.
• `(map proc lst)` -- build a new list by applying `proc` to each element of `lst`.
• `(apply proc lst)` -- call `proc` on the arguments given by `lst`
• Examples
• `(define square-vals (lambda (lst) (map (lambda (x) (* x x)) lst)))`
• `(define sum (lambda (lst) (apply + lst)))`
• Are there any other questions on the readings?

## The Long Version

### Apply to All

• Let's start with two similar problems, both of which somone might use to process a list of grades.
• Add 5 to every value in a list of numbers.
• Multiply every value in a list of numbers by 10/8.
• How might we code these?
• Can we generalize? Certainly
• As you may have noted, this seems a little bit inelegant.
• What else can we do?
• We can take the procedure to apply to each value as a parameter to the general procedure!
• Note that the apply to all design pattern is so common that Scheme includes it as a built-in procedure (called `map`).

### Common Higher-Order Procedures

• `(map proc lst)`: what we just wrote.
• `(apply proc lst)`: a way to treat the elements of lst as parameters to proc.
• Example:
```(define sum (lambda (lst) (apply + lst)))
```

### Anonymous Procedures

• When we use higher-order procedures, we often have to build small helpers that say what to do. For example, consider
```> (let ((square (lambda (x) (* x x))))
(map square (list 1 2 3 4)))
```
• But what does this say? It tells us that `square` is another name for `(lambda (x) (* x x))` and then uses that name.
• When we use the name, Scheme simply substitutes the thing that's been named.
• We can do the substitution ourselves
```(map (lambda (x) (* x x)) '(1 2 3 4))
```
• We've used a procedure without naming it!
• Such unnamed procedures are called anonymous procedures. You'll find that we often use them in conjunction with design patterns.

### Some Other Patterns

• Extract all the elements of a list that meet some criteria.
• Generalization of sum and product?

### Returning Procedures

• Given that we can take procedures as parameters, it may also make sense to return procedures as values.
• What does a procedure value look like? It looks like
```(lambda (arguments) body)
```
• So, here's a procedure that takes one parameter, a number, and returns a procedure. The resultant procedure takes one parameter and adds the first number to its parameter.
```(define make-adder
(lambda (n)
(lambda (v) (+ n v))))
```
• How did we build that? First we thought about the result. We wanted a procedure of one parameter that added some number to its parameter.
```(lambda (v) (+ some-number v))
```
• Now, we want to build that value, filling in some-number.

## History

Back to Vectors. On to Higher-Order Procedures (2).

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri May 7 09:43:11 2004.
The source to the document was last modified on Tue Jan 13 10:26:10 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2004S/Outlines/outline.16.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu