[Haskell-cafe] Re: speeding up fibonacci with memoizing

[Dan Weston]

Throwing in a trace statement in fibaux tells me that fibaux i a b c is 
not being memoized. If I do map fib [7..9], fibaux counts down to 0 
afresh for each of 7, 8, and 9. Ideally, in map fib [0..n], fib (i-2) 
and fib (i-1) should be memoized and fib i would be evaluated in 
constant time. This is what happens if the loop is unrolled explicitly.

marnes wrote:
>   fib :: Integer -> Integer
>   fib n = fibaux n 0 1 1
>    where
>     fibaux :: Integer -> Integer -> Integer -> Integer -> Integer
>     fibaux i a b c | i==0 = a
>                    | i/=0 = fibaux (i-1) b c (b+c)
> 
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
>