Proof By Example

Programming blog by Mark Feeney

Clojure Laziness Review

Quick notes on Clojure lazy sequences since I have confused myself on this a few times over the years, and just did so again.

The working example will be a hack implementation of range.

(defn range-so
  "Will blow stack."
  ([end] (range-so 0 end))
  ([start end]
  (when (< start end)
    (cons start (range-so (inc start) end)))))

;; (range-so 10000)
;; StackOverflowError   clojure.lang.Numbers$LongOps.inc (Numbers.java:529)

range-so is the naive recursive implementation that consumes stack and is not useful for ranges with more than a few thousand entries. It’s also eager, so (take 2 (range-so 1000)) will calculate the full item range before returning just the first two elements.

Clojure provides recur for non-stack-consuming “recursion”, so that will solve the StackOverflowError:

(defn range-recur
  "Won't blow stack due to recur."
  ([end] (range-recur [] 0 end))
  ([start end] (range-recur [] start end))
  ([acc start end]
   (if (< start end)
     (recur (conj acc start) (inc start) end)
     acc)))

;; (range-recur 10000)
;; [0 1 .. 9998 9999]

range-recur is also eager, so again (take 2 (range-recur 1000) realizes the whole range before returning only the first two items.

To make this lazy the obvious tool is the lazy-seq macro. Often you can just wrap your seq-bearing expressions in lazy-seq and you’re set. One caveat: don’t blindly wrap code using recur with lazy-seq of you’ll get potentially surprising errors:

(defn range-lazy-busted
  "Won't compile."
  ([end] (range-recur [] 0 end))
  ([start end] (range-recur [] start end))
  ([acc start end]
   (lazy-seq
     (if (< start end)
       (recur (conj acc start) (inc start) end)
       acc))))

;; IllegalArgumentException: Mismatched argument count to recur, expected: 0 args, got: 3

The reason for this is obvious when you realize that lazy-seq is just a macro that wraps its contents in (new clojure.lang.LazySeq (fn* [] ...). The surrounding fn* is a recur target expecteing zero args, hence the error message. Also, when you realize you’re returning a LazySeq instance immediately, it should be clear that you don’t need recur since there is no recursion.

Here’s the fully lazy version:

(defn range-lazy
  "Won't blow the stack due to lazy-seq."
  ([end] (range-lazy 0 end))
  ([start end]
   (lazy-seq
     (when (< start end)
       (cons start (range-lazy (inc start) end))))))

;; (range-lazy 10000)
;; (0 1 .. 9998 9999)

tl;dr - Recursive-looking self-calls ok when wrapped in lazy-seq.