(lambda x ...) (lambda (x y . z) ...) (case-lambda [(x) ...] [(x y) ...] ...)

A Scheme programmer can also define loops. To understand how, let's first
discuss the definitions of some of the loops that we have already
seen. Here is a simple version of `for-each`

:^{9}

(define (for-each f list1) (cond [(null? list1) null] [else (begin (f (car list1)) (for-each f (cdr list1)))]))

The function consumes a function `f`

and a list and recursively
traverses the list. As long as there are items on the list,
`for-each`

applies `f`

to an item and recursively traverses
the rest of the list. More generally, `for-each`

abstracts the
common situation when programs process each item in a list for some
effect. The traversal process, as encoded here, is always the same. Since
the processing of the items differs from case to case, we have turned the
process step into a function argument. In short, `for-each`

is a
parameterized list traversal.

Let's take a look at a simple version of `foldr`

:

(define (foldr f base l) (cond [(null? l) base] [else (f (car l) (foldr f base (cdr l)))]))

Like `for-each`

, `foldr`

traverses the list and applies
`f`

to each item as it goes. The second argument of each
application, however, is determine via recursion, so that in the end,
`f`

is first applied to the last item on the list and
`base`

. Therefore we say that `foldr`

uses `f`

to
process the list from right to left. Again, `foldr`

parameterizes a
list traversal over which function is actually applied to each item and
over the base case.

With `foldr`

it is also easy to demonstrate how the designers of
Scheme come up with lists. Compare the following two definitions:

The two definitions differ in the base case and in how they combine the
two values in the

`else`

case. The definition of `foldr`

abstracts over just these two values with `base`

and `f`

,
respectively. Conversely, we can define `add`

and `mul`

as
one-liners using `foldr`

:
In general, it is a good idea to introduce new Scheme loops after you have
discovered some similarities between two (or more) functions.

Loops are not only important for lists, vectors, strings and other linear data structures but also for things like trees and forests. Let us define a number tree as the union of two classes of values:

a number is a tree;

and if

`s`

and`t`

are trees and`n`

is a number, then`(list s n t)`

is also a tree.

Here are some examples:

a leaf:

`5`

,a tree with just a left spine:

`'(((-1 5 7) 3 4) -9 11)`

, anda bushy tree:

`'(((+1 5 7) 3 (2 -3 0)) 8 (-17 7 0))`

.

A symbol tree is just like a number tree except that it contains symbols instead of numbers.

Take a look at these two functions on number trees:

Like

`add`

and `mul`

, the two functions differ only in the
base case and the way the two functions combine the results of the
recursions. Defining a loop is almost straightforward. We parameterize the
base value and the combination function:
`;; ``(X Number X --> X) (Number --> X) (Treeof Number) --> X`

(define (foldt f base t)
(cond
[(number? t) (base t)]
[else
(f (foldt f base (car t))
(second t)
(foldt f base (third t)))]))

Instead of using a plain base value though, we use a function that consumes the leaf; similarly, the combination function also consumes the interior node, so that it can be used for computations, too.

With `foldt`

, we can define `height`

and `leaves`

as
follows:

(define (height t) (foldt (lambda (l i r) (+ 1 (max l r))) (lambda (x) 0) t)) | (define (leaves t) (foldt (lambda (l i r) (+ l r)) (lambda (x) 1) t)) |

^{9} The full
version of `for-each`

can work on many lists in parallel and checks
for certain basic conditions as well.