SICP Exercise 2.33: Accumulations

Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:

(define (map p sequence)
  (accumulate (lambda (x y) <??>) nil sequence))
(define (append seq1 seq2)
  (accumulate cons <??> <??>))
(define (length sequence)
  (accumulate <??> 0 sequence))

First, map... The procedure accumulate produces a single value by iterating over the list and, for each element in the list, applying a supplied two-parameter procedure to the element and the results of applying accumulate to the rest of the list. We want to produce a list as our result that contains the same number of elements as the original list, but that has applied the procedure p to each element. We're given a hint in our base case - it's the empty list. If we apply p to each element in the list and then use cons to put this result onto the head of the accumulated result for the remainder of the list then this will give us the desired result:

(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y))
              nil
              sequence))

Next append... We want append to put all of the items from seq1 onto the front of seq2. We know we're going to be using cons to perform the accumulation step, and we know that accumulate works in a manner equivalent to starting with the last item of the list it is accumulating over and applying op to it and the accumulated result so far, starting with some initial value and repeating that backwards throughout the list. So if we start with an initial value of seq2 and cons each item from seq1 to it, starting at the last and working through to the first then we will produce an equivalent implementation to append. Therefore we can implement append as follows:

(define (append seq1 seq2)
  (accumulate cons seq2 seq1))

Finally, length... We know that an empty list has a length of 0, and that if we start at 0 and add 1 for each element in the list we'll get the length of the list, so this gives us our initial value and tells us what op should do - increment the accumulated value by 1. This gives us the following implementation:

(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

Okay, let's take them for a spin:

> (define list1 (list 1 2 3 4))
> (define list2 (list 5 6 7 8 9))
> (map square list1)
(1 4 9 16)
> (map square list2)
(25 36 49 64 81)
> (append list1 list2)
(1 2 3 4 5 6 7 8 9)
> (append list2 list1)
(5 6 7 8 9 1 2 3 4)
> (length list1)
4
> (length list2)
5