JoT's Jottings

2011-09-27

SICP Exercise 2.21: Square Maps

The procedure square-list takes a list of numbers as argument and returns a list of the squares of those numbers.

> (square-list (list 1 2 3 4))
(1 4 9 16)

Here are two different definitions of square-list. Complete both of them by filling in the missing expressions:

(define (square-list items)
  (if (null? items)
      nil
      (cons <??> <??>)))
(define (square-list items)
  (map <??> <??>))

We're given two skeleton procedures here. The first procedure is similar to the recursive definition of scale-list in the Mapping over lists section of the book and is obviously the basis for a recursive procedure, while the second is analogous to the map-based definition of scale-list. The difference between scale-list and square-list is simply that the former scales each element of the list by some factor while the latter squares each element of the list. So our square-list implementations will bear an uncanny resemblance to scale-list, with just the scaling replaced with squaring.

Assuming we've got square defined as before:

(define (square x) (* x x))

...then we can produce the recursive implementation as follows:

(define (square-list items)
  (if (null? items)
      nil
      (cons (square (car items)) (square-list (cdr items)))))

...which produces the results:

> (square-list (list 1 2 3 4 5 6 7 8 9 10))
(1 4 9 16 25 36 49 64 81 100)

When it comes to the map-based version, we don't need to define a lambda-procedure as was necessary for scale-list, as we already have a procedure defined that provides the functionality we require: square. So we can define the map-based version as follows:

(define (square-list items)
  (map square items))

Of course this gives exactly the same results:

> (square-list (list 1 2 3 4 5 6 7 8 9 10))
(1 4 9 16 25 36 49 64 81 100)

SICP Exercise 2.20: Parity Lists

The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter's value will be a list of any remaining arguments. For instance, given the definition

(define (f x y . z) <body>)

the procedure f can be called with two or more arguments. If we evaluate

(f 1 2 3 4 5 6)

then in the body of f, x will be 1, y will be 2, and z will be the list (3 4 5 6). Given the definition

(define (g . w) <body>)

the procedure g can be called with zero or more arguments. If we evaluate

(g 1 2 3 4 5 6)

then in the body of g, w will be the list (1 2 3 4 5 6).

Use this notation to write a procedure same-parity that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument. For example,

> (same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
> (same-parity 2 3 4 5 6 7)
(2 4 6)

Okay, so if we our definition of same-parity takes the following form:

(define (same-parity i . l) <body>)

...then this allows us to implement a procedure in the following manner:

Figure out whether i is even or odd.
Recurse through l and filter it to those elements with the same parity as i.
Finally, use cons to prepend i onto the head of the filtered list.

The second step here is the most complex. We can implement this as an internal recursive procedure that takes an indication of the parity to filter for and the remainder of the list to filter and has three cases:

If the list is empty then return an empty list.
If the head of the list has the parity we're looking for then we cons the head onto the results of filtering the tail of the list via a recursive call and return that.
Otherwise we want to filter the head of the list, so we just return the results of filtering the tail of the list via a recursive call and return that.

Here's my implementation:

(define (same-parity i . l)
  (define (filter-list filter-to-even ll)
    (cond ((null? ll) nil)
          ((equal? filter-to-even (even? (car ll)))
              (cons (car ll) (filter-list filter-to-even (cdr ll))))
          (else (filter-list filter-to-even (cdr ll)))))
  (cons i (filter-list (even? i) l)))

...and here's the results of running it:

> (same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
> (same-parity 2 3 4 5 6 7)
(2 4 6)

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.

Pages

2011-09-27

SICP Exercise 2.21: Square Maps

SICP Exercise 2.20: Parity Lists

SICP Exercise 2.19: Counting UK Change