Haskell missing parentheses compiles but enters infinite loop

Question

I have a case where a Haskell missing parentheses compiles fine but enters an infinite loop. Here is my code with the working version commented out:

$ cat main.hs
fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n =
  let
    fib_n_minus_2 = fib n-2
    -- fib_n_minus_2 = fib (n-2)
    fib_n_minus_1 = fib (n-1)
  in
    fib_n_minus_2+
    fib_n_minus_1

main :: IO ()
main = putStrLn $ show $ fib 7

When I compile it everything goes fine, but when I run the resulting program it gets stuck. Why is that? I imagine the compiler parses fib n, then goes on to see -2 fib_n_minus_1 where it should stop and issue an error, right?

chi chi · Accepted Answer · 2019-10-15T07:21:00

fib_n_minus_2 = fib n-2

means

fib_n_minus_2 = (fib n)-2

and not

fib_n_minus_2 = fib (n-2)

Note that (fib n)-2 is a perfectly valid expression.

This is not parsed as (fib n) -2 fib_n_minus1 ... since fib_n_minus1 ... starts on the next line and is indented the exact same amount as the previous one, so it's the next binding for the let construct.

Indeed, you can pretend that, before real parsing starts, indentation is used to insert explicit braces around the bindings, and semicolons between them, as follows:

 let {
    fib_n_minus_2 = fib n-2 ;
    -- fib_n_minus_2 = fib (n-2)
    fib_n_minus_1 = fib (n-1)
    }
  in
    fib_n_minus_2+
    fib_n_minus_1

In the in section of let there can be only one expression, so the indentation rule does not apply, and those two lines are parsed as one expression, fib_n_minus_2 + fib_n_minus_1.

In conclusion, your code is calling itself without decreasing the argument n, thus causing the infinite recursion.

Haskell missing parentheses compiles but enters infinite loop

1 Answers