Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence
implementation
Bulat Ziganshin
bulat.ziganshin at gmail.com
Thu Aug 27 15:32:08 EDT 2009
Hello SimonK77,
Thursday, August 27, 2009, 11:24:14 PM, you wrote:
for linear timing it needs memoization of previous results. haskell
compilers doesn't do it automatically since it may change space
properties of program. well-known example is:
main = print (sum[1..1000] + prod[1..1000])
in order to use memoization you should declare fib as array:
fib = array (1,999) ([1,1]++map (\i -> fib!(i-1) + fib!(i-2)) [3..999])
> 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
More information about the Haskell-Cafe
mailing list