In Haskell, you can build infinite lists due to 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, what exactly goes on when I try to construct a list like this?
Prelude> let f = f !! 10 : f
Prelude> f !! 0
Interrupted.
Prelude> take 10 f
[Interrupted.
Prelude>
The Interrupted.s are me hitting CTRL+C after waiting a few seconds. It seems to go into an infinite loop, but why is that the case?
Explanation for non-Haskellers:
The : operator is prepend:
Prelude> 4 : [1, 2, 3]
[4,1,2,3]
This line:
Prelude> let g = 4 : g
says "let g be the list constructed by prepending 4 into the list g". When you ask for the first element, 4 is returned, as it's already there. When you ask for the second element, it looks for the element after 4. That element would be the first element of the list g, which we just calculated (4), so 4 is returned. The next element is the second element of g, which we again just calculated, etc...
!! is just indexing into a list, so this means get the element at index 0 from g:
Prelude> g !! 0
4
But when I do this:
Prelude> let f = f !! 10 : f
something breaks, because to compute the first element of f you need the 11th element, which doesn't exist yet? I would expect an exception, though, not an infinite loop...