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

[Rohan Lean]

SimonK77 <simonkaltenbacher <at> googlemail.com> 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)