Non-pointfree style is substantially slower

Question

I have the following, oft-quoted code for calculating the nth Fibonacci number in Haskell:

fibonacci :: Int -> Integer
fibonacci = (map fib [0..] !!)
    where fib 0 = 0
          fib 1 = 1
          fib n = fibonacci (n-2) + fibonacci (n-1)  

Using this, I can do calls such as:

ghci> fibonacci 1000

and receive an almost instantaneous answer.

However, if I modify the above code so that it's not in pointfree style, i.e.

fibonacci :: Int -> Integer
fibonacci x = (map fib [0..] !!) x
    where fib 0 = 0
          fib 1 = 1
          fib n = fibonacci (n-2) + fibonacci (n-1) 

it is substantially slower. To the extent that a call such as

ghci> fibonacci 1000

hangs.

My understanding was that the above two pieces of code were equivalent, but GHCi begs to differ. Does anyone have an explanation for this behaviour?

Answer 1

To observe the difference, you should probably look at Core. My guess that this boils down to comparing (roughly)

let f = map fib [0..] in \x -> f !! x

to

\x -> let f = map fib [0..] in f !! x

The latter will recompute f from scratch on every invocation. The former does not, effectively caching the same f for each invocation.

It happens that in this specific case, GHC was able to optimize the second into the first, once optimization is enabled.

Note however that GHC does not always perform this transformation, since this is not always an optimization. The cache used by the first is kept in memory forever. This might lead to a waste of memory, depending on the function at hand.