[Haskell-cafe] monads, memoization etc

[Ilya Razenshteyn]

The third problem (not passing the state everywhere) got solved by using
lift. Thanks to the people from #haskell channel. Interestingly, the code
became almost twice as slow as a result..

The new code can be found here: http://pastebin.com/hkeJECem

On Fri, Aug 7, 2015 at 6:17 PM, Ilya Razenshteyn <ilyaraz at gmail.com> wrote:

> quickfix: 10M'th, not 1M'th of course.
>
>
> Cheers,
> Ilya
>
> On Fri, Aug 7, 2015 at 6:11 PM, 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.
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150808/230d5c4f/attachment.html>