2011-09-27

SICP Exercise 2.23: For Each

The procedure for-each is similar to map. It takes as arguments a procedure and a list of elements. However, rather than forming a list of the results, for-each just applies the procedure to each of the elements in turn, from left to right. The values returned by applying the procedure to the elements are not used at all -- for-each is used with procedures that perform an action, such as printing. For example,
> (for-each (lambda (x) (newline) (display x))
            (list 57 321 88))
57
321
88
The value returned by the call to for-each (not illustrated above) can be something arbitrary, such as true. Give an implementation of for-each.

Well, the definition of map given in the book is:
(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))
The procedure for-each differs from map in only a couple of points:
  • It doesn't need to cons the results of applying proc to (car items) - it just needs to apply the procedure.
  • It can just return #t instead of a list.
We could just use map to implement this. After all, map applies proc to each element in turn. It happens to produce a list as a result, but we could throw this away and return #t:
(define (for-each proc items)
  (map proc items)
  #t)
This works as expected:
> (for-each (lambda (x) (newline) (display x))
            (list 57 321 88))
57
321
88 #t
However, this has the drawback that we're generating a potentially very large intermediate list and just throwing it away, so let's try to be a bit more space efficient.

When we try this we'll discover that, while we can replace nil with #t okay, we can't just drop the cons from around the application of proc to the head of the list and the recursion of the tail of the list. While we now want to evaluate a couple of procedures separately in the alternative of if, if doesn't support this. It takes three parameters only: the predicate, consequent and alternative. However, we can get around this by replacing the if with a cond as follows:
(define (for-each proc items)
  (cond ((null? items) #t)
        (else (proc (car items))
              (for-each proc (cdr items)))))
Again, this gives the expected results
> (for-each (lambda (x) (newline) (display x))
            (list 57 321 88))
57
321
88 #t
> (for-each (lambda (x) (newline) (display x))
            (list 1 2 3 4 5))
1
2
3
4
5 #t

No comments:

Post a Comment