How Are Lazy Sequences Implemented in Clojure?

Question

I like Clojure. One thing that bothers me about the language is that I don't know how lazy sequences are implemented, or how they work.

I know that lazy sequences only evaluate the items in the sequence that are asked for. How does it do this?

• What makes lazy sequences so efficient that they don't consume much stack?
• How come you can wrap recursive calls in a lazy sequence and no longer get a stack over flow for large computations?
• What resources do lazy sequences consume to do what it does?
• In what scenarios are lazy sequences inefficient?
• In what scenarios are lazy sequences most efficient?

Answer 1

Let's do this.

• I know that lazy sequences only evaluate the items in the sequence that are asked for, how does it do this?

Lazy sequences (henceforth LS, because I am a LP, or Lazy Person) are composed of parts. The head, or the part(s, as really 32 elements are evaluated at a time, as of Clojure 1.1, and I think 1.2) of the sequence that have been evaluated, is followed by something called a thunk, which is basically a chunk of information (think of it as the rest of the your function that creates the sequence, unevaluated) waiting to be called. When it is called, the thunk evaluates however much is asked of it, and a new thunk is created, with context as necessary (how much has been called already, so it can resume from where it was before).

So you (take 10 (whole-numbers)) – assume whole-numbers is a lazy sequence of whole numbers. That means you're forcing evaluation of thunks 10 times (though internally this may be a little difference depending on optimizations.

• What makes lazy sequences so efficient that they don't consume much stack?

This becomes clearer once you read the previous answer (I hope): unless you call for something in particular, nothing is evaluated. When you call for something, each element of the sequence can be evaluated individually, then discarded.

If the sequence is not lazy, oftentimes it is holding onto its head, which consumes heap space. If it is lazy, it is computed, then discarded, as it is not required for subsequent computations.

• How come you can wrap recursive calls in a lazy sequence and no longer get a stack over flow for large computations?

See the previous answer and consider: the lazy-seq macro (from the documentation) will

will invoke the body only the first time seq is called, and will cache the result and return it on all subsequent seq calls. 

Check out the filter function for a cool LS that uses recursion:

(defn filter   "Returns a lazy sequence of the items in coll for which   (pred item) returns true. pred must be free of side-effects."   [pred coll]   (let [step (fn [p c]                  (when-let [s (seq c)]                    (if (p (first s))                      (cons (first s) (filter p (rest s)))                      (recur p (rest s)))))]     (lazy-seq (step pred coll)))) 

• What resources do lazy sequences consume to do what it does?

I'm not quite sure what you're asking here. LSs require memory and CPU cycles. They just don't keep banging the stack, and filling it up with results of the computations required to get the sequence elements.

• In what scenarios are lazy sequences inefficient?

When you're using small seqs that are fast to compute and won't be used much, making it an LS is inefficient because it requires another couple chars to create.

In all seriousness, unless you're trying to make something extremely performant, LSs are the way to go.

• In what scenarios are lazy sequences most efficient?

When you're dealing with seqs that are huge and you're only using bits and pieces of them, that is when you get the most benefit from using them.

Really, it's pretty much always better to use LSs over non-LSs, in terms of convenience, ease of understanding (once you get the hang of them) and reasoning about your code, and speed.