On Thu, Apr 14, 2011 at 8:02 PM, Luke Palmer
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): https://gist.github.com/921469 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