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

Question

If I'm counting the occurences of characters in a string, I could easily implement this using an array in an imperative language, such as the following:

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 fast implementation of int-indexed mutable arrays.

But how could I easily do this using just Haskell with no additional packages and/or extensions? Of in other words, how can I implement a fast O(1) collection with indexing and mutability?

Answer 1

The implementation of vector uses internal GHC functions called primops. You can find them in the package ghc-prim which is hard-wired into GHC. It provides, among others, the following array functions:

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

These functions are implemented by GHC itself, but they are really lowlevel. The primitive package provides nicer wrappers of these functions. For arrays, these are:

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

Here is a simple example using these functions directly (IO is a 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 would just use the vector package, which is much more optimized (stream fusion, ...) and also easier to use.