haskell - Why is my intuition about self referential lazy sequences wrong? -

haskell - Why is my intuition about self referential lazy sequences wrong? -

in haskell can write self referential sequence, in ghci, so:

λ> allow x = 1:map (+1) x λ> take 5 x

which produces:

[1,2,3,4,5]

however intuition on lazy evaluation says should happen during expansion

let x = 1:map (+1) x 1:2:map (+1) x 1:2:map (+1) [1, 2] <-- substitution 1:2:2:3:map (+1) x 1:2:2:3:map (+1) [1, 2, 2, 3] <-- substitution 1:2:2:3:2:3:3:4:map (+1) x ...

this not what's happening. can see pattern in right answer. simply moving 1 element in list @ time downwards infinite stream. pattern recognize , can apply in code. not line mental model of lazy evaluation. feels bit "magic". intuition wrong?

remember substitute definition. whenever expand x, should substitute 1 : map (+1) x, not "current value" (whatever means).

i'll reproduce jefffrey's idea, due respect laziness.

x = 1 : map (+1) x take 5 x = take 5 (1 : map (+1) x) -- x = 1 : take 4 (map (+1) x) -- take = 1 : take 4 (map (+1) (1 : map (+1) x) -- x = 1 : take 4 (2 : map (+1) (map (+1) x)) -- map , (+) = 1 : 2 : take 3 (map (+1) (map (+1) x)) -- take = 1 : 2 : take 3 (map (+1) (map (+1) (1 : map (+1) x))) -- x = 1 : 2 : take 3 (map (+1) (2 : map (+1) (map (+1) x))) -- map , (+) = 1 : 2 : take 3 (3 : map (+1) (map (+1) (map (+1) x))) -- map , (+) = 1 : 2 : 3 : take 2 (map (+1) (map (+1) (map (+1) x))) -- take

and on.

exercise finish evaluation in style (it's quite informative).

notice how starting build chain of maps list grows. if print x, see output start slow downwards after while; why. there more efficient way, left exercise (and [1..] cheating :-).

n.b. still little less lazy happen. map (+1) (1 : ...) evaluates (1+1) : map (+1) ..., , add-on happen when number observed, either printing or e.g. comparing it.

will ness identified error in post; see comments , answer.

haskell lazy-evaluation