[Haskell-cafe] How to think about this? (profiling)
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
More information about the Haskell-Cafe
mailing list