Going Functional

17th Jan 2009 | Tags: clojure sicp

So, some Hacker News users recently decided that it’d be a good idea to work through the SICP together and make a kind of book club out of the deal over irc.

When I heard of it, I thought it’d be a good excuse to work through the text myself (since it was just sitting on my bookshelf), and also stretch my brain a bit more teaching myself Clojure. I’m almost done the reading and exercises for section 1.1, and I’m already finding it a valuable exercise.

The third exercise asks us to “define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.” At either extremity are two solutions. The straightforward solution a new programmer can generate based solely on the first 20 pages of the text looks something like this:

1
2
3
4
(defn sum-largest-squares [a b c]
  (cond (and (< a b) (< a c)) (+ (* b b) (* c c))
        (and (< b a) (< b c)) (+ (* a a) (* c c))
        (and (< c a) (< c b)) (+ (* a a) (* b b))))

Some tests to prove correctness, returning 2^2 + 3^2, or 13, are:

1
2
3
(sum-largest-squares 1 2 3)
(sum-largest-squares 2 3 1)
(sum-largest-squares 3 1 2)

An interesting (and enlightening) exercise is to take our naive function, and just start randomly refactoring, and see where it takes us. One step at a time, making sure we are always passing our handful of test cases. The goal is to decompose and abstract the function into more manageable pieces, with less repetition. To start:

1
2
3
4
(defn sum-largest-squares [a b c]
  (cond (and (< a b) (< a c)) (+ (square b) (square c))
        (and (< b a) (< b c)) (+ (square a) (square c))
        (and (< c a) (< c b)) (+ (square a) (square b))))

The square function is trivially pulling out (* x x), and conveniently is already present in Clojure.

Second step is to pull out the three conditional clauses into sum-of-squares:

1
2
3
4
5
6
7
(defn sum-of-squares [a b]
  (+ (square a) (square b)))

(defn sum-largest-squares [a b c]
  (cond (and (< a b) (< a c)) (sum-of-squares b c)
        (and (< b a) (< b c)) (sum-of-squares a c)
        (and (< c a) (< c b)) (sum-of-squares a b)))

Next, we can probably abstract the conditionals themselves, since what we’re looking for is the smallest of three elements (min is also provided by clojure):

1
2
3
4
(defn sum-largest-squares [a b c]
  (cond (= a (min a b c)) (sum-of-squares b c)
        (= b (min a b c)) (sum-of-squares a c)
        (= c (min a b c)) (sum-of-squares a b)))

Now, we’ve got a much more parallel structure here, so we should be able to collapse the conditional, and process the values first.

I’ll stop here, but there are a few different ways to get started with the next step - most involve transitioning our three arguments into a list at some point. I’ve found it instructive to play around with the different ways of decomposing the problem (including a few side steps along the way to the route I’ve followed above). I’m thinking that as I continue with the SICP exercies, I’ll try and make a habit of not stopping with the first solution that springs out of my text editor, but to try and explore the structure of the code through refactoring.

Also, while I never managed to figure out refactoring steps that would produce it, I think the most straightforward functional solution (rather than the semi-iterative solution we started with above) winds up being this - it has a certain elegance to it, no?

1
2
(defn sum-largest-squares [a b c]
  (apply + (map square (rest (sort (list a b c))))))