[Haskell-cafe] memorize function with number parameterized types in GHC
yczhang89 at gmail.com
Sun Nov 6 14:20:43 CET 2011
On Sun, Nov 6, 2011 at 9:10 PM, Bin Jin <bjin1990 at gmail.com> wrote:
> Hi, everyone
> I'm recently trying to implement the Montgomery reduction algorithm in
> Haskell, the code can be found on
> my Github page. 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
> 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?
> : http://en.wikipedia.org/wiki/Montgomery_reduction
> : https://github.com/bjin/montg-reduce
GHC only memorizes data structures, but not functions. See .
More information about the Haskell-Cafe