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

SimonK77 simonkaltenbacher at
Thu Aug 27 15:24:14 EDT 2009

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?  

I hope someone can help...
View this message in context:
Sent from the Haskell - Haskell-Cafe mailing list archive at
-------------- next part --------------
An HTML attachment was scrubbed...

More information about the Haskell-Cafe mailing list