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

[Bulat Ziganshin]

Hello SimonK77,

Thursday, August 27, 2009, 11:24:14 PM, you wrote:

list-based memoization for fibs should look as

fibs = 1 : 1 : map (sum.take 2) (tails fibs)

>  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: Reduction Sequence of simple Fibonacci sequence implementation
>  Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
>   


-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com