Why is cons necessary to prevent infinite recursion

Question

When defining an infinite sequence, I noticed that cons is necessary to avoid infinite recursion. However, what I don't understand is why. Here is the code in question:

(defn even-numbers
  ([] (even-numbers 0))
  ([n] (cons n (lazy-seq (even-numbers (+ 2 n))))))

(take 10 (even-numbers))
;; (0 2 4 6 8 10 12 14 16 18)

This works great; but since I love to question things, I began to wonder why the cons was needed (other than to include 0). After all, the lazy-seq function creates a lazy-seq. Which means, the rest of the values should not be calculated until called (or chunked). So, I tried it.

(defn even-numbers-v2
  ([] (even-numbers-v2 0))
  ([n] (lazy-seq (even-numbers-v2 (+ 2 n)))))

(take 10 (even-numbers-v2))
;; Infinite loooooooooop

So, now I know that cons is necessary, but I'd like to know why cons is necessary to cause lazy evaluation of a supposedly lazy sequence

When trying to print the first of 10 elements from take 10, the lazy-seq thunk is called. It yields only another lazy-seq thunk which is also called. It yields only another lazy-seq thunk... If instead these were yielding an element and optionally another lazy-seq thunk (or an [empty] seq), then eventually this would stop once 10 were found of the sequence terminated. — A. Webb
In an answer to another question I tried to lay out how lazy seqs work. It might (or might not) be instructive. — A. Webb
See Rich Hickey's (June 2020) explanation of lazy-seq on page ten of "A History of Clojure". — Aaron Bell

Michał Marczyk Michał Marczyk · Accepted Answer · 2016-03-12T03:18:37

Lazy seqs are a way to defer computation of actual seq elements, but those elements do need to be computed eventually. That doesn't actually have to involve cons – for example clojure.core/concat uses "chunked conses" when processing chunked operands, and it's ok to wrap any concrete seq type whatsoever in lazy-seq – but some kind of non-lazy return after however many layers of lazy-seq is necessary if any seq processing is to take place. Otherwise there won't even be a first element to get to.

Put yourself in the position of a function that's been handed a lazy seq. The caller has told it, in effect, "here's this thing that's for all intents and purposes a seq, but I don't feel like computing the actual elements until later". Now our function needs some actual elements to operate, so it pokes and prods the seq to try and get it to produce some elements… and then what?

If peeling off some lazy-seq layers eventually produces a Cons cell, a list, a seq over a vector or any other concrete seq-like thing with actual elements, then great, the function can read off an element from that and make progress.

But if the only result of peeling off those layers is that more layers are revealed, and it's lazy-seqs all the way down, well… There are no elements to be found. And since in principle there is no way to determine whether by peeling off sufficiently many layers some elements could eventually be produced (cf. the halting problem), the function consuming an unrealizable lazy seq of this sort has in general no choice but to continue looping forever.

To take another angle, let's consider your even-numbers-v2 function. It takes an argument and returns a lazy-seq object wrapping a further call to itself. Now, the original argument it receives (n) is used to compute the argument to the recursive call ((+ 2 n)), but otherwise isn't placed in any data structure or otherwise conveyed to the caller, so there is no reason why it would occur as an element of the resulting seq. All the caller sees is that the function has produced a lazy seq object and it has no choice but to unwrap that in search for an actual element of the sequence; and of course then the situation repeats itself (not strictly forever in this case, but only because + will eventually complain about arithmetic overflow when dealing with longs).

Why is cons necessary to prevent infinite recursion

1 Answers