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. I should point out as well that there are some packages on Hackage for memoization, like: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/data-memocombinators http://hackage.haskell.org/cgi-bin/hackage-scripts/package/MemoTrie -- Felipe. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
