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)

SICP Exercise 2.16: IEEE Interval Standard – P1788

Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.)

In exercise 2.14, the different arithmetic operations have different effects upon the center values and tolerances of the produced intervals. We also saw that our system as implemented has no concept of identity. I.e. A/A ≠ 1 ± 0%. These issues mean that we cannot apply standard algebraic transformations to a formula and expect it to produce an interval with the same bounds afterwards. This was demonstrated quite clearly in exercise 2.15, where two algebraically equivalent formulae were shown to produce intervals with different bounds.

In general we can state that the issue is that the more interval-arithmetic operations we perform during a calculation, the wider the resulting interval will be.

As to devising an interval-arithmetic package that does not have this shortcoming... As the authors state, "This problem is very difficult". So much so that the IEEE started working on a standard for interval arithmetic back in 2008... and they're still going as I write this. So, yes, it's very difficult - and certainly beyond the scope of our current exposure to Scheme at this point in the book!