Immutable vs Mutable Vectors in Haskell

When performance matters, deciding between immutable and mutable vectors can change your program’s speed and memory usage. This guide explains the constraints, compares both options, and shows a concrete ST‑monad implementation that stays pure from the caller’s view.

Problem Statement

Numeric kernels in Haskell often need to update large dense arrays in a tight loop. The vector package offers two flavors: immutable Data.Vector and mutable Data.Vector.Mutable. Choosing the wrong one can lead to unnecessary allocations or subtle bugs. The decision must satisfy the following constraints:

Compile with GHC 9.x and vector ≥ 0.12.
Expose a pure API to callers; the stateful part must be hidden inside runST.
The algorithm must not escape the ST monad.
Thread safety is required; the vector must not be shared unsafely between threads.

Given these constraints, the decision boils down to whether in‑place updates are worth the added complexity.

Decision & Constraints

Decision: Use Data.Vector.Mutable inside the ST monad for large, dense numeric updates, and return an immutable vector via runST. For simpler code or when updates are infrequent, stay with Data.Vector.

Constraints Recap:

GHC 9.x, vector ≥ 0.12.
Pure API surface.
No escaping ST state.
Thread‑safe usage.

Compact Comparison Table

\n\n \n \n \n \n \n \n \n \n \n \n \n

Aspect	Data.Vector	Data.Vector.Mutable (ST)
Update Cost	O(n) (copy on write)	O(1) (in‑place)
Memory Allocation	Large, frequent allocations	Minimal, single allocation
Purity	Pure	Pure via runST
Thread Safety	Safe to share	Unsafe to share; requires copy or sync
Debugging	Easy (no side‑effects)	Harder (stateful)
Typical Use	Small transforms, functional pipelines	Large loops, numeric kernels

Trade‑Offs Explained

Speed vs Simplicity: Mutable vectors give a ~2‑3× speedup for million‑element loops, but require careful scoping. Immutable vectors keep code simple but may double memory traffic.
Safety: Mutable vectors bypass bounds checks for speed; an out‑of‑bounds write is undefined. Use unsafeWrite only when the index is guaranteed valid.
Concurrency: Immutable vectors can be freely shared across threads. Mutable vectors must be cloned or protected with MVar or STM if shared.
Garbage Collection: Mutable vectors reduce GC pressure because fewer intermediate arrays exist.

Concrete Implementation: In‑Place Factorial Accumulator

The following example builds a factorial sequence in a mutable vector and then returns an immutable vector. The code stays pure because runST hides the mutable state.

{-# LANGUAGE RankNTypes #-}\nimport qualified Data.Vector as V\nimport qualified Data.Vector.Mutable as MV\nimport Control.Monad.ST (ST, runST)\n\n-- | Compute factorials up to n (inclusive) in a mutable vector.\nfactorialVec :: Int -> V.Vector Integer\nfactorialVec n = runST $ do\n  mv :: MV.MVector s Integer <- MV.new (n + 1)\n  MV.write mv 0 1                 -- 0! = 1\n  let loop i acc\n        | i > n = return ()\n        | otherwise = do\n            MV.write mv i acc\n            loop (i + 1) (acc * fromIntegral i)\n  loop 1 1\n  V.freeze mv\n

Key points:

MV.write is O(1); no bounds checks are performed at runtime for speed.
The entire mutable state lives inside the ST monad; runST guarantees it cannot escape.
The result is an immutable Vector suitable for any pure consumer.

Validation Steps

Compile with GHC 9.6 and flags -Wall -Werror to ensure no warnings.
Run ghc factorial.hs -O2 and execute the binary; verify the vector contains the expected factorials.
Use Criterion to benchmark the loop against an immutable‑vector version that copies on each update.

Benchmark Skeleton with Criterion

import Criterion.Main\nimport qualified Data.Vector as V\n\nmain :: IO ()\nmain = defaultMain [\n  bench \"mutable factorial\" $ nf factorialVec 1000000,\n  bench \"immutable loop\" $ nf immutableLoop 1000000\n  ]\n\nimmutableLoop :: Int -> V.Vector Integer\nimmutableLoop n = foldl' (\\vec i -> vec V.// [(i, vec V.! (i-1) * fromIntegral i)]) (V.replicate (n+1) 1) [1..n]\n

Run cabal bench or stack bench to see the expected ~2× speedup for the mutable version.

Practical Checks & Limitations

Use MV.unsafeWrite only when you can statically prove the index is within bounds.
In multi‑threaded contexts, pass the immutable result or clone the mutable vector before sharing.
Verify that no runST leaks by inspecting the generated Core with ghc -ddump-core; the ST monad should be inlined.
When debugging, prefer the immutable path; swap to mutable only when profiling shows a bottleneck.

Conclusion

For performance‑critical numeric workloads that require many in‑place updates, Data.Vector.Mutable inside ST is the right choice. It offers lower allocation, faster updates, and minimal GC overhead. However, it demands careful scoping, bounds safety, and thread‑safety considerations. When these constraints are not critical, the simpler immutable vector remains a safe and expressive alternative.

Choosing Between Data.Vector and Data.Vector.Mutable for High‑Performance Haskell Workloads