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

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