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 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.