Hallo everyone,

as Haskell uses the Lazy Evaluation reduction policy also known as Outermost Graph Reduction, I was wondering if the following simple implementation of the Fibonacci sequence would result in linear runtime behaviour.

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 2) + fib (n - 1)

Is the following reduction sequence realistic, or am I admitting to much intelligence to the Haskell Compiler?