SICP Exercise 2.33

Question

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

(define (map p sequence)
  (accumulate (λ (x y) ⟨??⟩)
              nil sequence))

(define (append seq1 seq2)
  (accumulate cons ⟨??⟩ ⟨??⟩))

(define (length sequence)
  (accumulate ⟨??⟩ 0 sequence))

Answer

To solve this, it helps to understand the actual way in which accumulate and specifically its op-parameter function.

The purpose of op is to take the next element of our sequence and perform some operation with it and the results of its previous calls. For example, in the case of map, op should take the next element, perform some operation p on it, and then add it to the list of the already p’d elements of the sequence (this list is the actual accumulator, so called because it accumulates results with every single iteration).

Therefore, op must always take two parameters: x, which is the car of our current sequence (moves one element forward on each iteration) and the element to be worked on, and y, the accumulator, which stores the results of all previous iterations within it. So here is the code:

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

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

(define (length sequence)
  (accumulate (λ (x y) (inc y)) 0 sequence))

Let’s test it:

(map square (list 1 2 3 4))
(append (list 1 2) (list 3 4))
(length (list 1 2 3 4 5))

Results:

(1 4 9 16)
(1 2 3 4)
5