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)

SICP Exercise 2.35: Counting Leaves Again

Redefine count-leaves from section 2.2.2 as an accumulation:

(define (count-leaves t)
  (accumulate <??> <??> (map <??> <??>)))

In the "Sequence operations" section the authors define the procedure enumerate-tree which flattens a tree into a list that contains only the leaf nodes of the tree. We can use this to simplify our job here - we're only interested in the leaf nodes and this saves us the complexity of writing our own tree-traversal. The length of this list is equal to the number of leaf nodes in the tree...

However, the procedure template we're given above doesn't allow us to do that - we have to map across a list and then accumulate in some way across the result of the mapped list. So what mapping should we use, and what accumulation?

Well, when we defined length in terms of accumulate in exercise 2.33, we started with an initial value of 0 and incremented this by 1 for each element in the tree. We could achieve the same effect by using + as our op for accumulate, 0 as the initial value, and pass it a sequence that's a list with the same number of elements as there are leaf nodes, but with each element having the value 1... And we can produce such a sequence by mapping each element from the list returned by enumerate-tree to 1.

Here's my implementation:

(define (count-leaves t)
  (accumulate + 0 (map (lambda (x) 1) (enumerate-tree t))))

...and in practice:

> (define x (cons (list 1 2) (list 3 4)))
> (define y (list 1 (list 2 3) (cons (list 4 5) (list 6 7))))
> (count-leaves x)
4
> (count-leaves (cons x x))
8
> (count-leaves y)
7
> (count-leaves (list x y))
11

SICP Exercise 2.34: Horner's Rule

Evaluating a polynomial in x at a given value of x can be formulated as an accumulation. We evaluate the polynomial

a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀

using a well-known algorithm called Horner's rule, which structures the computation as

( … (a_nx + a_n-1)x + … + a₁)x + a₀

In other words, we start with a_n, multiply by x, add a_n-1, multiply by x, and so on, until we reach a₀. Fill in the following template to produce a procedure that evaluates a polynomial using Horner's rule. Assume that the coefficients of the polynomial are arranged in a sequence, from a₀ through a_n.

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) <??>)
              0
              coefficient-sequence))

For example, to compute 1 + 3x + 5x³ + x⁵ at x = 2 you would evaluate

(horner-eval 2 (list 1 3 0 5 0 1))

Remembering that accumulate is effectively equivalent to starting with some initial value, then going through the supplied list backwards from the last item to the first, applying op to each item and the accumulated result so far, we're actually going to start at the n^th coefficient and work backwards towards the 0^th one. This allows use to define the recursive relationship here as: multiply the accumulated result so far by x and then add the next coefficient.

Let's put this into code:

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))

And give it a test:

> (horner-eval 2 (list 1 3 0 5 0 1))
79
> (horner-eval 4 (list 3 2 1))
27