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