This package [1] provides an implementation of a skip list using STM. A skip list is a probabilistic data structure with Data.Map-like operations. In contrast to a balanced tree, a skip list does not need any (expensive) rebalancing, which makes it particularly suitable for concurrent programming. You can find some documentation on how to use it here: http://darcs.monoid.at/tskiplist/dist/doc/html/tskiplist/Control-Concurrent-... Feedback appreciated! Peter [1] http://hackage.haskell.org/package/tskiplist-0.0.0