Understanding the implementation of a lazy fibonacci implementation in Clojure

Question

I am trying to understand the execution of the following code:

(def fibs (concat (lazy-seq [0 1]) (lazy-seq (map + fibs (rest fibs))))) 

This is what I expect execution to look like

 [0 1 : (map + [0 1] [1]) => 1 [0 1 1 : (map + [0 1 1] [1 1]) => 1 2 [0 1 1 1 2 : (map + [0 1 1 2] [1 1 2]) => 1 2 3 [0 1 1 1 2 1 2 3 : (map + [0 1 1 2 3] [1 1 2 3]) => 1 2 3 5 [0 1 1 1 2 1 2 3 1 2 3 5 .... 

This is clearly incorrect, as the result is incorrect. The only execution I could come up with produced the correct result:

 [0 1 : (map + [0 1] [1]) => 1 [0 1 1 : (map + [1 1] [1]) => 2 [0 1 1 2 : (map + [1 2] [2]) => 3 [0 1 1 2 3 : (map + [2 3] [3]) => 5 [0 1 1 2 3 5 .... 

Is this the correct "representation" of the state of the head and tail at runtime? If so, why (rest fibs) returns one element? Is it because of a recursive call like (rest (rest (rest (rest [1 1 2 3])))?

Answer 1

Fibs (0 1 ...) (due to (concat [0 1] ... ) at the beginning). (rest fibs) - (1 ...) . Then (map + fibs (rest fibs)) is

 ((+ 0 1) ...) => (1 ...) 

So fibs (0 1 1 ...) . Since we got the following element, we can calculate another one:

 (1 (+ 1 1) ...) => (1 2 ...) 

And it goes on ...

 (1 2 (+ 1 2) ...) 

Think of Phoebe as if it were already there, and the state (map + fibs (rest fibs) as moving around a list of existing ones (which is fine because it finishes computing everything we need along the way).

It can also help just write down two sequences:

  (0 1 1 2 3 5 ...) +(1 1 2 3 5 ...) =(1 2 3 5 8 ...) 

(I would draw arrows here to indicate what we already got and where the result is, but I can't do it so well).