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

[Bin Jin]

Hi, everyone

I'm recently trying to implement the Montgomery reduction algorithm[1] in
Haskell, the code can be found on
my Github page[2]. After doing some benchmark testing I found that the
library works rather slow. With the
help of `trace` function from Debug.Trace, I found that GHC is not magical
enough to memorize values with
the same type(well, it's actually dynamically generated number
parameterized type).

I used binary representation to handle all positive numbers in type system.

> data One = One
> data D0 a = D0 a
> data D1 a = D1 a
> class PostiveN a where
>     p2num :: (Num b, Bits b) => a -> b
> instance PostiveN One ...
> instance PostiveN a => PostiveN (D0 a) ...
> instance PostiveN a => PostiveN (D1 a) ...

Here is a function that will be called everytime by `(*)` in `Num` typeclass
> montgKeys :: (PostiveN p, Integral a, Bits a) => p -> a

as you can imagine, I always pass (undefined :: p) as parameter to
`montgKeys`, so if it's handled
well, it should be memorized for future usage. But tracing shows that both
`p2num` and `montgKeys`
are evaluated every time being called.

So my question is, how to force GHC memorizing this kind of functions?

[1]: http://en.wikipedia.org/wiki/Montgomery_reduction
[2]: https://github.com/bjin/montg-reduce

Regards,
Bin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111106/0612bde7/attachment.htm>