Am Donnerstag 27 August 2009 21:41:49 schrieb Jason Dagit: > On Thu, Aug 27, 2009 at 12:32 PM, Bulat > > Ziganshin<[email protected]> 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)
Should be fibs = 0:1:zipWith (+) fibs (tail fibs) of course. > > Then to get a specific fib, zero index, you do: > fib n = fibs !! n > > Jason _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
