SICP Exercise 2.8: Interval Subtraction

Using reasoning analogous to Alyssa's, describe how the difference of two intervals may be computed. Define a corresponding subtraction procedure, called sub-interval.

Well, let's check Alyssa's reasoning for her procedure add-interval: "the minimum value the sum could be is the sum of the two lower bounds and the maximum value it could be is the sum of the two upper bounds". Let's see if we can provide a bit more in-depth analysis for subtracting intervals.

The result of subtracting one interval from another should be the interval consisting of the minimum and maximum values out of the four values produced by subtracting each of the bounds of the second interval from each of the bounds of the first interval. To produce the minimum value we want to start with the lowest value possible and subtract the largest value possible from it. I.e. subtract the upper bound of the second interval from the lower bound of the first interval. To produce the maximum value we do the converse of this - we want to start with the largest value possible and subtract the least from it. I.e. subtract the lower bound of the second interval from the upper bound of the first interval.

We can show this via example. Suppose we have an interval with the bounds [5,7] and we want to subtract the interval [2,4] from it. What happens when we subtract each of the bounds of the second interval from each of the bounds of the first one:

First Interval Bound	Second Interval Bound	Subtracted Value
5	2	3
5	4	1
7	2	5
7	4	3

As you can see the minimum value is produced by subtracting the upper bound of the second interval from the lower bound of the first interval and the maximum value is produced by subtracting the lower bound of the second interval from the upper bound of the first interval.

Here's an implementation that encapsulates this functionality:

(define (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                 (- (upper-bound x) (lower-bound y))))

Let's try it out:

> (sub-interval (make-interval 5 7) (make-interval 2 4))
'(1 . 5)
>  (sub-interval (make-interval 4 6) (make-interval 3 10))
'(-6 . 3)