Actually, looking back, I'm not sure mapM is even the right choice. I think
foldM would suffice. All we're doing is finding the association pair with
the minimum key, no? In this case, foldM would do everything we need
to...and State.Strict would be pretty good at that.
Louis Wasserman
wasserman.louis@gmail.com
http://profiles.google.com/wasserman.louis
On Thu, Mar 4, 2010 at 8:32 AM, Daniel Fischer
Am Donnerstag 04 März 2010 04:20:05 schrieb Louis Wasserman:
James,
Which version of Control.Monad.State are you importing?
If you're just importing vanilla Control.Monad.State, that's actually sending you to Control.Monad.State.Lazy.
Using Control.Monad.State.Strict might solve your problems, srsly. Laziness can result in epically failing memory leaks.
That was my first thought too, but for this code, Control.Monad.State.Lazy is the better choice. Control.Monad.State.Strict doesn't play too well with sequence (and hence mapM). Since James consumes the list of chain lengths as it is produced (key = maximum keys), no large thunks can build up. With the strict State, he can't start to look for the maximum until all chain lengths have been computed, building a big fat thunk for the list.
Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis