Thursday, 12 December 2013

The riddle of loop recur in Clojure

When writing programs with loop / recur, its not always clear to me how to arrive at a solution from first principles. Initially loop / recur seems like a bit of a mystery.

Consider the problem of adding up numbers from 1. E.g. The base case is 0.

[0]       -> 0
[1]       -> 1
[1 2]     -> 3
[1 2 3]   -> 6
[1 2 3 4] -> 10

The classical solution to the problem might have a function with 2 arities (1 and 3 arguments in this case). It might be invoked as (add-up 3) with an expected answer of 6. This invokes the first arity: (add-up 3 0 0), subsequent recursions will then invoke via the 2nd arity.

(defn add-up
  ([limit] (add-up limit 0 0 ))
  ([limit current sum]
    (if (< limit current)
      sum
      (add-up limit (+ 1 current) (+ current sum)))))

The problem with the above function is that it could blow the stack because Clojure is not naturally tail recursive. It must be told to be tail recursive by means of recur. Refactor it to use recur in the tail call position:

(defn add-up
  ([limit] (add-up limit 0 0 ))
  ([limit current sum]
    (if (< limit current)
      sum
      (recur limit (+ 1 current) (+ current sum)))))

It works now, and will not blow the stack but it's not idiomatic. Refactor again by removing the arities, replace the 2nd arity call by loop with with the function argument no longer passed in. The two other arguments, which had previously been initialised in the first arity call are now initialised at the loop

(defn add-up
  [limit]
  (loop [current 0 sum 0]
    (if (< limit current)
      sum
      (recur (+ 1 current) (+ current sum)))))

This is now idiomatic Clojure. Testing:

user=> (add-up 0)
0
user=> (add-up 4)
10
user=> (add-up 1000000)
500000500000

No comments: