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

[Felipe Lessa]

2008/12/16 Magnus Therning <magnus at therning.org>:
> 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?
>
> I realise this particular function can be written using scanl:
[...]
> but I guess it's not always that easy to construct a solution based on scanl.


You can always write something like

> foo :: Int -> Int
> foo = (vals !!)
>     where
>     vals = map foo' [0..]
>     foo' 0 = 0
>     foo' 1 = 1
>     foo' 2 = 2
>     foo' n = sum $ map foo [0..n-1]

which doesn't prevent you from using whatever recursive case you want.
Note that if your recursive case depends on all preceding values, then
you can't do better than using a linear access data structure like a
list unless you need random access.


I should point out as well that there are some packages on Hackage for
memoization, like:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/data-memocombinators
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/MemoTrie


-- 
Felipe.