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

Yucheng Zhang yczhang89 at gmail.com
Sun Nov 6 16:06:58 CET 2011

On Sun, Nov 6, 2011 at 9:35 PM, Bin Jin <bjin1990 at gmail.com> 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

More information about the Haskell-Cafe mailing list