Hello, On Tuesday 16 December 2008 13:19, Felipe Lessa wrote: > 2008/12/16 Magnus Therning <mag...@therning.org>: > > That is, where each value depends on _all_ preceding values. AFAIK > > list access is linear, is there a type that is a more suitable state > > for this changed problem? > > > > I realise this particular function can be written using scanl: > [...] > > but I guess it's not always that easy to construct a solution based on scanl. > > > You can always write something like > > > foo :: Int -> Int > > foo = (vals !!) > > where > > vals = map foo' [0..] > > foo' 0 = 0 > > foo' 1 = 1 > > foo' 2 = 2 > > foo' n = sum $ map foo [0..n-1] > > which doesn't prevent you from using whatever recursive case you want. > Note that if your recursive case depends on all preceding values, then > you can't do better than using a linear access data structure like a > list unless you need random access.
Another possibility would be: > g n = t!n > where > t = array > (0,max 2 n) > $ (0,0):(1,1):(2,2):[ (i,t!(i-3) + t!(i-2) + t!(i-1)) | i <- [3..n] ] > using your original example. As noted in the Haskell 98 report, section 16.1 Array Construction, the array function is non-strict in the values of the association list, making this recurrence possible. > ... Best regards Thorkil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
