Funky haskell lazy list implicit recursion

Question

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...

Answer 1

In this case, a picture may tell a thousand words.

First, remember how cons (the (:) list constructor) works. It's a pair of two things: an element, and a reference to a list tail (which is either another cons, or []).

As you should know, when you say [1, 2, 3], it's just a shortcut for (1:(2:(3:[]))) or 1:2:3:[]. If you visualize each cons pair as a box with two slots, this expression look like:

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

One loop

When you say g = 4 : g, you're not really building an "infinite" list, you're building a circular list: g is defined as a cons whose tail reference simply points back to g itself:

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

This actually has nothing to do with laziness, and everything with self-reference: for example, you can do the same thing in (eager) Common Lisp using syntax like '#1=(4 . #1#) (where the #1 is like g).

Whether you say g !! 0, or g !! 1000000000000, g never grows: (!!) simply runs around the loop in-place, for as many times as you told it to, until it exhausts itself and returns the element, 4.

Two loops

When you say f = (f !! 10) : f, the same thing happens—except now, the element slot contains a different expression than 4:

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

Crucially, this sub-expression also refers back to f, just like the tail does:

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

So, when you ask for f !! n, (!!) will first run around the top loop n times, then return the element, as it did for g. However, instead of escaping the loop, (f !! 10) just re-enters it, and the process repeats itself: looping 10 times around the top, then once around the bottom, and back.