wren ng thornton wren at freegeek.org
Tue Dec 16 15:09:20 EST 2008

```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
```