On Thu, Aug 27, 2009 at 12:32 PM, Bulat Ziganshin<bulat.zigans...@gmail.com> wrote: > 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])
Unless I'm mistaken this one is also memoized and simpler: fibs = 1 : 1 : zipWith (+) fibs (tail fibs) Then to get a specific fib, zero index, you do: fib n = fibs !! n Jason _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe