[Haskell-cafe] monads, memoization etc

[Will Yager]

You could use a StateT (Map k v) or something and avoid using ST. No idea what the performance would be like. 

You could probably get a performance boost using a memo data structure optimized for numeric keys, like IntMap. 

--Will 


> On Aug 7, 2015, at 18:11, Ilya Razenshteyn <ilyaraz at gmail.com> wrote:
> 
> Hi everyone,
> 
> 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 https://tonymorris.github.io/blog/posts/20-intermediate-haskell-exercises/, and then map these exercises to actual functions in the standard library.
> 
> Then, I decided to implement memoization to practice a bit with ST, HashTable's and such. Here is what I managed to get: http://pastebin.com/79pwjLPL . 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.
> 
> I have several question about all this.
> 
> 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.
> 
> Second, is this code the right way of doing what it does (assuming that I really care about the performance)?
> 
> 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.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150807/db1beb60/attachment.html>