lazy-seq StackOverflowError

2
votes

Why does this work

(def fibs (cons 0 (cons 1 (lazy-seq (map + fibs (rest fibs))))))
(take 10 fibs)

while this other

(def fibs (lazy-seq (cons 0 (cons 1 (map + fibs (rest fibs))))))
(take 10 fibs)

generate a StackOverflowError?

1
clojurelazy-sequences
What are you trying to achieve with lazy-seq? It seems to run fine if you just remove it. – jmargolisvt
@jmargolisvt On my repl (clojure 1.6) the code ` (def fibs (cons 0 (cons 1 (map + fibs (rest fibs)))))` does not work. Lazy-seq is necessary I think, because it delays the computation of the stream, otherwise it won't work defining fibs in terms of fibs itself – Matteo

1 Answers

4
votes

Let's first note that it also works with one cons outside:

(def fibs (cons 0 (lazy-seq (cons 1 (map + fibs (rest fibs))))))

Let's also establish that lazy-seq is a macro (obviously, since it doesn't evaluate the arguments) and puts the body (the argument(s) to lazy-seq) into a function.

Now, if you "request" an element from that sequence that function will be called once and subsequent calls will return the cached value.

Obviously, only once that function returns something you have a value available. Now, what's happening in our bad case:

Imagine clojure is in the middle of evaluating the function for the very first time. The first thing it needs is +, fibs and (rest fibs) in order to pass this to cons. Now clojure will see that fibs is a lazy sequence and invoke it! This is because you're currently in your first invocation and haven't returned. This is causing an infinite recursion.

The fix is easy: Make sure there is a realized element in the beginning of the list so that the two expressions, fibs and (rest fibs) can return something. In particular, taking the rest of (cons 1 whatever) will return whatever without realizing a single element (important since otherwise we'd have the same problem again).