List comprehension is not tail recursive?

[tr00per]

I've typed the classic Fibonacci-in-list example in REPL: let fib = 0 : 1 : [ a + b | (a,b) <- zip fib (tail fib)] then I wanted to get the 10000th element with fib !! 10000 - GHCi managed to compute this, but etlas repl (docker version) returned only StackOverflowError. If I first compute 1000th and 3000th element in etlas repl, then it's possible to get the 10000th element.

Is list comprehension not tail recursive? How can I provide/extract more details to help debug this?

[rahulmutt]

Thanks for reporting! The issue here doesn't appear to be tail recursion and more about how thunks are handled. I'll take a look and try to reproduce in my repl as well.

[rahulmutt]

I was able to reproduce the StackOverflow, but I was not able to reproduce the fact that were able to get it to succeed by evaluating it a little.

main :: IO ()
main = do
  let fib = 0 : 1 : [ a + b | (a,b) <- zip fib (tail fib)]
  print $ fib !! 1000
  print $ fib !! 3000
  print $ fib !! 10000

This problem evaluates the first two successfully but fails to evaluate the last.

[rahulmutt]

I was able to reproduce that behavior in the repl - very strange!

[rahulmutt]

The problem here is that in order to evaluate fib !! 10000, Eta has to evaluate a long chain of thunks. For each thunk in the chain, it'll create an update frame [1] which amounts to a method call that increases the call stack size.

If any thunk in the chain is already evaluated, it cuts the chain short. This is why you observed the effect that fib !! 3000 and then fib !! 10000 will work. fib !! 3000 would have evaluated the first 3001 elements of fibonacci and replaced the thunks with their evaluated values, so the chain size would be 3000 shorter, which means the call stack size would also be that much shorter.

Now let's understand how the graph of thunks is created by the simple line of code:

let fib = 0 : 1 : [ a + b | (a,b) <- zip fib (tail fib)]

Suppose the structure looks like this on the heap:

0 : 1 : a2

a2 upon evaluation, will expand to more elements of the list as per demand. When you run fib !! 10000, the list will be traversed without evaluating the intermediate thunks!

0 : 1 : a2 : a3 : a4 : .... : a10000 : a10001

Note that to evaluate an aN you need to evaluate a(N - 1) and a(N - 2) and so on. Hence, if you evaluate any of the aN it will (eventually) evaluate all the a* before it. When evaluating a10000, it will create a long evaluation chain (hence call stack) all the way to a2 and then it will come back down to give you a result.

Because of the stack size limitation of the JVM (which GHC doesn't have - it has an unbounded stack), you'll get a StackOverflowError. I personally consider this a good thing because long evaluation chains like this will be responsible for sudden memory usage bursts in a production app which may take it down if it's in a container environment with memory limits. [2] Another problem with long call stacks is that it increases the GC time because the GC treats the references in the call stack as roots.

Now that we have a basic understanding, let's make this work. The key insight here is that since we need to evaluate all the thunks before aN anyways, we might as well do it eagerly! Which means we need a slightly stricter version of !! which I'll name evaluateAndGo.

main :: IO ()
main = do
  let fib = 0 : 1 : [ a + b | (a,b) <- zip fib (tail fib)]
      evaluateAndGo (x:_) 0 = x
      evaluateAndGo (x:xs) n = x `seq` evaluateAndGo xs (n - 1)
  print (evaluateAndGo fib 10000)

Hope that helps!

[1] This is a bit of code that updates the thunk with the evaluated result after it's done to avoid re-evaluating the thunk on future evaluation requests.

[2] Those update frames take up space too, even in GHC, they will just be more space-optimized!