[Haskell-beginners] Looking for a datastructure

[David Place]

On Jul 17, 2011, at 3:57 AM, Kees Bleijenberg wrote:

> 2. A fast way to find the key with the lowest map-value (without traversing
> the whole map).

I see.   If you were to implement it without worrying about the performance, you could just use a map and compute a fold over the map to find the min value.  To have better performance, you want to incrementally recompute the fold at each update.  This is the topic of an article that I wrote for the Monad.Reader called "How to refold a map." 

> http://www.haskell.org/wikiupload/6/6a/TMR-Issue11.pdf

I show how to modify Data.Map for that purpose.  Also, it turns out to be really nice to implement it in FingerTrees.  If you would like I can post that too.

___________________
David Place   
Owner, Panpipes Ho! LLC
http://panpipesho.com
d at vidplace.com