(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
(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,
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
(define (foldr f base l) (cond [(null? l) base] [else (f (car l) (foldr f base (cdr l)))]))
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
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.
foldr it is also easy to demonstrate how the designers of
Scheme come up with lists. Compare the following two definitions:
elsecase. The definition of
foldrabstracts over just these two values with
f, respectively. Conversely, we can define
mulas one-liners using
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;
t are trees and
n is a
(list s n t) is also a tree.
Here are some examples:
a tree with just a left spine:
'(((-1 5 7) 3 4) -9 11), and
a 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:
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.
foldt, we can define
(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
for-each can work on many lists in parallel and checks
for certain basic conditions as well.