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

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" ? On Sun, Nov 6, 2011 at 9:20 PM, Yucheng Zhang wrote:

...

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

On Sun, Nov 6, 2011 at 9:10 PM, Bin Jin wrote: 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

GHC only memorizes data structures, but not functions. See [1].

[1] http://www.haskell.org/haskellwiki/Memoization

-- Yucheng Zhang

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe