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

[Bulat Ziganshin]

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