Funky haskell lazy list implicit recursion -

in haskell, can build infinite lists due laziness:

prelude> let g = 4 : g prelude> g !! 0 4 prelude> take 10 g [4,4,4,4,4,4,4,4,4,4] 

now, goes on when try construct list this?

prelude> let f = f !! 10 : f prelude> f !! 0 interrupted. prelude> take 10 f [interrupted. prelude> 

the interrupted.s me hitting ctrl+c after waiting few seconds. seems go infinite loop, why case?

---

explanation non-haskellers:

the : operator prepend:

prelude> 4 : [1, 2, 3] [4,1,2,3] 

this line:

prelude> let g = 4 : g 

says "let g list constructed prepending 4 list g". when ask first element, 4 returned, it's there. when ask second element, looks element after 4. element first element of list g, calculated (4), 4 returned. next element second element of g, again calculated, etc...

!! indexing list, means element @ index 0 g:

prelude> g !! 0 4 

but when this:

prelude> let f = f !! 10 : f 

something breaks, because compute first element of f need 11th element, doesn't exist yet? expect exception, though, not infinite loop...

in case, picture may tell thousand words.

first, remember how cons (the (:) list constructor) works. it's pair of 2 things: element, , reference list tail (which either cons, or []).

as should know, when [1, 2, 3], it's shortcut (1:(2:(3:[]))) or 1:2:3:[]. if visualize each cons pair box 2 slots, expression like:

┌───┬──┐  ┌───┬──┐  ┌───┬──┐  ┌────┐ │ 1 │ ─┼─>│ 2 │ ─┼─>│ 3 │ ─┼─>│ [] │ └───┴──┘  └───┴──┘  └───┴──┘  └────┘ 

one loop

when g = 4 : g, you're not building "infinite" list, you're building circular list: g defined cons tail reference points g itself:

┌──────────┐ │ ┌───┬──┐ │ └>│ 4 │ ─┼─┘   └───┴──┘ 

this has nothing laziness, , self-reference: example, can same thing in (eager) common lisp using syntax '#1=(4 . #1#) (where #1 g).

whether g !! 0, or g !! 1000000000000, g never grows: (!!) runs around loop in-place, many times told to, until exhausts , returns element, 4.

two loops

when f = (f !! 10) : f, same thing happens—except now, element slot contains different expression 4:

┌──────────┐ │ ┌───┬──┐ │ └>│ ╷ │ ─┼─┘   └─┼─┴──┘     │     │ ┌───────────┐     └>│ (f !! 10) │       └───────────┘ 

crucially, sub-expression also refers f, tail does:

 ┌──────────┐  │ ┌───┬──┐ │ ┌┴>│ ╷ │ ─┼─┘ │  └─┼─┴──┘ │    │ │    │ ┌───────────┐ │    └>│ (f !! 10) │ │      └──┼────────┘ └─────────┘ 

so, when ask f !! n, (!!) first run around top loop n times, return element, did g. however, instead of escaping loop, (f !! 10) re-enters it, , process repeats itself: looping 10 times around top, once around bottom, , back.