Re: [Haskell-cafe] How to think about this? (profiling)

Lemmih wrote:

On Tue, Dec 16, 2008 at 1:07 PM, Magnus Therning wrote:

...

I understand your solution, but AFAICS it's geared towards limited recursion in a sense. What if I want to use memoization to speed up something like this

foo :: Int -> Int foo 0 = 0 foo 1 = 1 foo 2 = 2 foo n = sum [foo i | i <- [0..n - 1]]

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?

You could use a Map or a mutable array. However, this kind of problem comes up a lot less often than you'd think.

And, that example is also easily memoizable by forward chaining (i.e. accumulators). The reason is because `sum` is such a simple function that you can decompose it as total_{t} = total_{t-1} + x_{t}; and given that x_{t} is defined to be the same as total_{t-1} we have: > foo i = foos !! i > where > foos = let s x = x : (s $! x + x) in 0 : 1 : 2 : s 3 You'd need to come up with an example where you replace `sum` with a function that is a non-decomposable combination of its input values. Lists are beautiful for being decomposable, which is why we have such nice functions as foldr and friends, so anything intuitive based on a list is most likely going to be decomposable as well. Coming up with a variadic function which isn't decomposable is extremely uncommon in practice. -- Live well, ~wren