Quirksand

SICP

SICP 2.1.1 Solutions

December 30, 2013 11:13

Ex 2.1.

In order to cleanly handle negative values in rational numbers, all possible cases in which negative values may appear must be considered. Those cases are:

  • Both numerator and denominator are positive.
  • The numerator is negative, the denominator is positive.
  • The denominator is negative, and the numerator is positive.
  • Both numerator and denominator are negative.

Each of these cases has a test value associated with it. There is also the special case of 0, which must not be treated as if it were positive or negative. Special cases like this can occasionally be difficult to remember, although in mathematical functions 0 is usually an important one so it’s worthwhile to always check what happens around 0.

The first two cases described above are acceptable as-is. The third should be converted into the second (a negative value with only the numerator negative) by convention. The fourth is a positive value, so it needs to be converted into the format of the first.

The first version of the function will use a cond statement to implement this pattern directly. For the first two cases, no change is made. (Here n and d stand for the numerator and denominator respectively, and the gcd reduction is dispensed with for clarity’s sake):

(cond 
	((and (> n 0) (> d 0)) (cons n d))
	((and (< n 0) (> d 0)) (cons n d))
	((and (> n 0) (< d 0)) (cons (- n) (- d)))  
	((and (< n 0) (< d 0)) (cons (- n) (- d)))
	(else (cons 0 d))
	)

Now this will work just fine, but it’s a bit more lengthy than it needs to be. The observation can be made almost immediately that there are only two real outcomes: Either the signs stay the same, or they both change. We combine the cases and discover that the only test we need is on the denominator. This leads to the more concise form:

(if (< d 0) 
    (cons ((- n) (- d))) 
    (cons n d)
    )

Checking (not just by thinking about it, but by using the actual test value) we see that values with 0 in the numerator will work fine with this as well. Values with 0 in the denominator are implicitly covered in the least terms reduction (in that they raise an error). I think it is worthwhile to at least consider the sorts of out-of-bounds behavior, but when it’s something that isn’t part of the system presented in the text, it’s not critical to do extra work to handle it ‘properly’.

Solutions 2.1.1