Haskell list recursion - why does one work and not the other?

Question

Anyone familiar with Haskell will have likely seen this implementation of the Fibonacci sequence.

fibs = 0:1:zipWith (+) fibs (tail fibs)

The way I understand this is as follows:

Haskell's lazy evaluation allows for this infinite recursion with no issues
The way Haskell constructs lists (pairing the first element with the rest of the list) means the zipWith is evaluated to obtain the next element when needed
When fibs is referenced in the zipWith parameters, it takes the list as it currently exists without the new element being evaluated

With that knowledge, why does this loop infinitely rather than generate a list of primes?

main = print $ take 10 primes

dividesNone x ys = not $ any ((==0) . (x `mod`)) ys

primes = 2:[x | x <- [2..], x `dividesNone` primes]

I've tried similar implementations using dropWhile and find but the same thing happens. I've settled on this one as the one I most think "should" work. I'm sure there is some way to make this work the way I want - but even if I knew what that way was, I wouldn't understand why this doesn't. What is the difference between these two examples that causes one to work and one to loop infinitely?

user_33796 · Answer

From a denotational perspective, it's because 2:⊥ is a fixed point of the equation that defines primes.

The semantics of Haskell say that the meaning of a recursive definition is the least fixed point of the equation -- we should find the least defined value that satisfies the equation. Our equation is:

primes = 2:[x | x <- [2..], x `dividesNone` primes]

Notice that 3 `dividesNone` (2:⊥) gives ⊥. The check against 2 fails, then we ask if 3 divides any of the elements of the list ⊥, a list about which there is no information, so we have no information about that answer.

If we fill in 2:⊥ for primes:

2:⊥ = 2 : [x | x <- [2..], x `dividesNone` 2:⊥]  -- 2 fails the filter
    = 2 : [x | x <- [3..], x `dividesNone` 2:⊥]
    = 2 : [x | x <- [3..], ⊥]
    = 2:⊥

It satisfies the equation. And the only things less defined than 2:⊥ are ⊥ and ⊥:⊥, which do not satisfy the equation:

⊥   /= 2:[x | x <- [2..], x `dividesNone` ⊥]   = 2:⊥
⊥:⊥ /= 2:[x | x <- [2..], x `dividesNone` ⊥:⊥] = 2:⊥

So 2:⊥ is the least fixed point. That is, we will output two and then infinite loop.

In practice I use both the denotational and operational perspectives to reason about my code. Thinking about laziness operationally can get really complicated really quickly, so it's nice to have another tool in your belt.

user_67579 · Answer

When fibs is referenced in the zipWith parameters, it takes the list as it currently exists without the new element being evaluated.

It holds a reference to the list that is not entirely evaluated yet. But if it had to access the third element before that was evaluated, it would get stuck in an infinite loop. It thus initially looks like:

            ╭─────────────────────────────────╮
            │          ╭────────────────────╮ │
            ▽          ▽                    │ │
        ┌───┼───╮  ┌───┼───╮  ┌───────────╮ │ │
fibs ─▷ │ o │ o───▷│ o │ o───▷│  zipWith  │ │ │
        └─│─┴───╯  └─│─┴───╯  ├───┬───┬───┤ │ │
          ▽          ▽        │ o │ o │ o───╯ │
          0          1        └─│─┴─│─┴───╯   │
                                ▽   ╰─────────╯
                               (+)

and the zipWith will each time evaluate an item, and then the references will move to the next node, and that node is always evaluated already, or at least sufficient to not get into an infinite loop, so the next step, it looks like:

                       ╭─────────────────────────────────╮
                       │          ╭────────────────────╮ │
                       ▽          ▽                    │ │
        ┌───┬───╮  ┌───┼───╮  ┌───┼───╮  ┌───────────╮ │ │
fibs ─▷ │ o │ o───▷│ o │ o───▷│ o │ o───▷│  zipWith  │ │ │
        └─│─┴───╯  └─│─┴───╯  └─│─┴───╯  ├───┬───┬───┤ │ │
          ▽          ▽          │        │ o │ o │ o───╯ │
          0          1          ▽        └─│─┴─│─┴───╯   │
          △          △        ┌───────╮    ▽   ╰─────────╯
          │          │        │  (+)  │   (+)
          │          │        ├───┬───┤
          ╰──────────│──────────o │ o │
                     │        └───┴─│─╯
                     ╰──────────────╯

That is also what happens with your primes. The dividesNone will for example look for 3, and thus walk to the end of the thus far evaluated primes list. But since 3 is not dividable by 2, it will enumerate further, and thus walk into an unevaluated node. It will thus start evaluating the third item of the primes list (in order to evaluate the third element of the prime list), but that will again require to generate the third item, and thus gets stuck in an infinite loop.

It thus does not get a "copy" of the list that stops where it still has to evaluate. The list simply points to a node that still needs to be evaluated, triggering the interpreter to evaluate it, and thus gets it stuck into an infinite loop.

Haskell list recursion - why does one work and not the other?

2 Answers