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

[wren ng thornton]

Lemmih wrote:
> On Tue, Dec 16, 2008 at 1:07 PM, Magnus Therning <magnus at therning.org> 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