Hi,<br>Since I actually didn't use the parameter in calculation, the return value only depends on the type<br>of input, not the actually value. If it's impossible to cache the result, is there another way to<br>memorize this "function" ?<br>
<br><div class="gmail_quote">On Sun, Nov 6, 2011 at 9:20 PM, Yucheng Zhang <span dir="ltr"><<a href="mailto:yczhang89@gmail.com">yczhang89@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="HOEnZb"><div class="h5">On Sun, Nov 6, 2011 at 9:10 PM, Bin Jin <<a href="mailto:bjin1990@gmail.com">bjin1990@gmail.com</a>> wrote:<br>
> Hi, everyone<br>
><br>
> I'm recently trying to implement the Montgomery reduction algorithm[1] in<br>
> Haskell, the code can be found on<br>
> my Github page[2]. After doing some benchmark testing I found that the<br>
> library works rather slow. With the<br>
> help of `trace` function from Debug.Trace, I found that GHC is not magical<br>
> enough to memorize values with<br>
> the same type(well, it's actually dynamically generated number parameterized<br>
> type).<br>
><br>
> I used binary representation to handle all positive numbers in type system.<br>
><br>
>> data One = One<br>
>> data D0 a = D0 a<br>
>> data D1 a = D1 a<br>
>> class PostiveN a where<br>
>> p2num :: (Num b, Bits b) => a -> b<br>
>> instance PostiveN One ...<br>
>> instance PostiveN a => PostiveN (D0 a) ...<br>
>> instance PostiveN a => PostiveN (D1 a) ...<br>
><br>
> Here is a function that will be called everytime by `(*)` in `Num` typeclass<br>
>> montgKeys :: (PostiveN p, Integral a, Bits a) => p -> a<br>
><br>
> as you can imagine, I always pass (undefined :: p) as parameter to<br>
> `montgKeys`, so if it's handled<br>
> well, it should be memorized for future usage. But tracing shows that both<br>
> `p2num` and `montgKeys`<br>
> are evaluated every time being called.<br>
><br>
> So my question is, how to force GHC memorizing this kind of functions?<br>
><br>
> [1]: <a href="http://en.wikipedia.org/wiki/Montgomery_reduction" target="_blank">http://en.wikipedia.org/wiki/Montgomery_reduction</a><br>
> [2]: <a href="https://github.com/bjin/montg-reduce" target="_blank">https://github.com/bjin/montg-reduce</a><br>
><br>
> Regards,<br>
> Bin<br>
<br>
</div></div>GHC only memorizes data structures, but not functions. See [1].<br>
<br>
[1] <a href="http://www.haskell.org/haskellwiki/Memoization" target="_blank">http://www.haskell.org/haskellwiki/Memoization</a><br>
<span class="HOEnZb"><font color="#888888"><br>
<br>
--<br>
Yucheng Zhang<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</font></span></blockquote></div><br>