A Skip List Implementation in Software Transactional Memory (STM)
|Latest on Hackage:||1.0.1|
This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.
This package provides a proof-of-concept implementation of a skip list in STM. A skip list is a probabilistic data structure with dictionary operations and support for efficient range-queries (similarly to Data.Map). In contrast to tree data structures, a skip list does not need any rebalancing, which makes it particularly suitable for concurrent programming. (See: William Pugh. Skip Lists: A Probabilistic Alternative to Balanced Trees.)