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

[SimonK77]

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?


http://www.bilder-hochladen.net/files/bxlk-6-jpg.html 
http://www.bilder-hochladen.net/files/thumbs/bxlk-6.jpg  

I hope someone can help...
-- 
View this message in context: http://www.nabble.com/Reduction-Sequence-of-simple-Fibonacci-sequence-implementation-tp25178377p25178377.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090827/b03f8d40/attachment-0001.html