SICP 2.21 - 2.23: Mapping over lists

From SICP section 2.2.1 Representing Sequences

The last few exercises in section 2.2.1 introduce the concept of mapping. The map procedure takes a procedure and a list as arguments, and returns a list of the results produced by applying the procedure to each element in the list.

(define (map proc items)
   (if (null? items)
       null
       (cons (proc (car items))
             (map proc (cdr items)))))

The higher-order procedure map abstracts away the details of traversing a list and allows you to think in terms of procedures that you want to apply to an entire list.


Exercise 2.21 asks us to complete two different implementations of square-list by filling in missing expressions. Each procedure takes a list of numbers as its argument and returns a list of the squares of those numbers. The first example handles list traversal on its own.

(define (square-list items)
   (if (null? items)
       null
       (cons (* (car items) (car items))
             (square-list (cdr items)))))

Note that the structure is identical to that of map. The only difference is that the procedure applied to each element of the list is hard-coded instead of passed in as a parameter.

The second implementation defines square-list in terms of map.

(define (square-list items)
   (map (lambda (x) (* x x)) items))

There's a major difference here. In the second implementation we only need to think about the procedure that we want to apply to each element of the list and map takes care of the rest.

> (square-list (list 1 2 3 4 5))
(1 4 9 16 25)

Exercise 2.22 shows us two attempts at implementing square-list using an iterative process and asks us to explain what's wrong with them.

(define (square-list items)
   (define (iter things answer)
     (if (null? things)
         answer
         (iter (cdr things)
               (cons (square (car things))
                     answer))))
   (iter items null))

This first implementation produces a list in the reverse order of the input list.

> (square-list (list 1 2 3 4 5))
(25 16 9 4 1)

The result is reversed because as the procedure iterates through the list it takes an item from the front of the list, squares it, then puts the square on the front of the answer list. The square of the last item in the original list will be the last item placed at the front of the answer list.

The implementer tried to fix this bug by interchanging the arguments to cons:

(define (square-list items)
   (define (iter things answer)
     (if (null? things)
         answer
         (iter (cdr things)
               (cons answer
                     (square (car things))))))
   (iter items null))

This may seem like a reasonable thing to do, but it produces a very strange looking result.

> (square-list (list 1 2 3 4 5))
(((((() . 1) . 4) . 9) . 16) . 25)

By flipping the arguments to cons, we've made the first argument a list and the second argument an integer. At every step we're combining the list from the previous step with a new integer and wrapping them in a new list. That accounts for the weird looking result. The good news is that the results are in the right order.

A correct iterative implementation would only require a small change.

(define (square-list items)
   (define (iter things answer)
     (if (null? things)
         answer
         (iter (cdr things)
               (append answer
                       (list (square (car things)))))))
   (iter items null))

Here we just use append to add the new squared value to the end of the answer list each time through the loop, just like we saw in the reverse example in exercise 2.18.

> (square-list (list 1 2 3 4 5))
(1 4 9 16 25)

Exercise 2.23 asks us to implement a for-each procedure, which is very similar to map. The for-each procedure takes a procedure and a list as its arguments, but instead of returning a list it just applies the procedure to each element of the list.

(define (for-each proc items)
   (cond ((null? items) #t)
         (else (proc (car items))
               (for-each proc (cdr items)))))

This is nearly the same as the implementation of map that we started out with. The main difference in implementation is that we need to execute two separate statements in sequence in the else clause instead of just one cons statement.

> (for-each (lambda (x) (newline) (display x))
         (list 57 321 88))

57
321
88#t

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.