Using Haskell’s ST Monad for Fast, Pure Mutable State

Problem: Speedy Loops in a Pure Language

When processing millions of numbers, a naïve Haskell implementation that builds intermediate lists or vectors can become a performance bottleneck. Developers often wonder: can we write a tight, in‑place loop in Haskell without dropping referential transparency?

Thesis: The ST Monad Is the Bridge Between Purity and Imperative Speed

The ST monad encapsulates mutable references and arrays inside a thread‑local state thread. By wrapping all mutable operations inside runST, the type system guarantees that no mutable state can escape, preserving the purity of the surrounding code. At the same time, GHC can compile the inner loop into efficient, unboxed machine code that rivals hand‑written C.

How the ST Monad Works

• ST s a is a state thread indexed by a phantom type s. The index ensures that mutable values cannot leave the runST boundary.
• STRef s a and STArray s i a are mutable containers that live only inside the same s.
• Running runST :: (forall s. ST s a) -> a erases the state thread after execution, returning a pure value.
• Because the state thread is erased, GHC can inline and unbox the loop, eliminating heap allocations for temporary values.

Concrete Example: Summing an Array In‑Place vs. Pure Vector

The following snippet shows a classic sum implemented with STArray and STRef, and a purely functional counterpart using Data.Vector.Unboxed.

{-# LANGUAGE ScopedTypeVariables #-}
import Control.Monad
import Control.Monad.ST
import Data.Array.MArray
import Data.Array.ST
import qualified Data.Vector.Unboxed as VU

-- | Mutable sum using STArray and STRef
sumArray :: Int -> Int
sumArray n = runST $ do
  arr  <- newArray (0, n-1) 0 :: ST s (STArray s Int Int)
  -- initialise the array with 0..n-1
  forM_ [0..n-1] $ \i -> writeArray arr i i
  sumRef <- newSTRef 0
  forM_ [0..n-1] $ \i -> do
    v <- readArray arr i
    modifySTRef' sumRef (+ v)
  readSTRef sumRef

-- | Pure sum using an unboxed vector
pureSum :: Int -> Int
pureSum n = VU.foldl' (+) 0 (VU.enumFromN 0 n)

Compile both functions with -O2 and benchmark them with cabal bench or stack bench. Typical results on a 64‑bit machine show the ST version running 3–5× faster for large n (e.g., 10⁷ elements). The speedup comes from:

• Elimination of intermediate lists or vectors.
• Unboxed integer arithmetic inside the loop.
• No heap allocation for the loop counter or the accumulator.

You can verify the optimization by inspecting the generated Core:

ghc -O2 -ddump-simpl MyModule.hs

Look for STRef read/write operations compiled to primitive mutableByteArray primitives and no alloc calls inside the loop body.

Trade‑offs and Caveats

• Scope is strict. Mutable values must never escape runST. The type system enforces this, but accidental use of unsafeCoerce or storing an STRef in a global can break safety.
• Performance depends on GHC flags. Without -O2 or on older GHC releases, the compiler may not unbox values, and the ST loop may be as slow as the pure version.
• Compatibility with other monads. To combine ST with stateful or error‑handling monads, you normally lift ST into a transformer stack (e.g., StateT s (ST s) or ExceptT e (ST s)). Lifting adds a small overhead but preserves the safety guarantee.
• Debugging difficulty. Because the mutable state is hidden, stack traces for errors inside runST can be harder to interpret. Use traceST or explicit checks if you need debugging output.

Actionable Takeaway

When you need a tight loop over a large dataset, wrap the mutable logic in ST and compile with -O2. Verify the speedup by:

1. Running a simple benchmark comparing the ST and pure implementations.
2. Inspecting the generated Core for unboxed primitives.
3. Checking GC statistics with +RTS -s to confirm minimal allocations.

If you encounter performance regressions, try enabling -fllvm or -fspec-constr to help GHC unbox more aggressively. Remember that the ST monad is safe as long as you keep mutable references local; any attempt to escape them will be caught by the type checker.

With these checks in place, you can confidently use ST to write high‑performance, pure Haskell code that feels like an imperative language.