[Haskell-cafe] Re: Reduction Sequence of simple Fibonacci
sequence implementation
Rohan Lean
haskell at rohanlean.de
Thu Aug 27 15:34:43 EDT 2009
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)
More information about the Haskell-Cafe
mailing list