Mapping Over Lists and Trees

The procedure map takes a procedure and a list, applies the procedure to each element of the list, and returns a list of the results. One way to define map could be

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

(map square (list 1 2 3 4))
;; (1 4 9)

You can also pass anonymous functions with lambda:

(map (lambda (x) (* x 2)) (list 1 2 3))
;Value 7: (2 4 6)

Then use this for more general procedures.

(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

(scale-list (list 1 2 3) 10)
;Value 8: (10 20 30)

You can use recursion to map over trees. Check for leaves as the terminating condition.

(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))

(scale-tree (list 1 2 (list 4 5) 5) 10)

;Value 15: (10 20 (40 50) 50)

The built-in map is more general. If the procedure passed in takes multiple arguments, you can also supply multiple lists. The procedure is applied to all the first elements of the lists, then all the second elements of the list, and so on.

(map + (list 1 2 3 4) (list 10 20 30 40))
;Value 3: (11 22 33 44)

Exercise 2.30 Implement square-tree both directly and by using map and recursion.

;;Direct implementation
(define (square-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? (car tree))) (cons (square (car tree))
                                        (square-tree (cdr tree))))
        (else (cons (square-tree (car tree))
                    (square-tree (cdr tree))))))

;;Using map
(define (square-tree tree)
  (map (lambda (x)
  (if (pair? x)
      (square-tree x)
      (square x)))
       tree))

The version using map is much shorter and easier to grok.

Exercise 2.31 Abstract previous exercise to use a procedure tree-map.

(define (tree-map proc tree)
  (map (lambda (x)
         (if (pair? x)
         (tree-map proc x)
         (proc x)))
   tree))

(define (square-tree tree) (tree-map square tree))

Return

I haven't posted in a while for a few reasons. One was that I needed to rest my brain after wrestling with the Church numerals exercise. When I came back to SICP, I worked through the "extended exercise" on interval arithmetic. I found that stupefyingly dull. Exercise 2.11 did me in. It involved building a complicated system of nested condition-checking. It reminded me of the CS courses I took in school that sapped my will to code. That's perhaps a bit harsh, but it did feel like a pedestrian exercise after the eye-opening new ideas that preceded it. So I bailed on the section and moved on to Section 2.2.

I also decided to take a different tack on my posts. If I cruise through an exercise without much difficulty, I'm not going to document it here. The Scheme Wiki has a good set of solutions if that's what you're looking for. Instead, I'm going to document the major points that I need to reiterate to fully digest, or any sections that I find difficult to grasp. I've worked through much of Chapter 2, so I should have more posts up. I need to review accumulation, folding, the picture language.