SICP Exercise 2.36: n-way Accumulation

The procedure accumulate-n is similar to accumulate except that it takes as its third argument a sequence of sequences, which are all assumed to have the same number of elements. It applies the designated accumulation procedure to combine all the first elements of the sequences, all the second elements of the sequences, and so on, and returns a sequence of the results. For instance, if s is a sequence containing four sequences, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), then the value of (accumulate-n + 0 s) should be the sequence (22 26 30). Fill in the missing expressions in the following definition of accumulate-n:

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init <??>)
            (accumulate-n op init <??>))))

What we need to do here is to get the sequence containing all the first elements of the sequences in seqs and apply accumulate to those, and then cons that result onto the head of the list produced by applying accumulate-n to the sequence of sequences where each sub-sequence is the tail of the corresponding sequence in seqs. We're given most of this in the template procedure. It applies accumulate to some sequence and then cons it onto the sequence returned by applying accumulate-n onto a sequence of sequences. All we need to do is to:

• Get the sequence containing all the first elements of the sequences in seqs, so we can pass this to accumulate.
• Get the sequence of sequences where each sub-sequence is the tail of the corresponding sequence in seqs, so we can pass this to the recursive call to accumulate-n.

We can achieve both of these via map. We know that we can extract the first element of a sequence by using car, so mapping seqs with the operation car will give us the sequence containing the first element of each sequence in seqs. Similarly, we know that we can extract the tail of a sequence by using cdr, so mapping seqs with the operation cdr will give us the sequence of sequences containing the tails of each sequence in seqs.

So here's the completed procedure:

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

And here it is in action:

> (define s (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
> (accumulate-n + 0 s)
(22 26 30)
> (accumulate-n * 1 s)
(280 880 1944)