[Haskell-cafe] Re: Reduction Sequence of simple Fibonacci sequence implementation

SimonK77 writes:

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?

You are, as easily seen when you try to calculate (fib 30). A version that works: import Data.MemoTrie fib :: Integer -> Integer fib = memo \n -> case n of 0 -> 0 1 -> 1 n -> fib (n-1) + fib (n-2)