On Thu, Apr 14, 2011 at 8:02 PM, Luke Palmer <lrpalmer@gmail.com> wrote:
For this problem, it is too slow to memoize everything; you have to use a bounded memo table. That's why I use a combinator-based memo approach as opposed to the type-directed approach used in eg. MemoTrie. The memo table you need is something like
switch (<10^6) integral id
I think because of the definition of `Data.Function.fix`
fix f = let x = f x in x
which uses sharing, the definition
fibonacci = fix (switch (<10^6) integral id . fib)
chaches results even of independent global calls. If `fix` would be defined as
fix f = f (fix f)
it would only cache the recursive calls of each individual call.
Do you agree?
Here is a fixpoint combinator that is parameterized by a memo combinator:
fixmemo :: Memo a -> ((a -> b) -> (a -> b)) -> (a -> b)
fixmemo memo f = fix (memo . f)
If I use
fixmemo (switch (<=10^6) integral id) collatz
the computation of the maximum Collatz length between 1 and 10^6 takes around 16 seconds (rather than 4 seconds without memoization). But when using
fixmemo (arrayRange (1,10^6)) collatz
memoization actually pays off and run time goes down to around 3 seconds. I uploaded the program underlying my experiments to github (spoiler alert):
I knew that memocombinators are more flexible than a type-based MemoTrie but it is nice to see that they also lead to more efficient implementations and allow to define the other array-based implementation from this thread in a modular way.
Sebastian