SICP Exercise 2.19: Counting UK Change

Consider the change-counting program of section 1.2.2. It would be nice to be able to easily change the currency used by the program, so that we could compute the number of ways to change a British pound, for example. As the program is written, the knowledge of the currency is distributed partly into the procedure first-denomination and partly into the procedure count-change (which knows that there are five kinds of U.S. coins). It would be nicer to be able to supply a list of coins to be used for making change.

We want to rewrite the procedure cc so that its second argument is a list of the values of the coins to use rather than an integer specifying which coins to use. We could then have lists that defined each kind of currency:

(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

We could then call cc as follows:

> (cc 100 us-coins)
292

To do this will require changing the program cc somewhat. It will still have the same form, but it will access its second argument differently, as follows:

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

Define the procedures first-denomination, except-first-denomination, and no-more? in terms of primitive operations on list structures. Does the order of the list coin-values affect the answer produced by cc? Why or why not?

The exercise already tells us the representation we're going to be using for denominations: lists of the denomination values. As a result, the procedures first-denomination, except-first-denomination, and no-more? are straightforward to define. first-denomination just needs to return the car of the list, except-first-denomination just needs to return the cdr of the list, and no-more? just needs to check to see if the list is empty:

(define (first-denomination coin-values)
  (car coin-values))

(define (except-first-denomination coin-values)
  (cdr coin-values))

(define (no-more? coin-values)
  (null? coin-values))

We can check this works as expected:

> (cc 100 us-coins)
292
> (cc 100 uk-coins)
104561

As for whether or not the order of the list coin-values affects the answer produced by cc, we can easily test this:

> (cc 100 (list 1 5 10 25 50))
292
> (cc 100 (list 5 25 50 10 1))
292

So no, it doesn't appear as if it does affect ordering. So why not? Well, looking at the algorithm we can see that each non-terminal call to cc sums the results of two (also potentially non-terminal) recursive calls:

• One of these finds the number of ways we can change amount using denominations other than the first one in the list of denominations. As a result, this counts all of the combinations for changing amount that do not use the first denomination.
• The other deducts the value of the first denomination in the list of denominations from amount and finds how many ways we can change that using any and all of the denominations in the list. As a result, this counts all of the combinations for changing amount that do use the first denomination.

In other words, these two recursive calls split the counting to cover two distinct sets of coin combinations which, when merged together, produces a set containing all valid combinations of denominations for changing amount. As a result the order of the denominations does not matter.

SICP Exercise 2.18: Reversing a List

Note: Neither of the interpreters I've been using support nil, but will quite happily accept () as an equivalent expression. If you're in the same situation you can get around this by using:

(define nil ())

Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order:

> (reverse (list 1 4 9 16 25))
(25 16 9 4 1)

The logical first thought here is to just recurse through the list, take each item in turn and add it to the end of the list produced by recursing through the remainder of the list. This however doesn't work. Here's an implementation of this broken version:

(define (broken-reverse l)
  (if (null? l)
      nil
      (cons (broken-reverse (cdr l)) (car l))))

And here's what happens when we run it:

> (broken-reverse (list 1 2 3 4))
((((() . 4) . 3) . 2) . 1)

As you can see what we're actually doing here is to build up a pair where the first element of the pair is the "paired-reversal" of the remainder of the list and the second element is the head of the list. Part of the problem here is that cons produces pairs, not lists. When we perform (cons (broken-reverse (cdr l)) (car l)) we're creating a pair in which the second item is a value, not a pair as it would be in a list. Changing cons to list doesn't help either:

(define (broken-reverse-2 l)
  (if (null? l)
      nil
      (list (broken-reverse-2 (cdr l)) (car l))))

...gives:

> (broken-reverse-2 (list 1 2 3 4))
((((() 4) 3) 2) 1)

We've got a list alright, but it's a two-element list in which the first element of the list is a recursive reversal of the remainder of the list (and so has a list for its first element) and the second element is the head of the list. To use this we'd need to flatten the list on completion.

An alternative approach would be to use append to produce the flattened list as we go:

(define (reverse l)
  (if (null? l)
      nil
      (append (reverse (cdr l)) (list (car l)))))

This produces the effect we want, but is less than efficient. For each element in the list we have to append the results of reversing the remainder of the list to the head of the list containing the current element. append is an Θ(n) operation, so this implementation of reverse will be Θ(n²).

No, we can do better than that, and we can do it with an iterative procedure. Iteratively we can state the problem of reversing the list as starting with two lists: the list we want to reverse and an empty list. We iterate through the first list and for each item in the first list we cons it onto the head of the second list. So for the first item in the first list we cons it onto an empty list, for the second item we cons it onto a list containing just the first item and so on. Here's my implementation:

(define (reverse l)
  (define (iter remaining result)
    (if (null? remaining)
        result
        (iter (cdr remaining) (cons (car remaining) result))))
  (iter l nil))

And here's a few tests:

> (reverse (list 1 2 3 4))
(4 3 2 1)
> (reverse (list 4 3 2 1))
(1 2 3 4)
> (reverse (list 1 4 9 16 25))
(25 16 9 4 1)

SICP Exercise 2.17: Last Pair

Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list:

> (last-pair (list 23 72 149 34))
(34)

We know that we can identify the last pair in a list by the cdr of the pair being nil, and returning this pair will give us the result we need. All we need to do is to walk through the list recursively, in a similar manner to the list operations defined in the book, and stop when we reach such a pair.

Here's my implementation:

(define (last-pair l)
  (let ((tail (cdr l)))
     (if (null? tail)
         l
         (last-pair tail))))

And here it is in action:

> (last-pair (list 23 72 149 34))
(34)
> (last-pair (list 1 2 3 4))
(4)
> (last-pair (list 4 3 2 1))
(1)