
<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div><span></span></div><div><div>You could use a StateT (Map k v) or something and avoid using ST. No idea what the performance would be like. </div><div><br></div><div>You could probably get a performance boost using a memo data structure optimized for numeric keys, like IntMap. <br><br>--Will <br><br></div><div><br>On Aug 7, 2015, at 18:11, Ilya Razenshteyn <<a href="mailto:ilyaraz@gmail.com">ilyaraz@gmail.com</a>> wrote:<br><br></div><blockquote type="cite"><div><div dir="ltr"><div>Hi everyone,</div><div><br></div><div>I'm new to Haskell and decided to learn a bit about monads and their utility. Actually, what worked nicely for me was: to read first several pages from "Computational lambda-calculus and monads", then do exercises from <a href="https://tonymorris.github.io/blog/posts/20-intermediate-haskell-exercises/">https://tonymorris.github.io/blog/posts/20-intermediate-haskell-exercises/</a>, and then map these exercises to actual functions in the standard library.</div><div><br></div><div>Then, I decided to implement memoization to practice a bit with ST, HashTable's and such. Here is what I managed to get: <a href="http://pastebin.com/79pwjLPL">http://pastebin.com/79pwjLPL</a> . This code computes Fibonacci numbers while caching the intermediate values in a hash table. I tried to make the code as fast as possible (it runs in under 15 seconds, when computing 1M'th Fibonacci number modulo 999983). It uses the package hashtables.</div><div><br></div><div>I have several question about all this.</div><div><br></div><div>First, is there a cheap way to speed this code up? Note that I'm interested in a universal memoization strategy, that is I don't want to use arrays instead of hash tables etc.</div><div><br></div><div>Second, is this code the right way of doing what it does (assuming that I really care about the performance)?</div><div><br></div><div>Third question. Currently, the code passes "cache" everywhere. It would be natural to combine ST with something like ReaderT to store it there. What is a way to do it? I tried something like "ReaderT (HashTable s) (ST s) Int", but I have not managed to get it work.</div></div>

</div></blockquote><blockquote type="cite"><div><span>_______________________________________________</span><br><span>Haskell-Cafe mailing list</span><br><span><a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a></span><br><span><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a></span><br></div></blockquote></div></body></html>