# 2  More on Lambda

```(lambda x ...)

(lambda (x y . z) ...)

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

## 2.1  Defining Loops

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:

 ```;; `(Listof Number)  -->  Number` ;; to compute the sum of ;; the numbers on `alon` (define (add alon) (cond [(null? alon) 0] [else (+ (car alon) (add (cdr alon)))])) ``` ```;; `(Listof Number)  -->  Number` ;; to compute the product of ;; the numbers on `alon` (define (mul alon) (cond [(null? alon) 1] [else (* (car alon) (mul (cdr alon)))])) ```
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`:
 ```;; `(Listof Number)  -->  Number` ;; to compute the sum of ;; the numbers on `alon` (define (add alon) (foldr + 0 alon)) ``` ```;; `(Listof Number)  -->  Number` ;; to compute the product of ;; the numbers on `alon` (define (mul alon) (foldr * 1 alon)) ```
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:

1. a number is a tree;

2. 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)`, 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:

 ```;; `(Treeof Number)  -->  N` ;; determine the height of `t` (define (height t) (cond [(number? t) 0] [else (+ 1 (max (height (car t)) (height (third t))))])) ``` ```;; `(Treeof Number)  -->  Number` ;; count the # of leaves of `t` (define (leaves t) (cond [(number? t) 1] [else (+ (leaves (car t)) (leaves (third t)))])) ```
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)) ```
And better still, we can also define ``one-liners'' that add all the numbers in a tree, multiply them, translate them into strings, and so on. By parameterizing data structure traversals, we quickly obtain powerful functions, and loops are just a special case.

9 The full version of `for-each` can work on many lists in parallel and checks for certain basic conditions as well.