[Haskell-cafe] monads, memoization etc

Ilya Razenshteyn ilyaraz at gmail.com
Sat Aug 8 01:11:06 UTC 2015


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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150807/32233841/attachment.html>


More information about the Haskell-Cafe mailing list