Re: [Haskell-cafe] memorize function with number parameterized types in GHC

Hi, Then how about p2num, how to memorize this function. Also I think it's okay to memorize this kind of function. The type system ensure all calling of montgKeys have the same type, e.g., it's a pure function without parameter, it's safe to memorize it since it didn't occupy more memory than representing dynamic generated types. On Nov 6, 2011 11:06 PM, "Yucheng Zhang" wrote:

On Sun, Nov 6, 2011 at 9:35 PM, Bin Jin wrote:

...

Hi, Since I actually didn't use the parameter in calculation, the return value only depends on the type of input, not the actually value. If it's impossible to cache the result, is there another way to memorize this "function" ?

Sorry, I haven't considered about 'number parameterized type' when I answered the question.

However, you can still use a data structure like MemoTrie [1] to memorize the function. The memorization is trivial, since you can convert between the number-typed 'undefined' and 'Integer' with the functions 'p2num' and 'num2p' in your code. I've not tested, but this is an example using MemoTrie:

...

import Data.MemoTrie

memoMontgKeys :: (PostiveN p, Integral a, Bits a) => p -> a memoMontgKeys = memoMontgKeys' . p2num

memoMontgKeys' :: (Integral a) => Integer -> a memoMontgKeys' = memo (montgKeys . num2p)

On the other hand, I think GHC is not expected to do the memorization automatically. An arbitrary number can turn up as the argument type of 'montgKeys'. This is similar to a function with an Integer argument, which GHC does not memorize now.

[1] http://hackage.haskell.org/package/MemoTrie

Yucheng Zhang