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

[Bin Jin]

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 <yczhang89 at gmail.com> wrote:

> 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[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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111106/bf8621ce/attachment.htm>