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

if i'm counting occurences of characters in string, implement using array in imperative language, such following:

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

i can see how in haskell using data.vector.mutable, provides fast implementation of int-indexed mutable arrays.

but how using haskell no additional packages and/or extensions? of in other words, how can implement fast o(1) collection indexing , mutability?

the implementation of vector uses internal ghc functions called primops. can find them in package ghc-prim hard-wired ghc. provides, among others, following array functions:

newarray# :: int# -> -> state# s -> (#state# s, mutablearray# s a#)  readarray# :: mutablearray# s -> int# -> state# s -> (#state# s, a#) writearray# :: mutablearray# s -> int# -> -> state# s -> state# s  

these functions implemented ghc itself, lowlevel. primitive package provides nicer wrappers of these functions. arrays, these are:

newarray :: primmonad m => int -> -> m (mutablearray (primstate m) a)  readarray :: primmonad m => mutablearray (primstate m) -> int -> m  writearray :: primmonad m => mutablearray (primstate m) -> int -> -> m ()  

here simple example using these functions directly (io primmonad):

import data.primitive.array import control.monad  main :: io () main =   arr <- newarray 3 (0 :: int)   writearray arr 0 1   writearray arr 1 3   writearray arr 2 7   form_ [0..2] $ \i -> putstr (show ++ ":") >> readarray arr >>= print 

of course, in practice use vector package, more optimized (stream fusion, ...) , easier use.