Lemmih wrote:
On Tue, Dec 16, 2008 at 1:07 PM, Magnus Therning <mag...@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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
