Very fast, mutable associative data types based on Judy arrays.

A good imperative, mutable replacement for IntMap.

Judy arrays are both speed- and memory-efficient, with no tuning or configuration required, across a wide range of index set types (sequential, periodic, clustered, random). Judy's speed and memory usage are typically better than other data storage models such as skiplists, linked lists, binary, ternary, b-trees, or even hashing, and improves with very large data sets.

The memory used by a Judy array is nearly proportional to the population (number of elements).

For further references to the implementation, see:

• http://en.wikipedia.org/wiki/Judy_array

Building a simple word-index table. About 4x faster than using an IntMap

 import Control.Monad
 import qualified Data.Judy as J

 main = do
    j <- J.new :: IO (J.JudyL Int)
    forM_ [1..10000000] $ \n -> J.insert n (fromIntegral n :: Int) j
    v <- J.lookup 100 j
    print v

Running this:

 $ ghc -O2 --make A.hs
 [1 of 1] Compiling Main             ( A.hs, A.o )
 Linking A ...

 $ time ./A
 Just 100
 ./A  1.95s user 0.08s system 99% cpu 2.028 total