Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence
bulat.ziganshin at gmail.com
Thu Aug 27 15:42:18 EDT 2009
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.
Bulat mailto:Bulat.Ziganshin at gmail.com
More information about the Haskell-Cafe