How can I implement a collection with O (1) indexing and volatility in Haskell?

Question

If I count the occurrences of characters in a string, I could easily implement this using an array in an imperative language, for example:

char values[256]; char c; while (c = readChar()) { values[c] += 1; } 

I can see how to do this in Haskell using something like Data.Vector.Mutable , which provides a quick implementation of modified int-indexable arrays.

But how could I easily do this using only Haskell without any additional packages and / or extensions? . In other words, how can I implement a fast O (1) collection with indexing and volatility?

Answer 1

The vector implementation uses GHC internal functions called primops. They can be found in the ghc-prim package, which is tightly connected to the GHC. It provides, among other things, the following array functions:

 newArray# :: Int# -> a -> State# s -> (#State# s, MutableArray# sa#) readArray# :: MutableArray# sa -> Int# -> State# s -> (#State# s, a#) writeArray# :: MutableArray# sa -> Int# -> a -> State# s -> State# s 

These functions are implemented by the GHC itself, but they are really low. The primitive package provides more convenient wrappers for these functions. For arrays, this is:

 newArray :: PrimMonad m => Int -> a -> m (MutableArray (PrimState m) a) readArray :: PrimMonad m => MutableArray (PrimState m) a -> Int -> ma writeArray :: PrimMonad m => MutableArray (PrimState m) a -> Int -> a -> m () 

Here is a simple example that uses these functions directly (IO is PrimMonad ):

 import Data.Primitive.Array import Control.Monad main :: IO () main = do arr <- newArray 3 (0 :: Int) writeArray arr 0 1 writeArray arr 1 3 writeArray arr 2 7 forM_ [0..2] $ \i -> putStr (show i ++ ":") >> readArray arr i >>= print 

Of course, in practice, you just use the vector package, which is much optimized (stream merging, ...), and also easier to use.