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

SICP Exercise 2.32: Power Sets

We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map <??> rest)))))

We have a recursive procedure here:

• If we have the empty set then the complete set of subsets is the empty set.
• Otherwise, in order to build the complete set of subsets for the set we:
  1. First build the complete set of subsets for the set with its first item removed.
  2. Then we map this list of subsets in some way.
  3. Finally we join these two sets together (via append) to produce the complete set of subsets.

So what's the mapping step? Well, we can define the complete set of subsets of any non-empty set s as being the union of two sets:

1. The set of all subsets of s that do not include the head of s.
2. The set of all subsets of s that do include the head of s.

Now if we have a complete implementation of subsets, then the local variable rest will contain the first of these sets. We can produce the second of these sets by noting that the first and second sets have the same number of elements, and that each element in the second set can be produced by taking an element from the first set and adding the head of s to it. Note that this is a pretty common algorithm for producing power sets, which is what this procedure is meant to be doing.

Okay, so here's how we complete the procedure:

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (x) (cons (car s) x)) rest)))))

And let's give it a spin:

> (subsets (list 1 2))
'(() (2) (1) (1 2))
> (subsets (list 1 2 3))
'(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
> (subsets (list 1 2 3 4))
'(() (4) (3) (3 4) (2) (2 4) (2 3) (2 3 4) (1) (1 4) (1 3) (1 3 4) (1 2) (1 2 4)
 (1 2 3) (1 2 3 4))

The discussion above also indicates why this is a correct approach. Let's go a step further and give a proof by induction for the algorithm.

First we show that the base case is correct: that the power set of the empty set contains only one set, the empty set:

  (subsets nil)
= (if (null? nil)
      (list nil)
      (let ((rest (subsets (cdr nil))))
        (append rest (map (lambda (x) (cons (car nil) x)) rest)))))
= (if #t
      (list nil)
      (let ((rest (subsets (cdr nil))))
        (append rest (map (lambda (x) (cons (car nil) x)) rest)))))
= (list nil)
= (())

Before we move onto the inductive step, let's make the observation that, given that rest is the set of all subsets of s that do not include the head of s, then (map (lambda (x) (cons (car s) x)) rest) will append the head of s onto each of these subsets and so produce the set of all subsets of s that do include the head of s.

Now onto the inductive step. Given the assumption that for any arbitrary set s, (subsets s) correctly produces the power set of s, we need to prove that (subsets (cons h s)) produces the power set of (cons h s):

  (subsets (cons h s))
= (if (null? (cons h s))
      (list nil)
      (let ((rest (subsets (cdr (cons h s)))))
        (append rest (map (lambda (x) (cons (car (cons h s)) x)) rest)))))
= (if #f
      (list nil)
      (let ((rest (subsets (cdr (cons h s)))))
        (append rest (map (lambda (x) (cons (car (cons h s)) x)) rest)))))
= (let ((rest (subsets (cdr (cons h s)))))
    (append rest (map (lambda (x) (cons (car (cons h s)) x)) rest)))
= (let ((rest (subsets s)))
    (append rest (map (lambda (x) (cons (car (cons h s)) x)) rest)))
= (append (subsets s) (map (lambda (x) (cons h x)) (subsets s)))

Now we know that (subsets s) is the set of all subsets of (cons h s) that do not include h. We also know from our previous observation that (map (lambda (x) (cons h x)) (subsets s)) produces the set of all subsets of (cons h s) that do include h. Therefore appending these two sets together produces the set of all subsets of (cons h s).