Inside the ST boundary: a Haskell deep read
A deep read of Michael Snoyman's analogy between Haskell's immutable values, local mutation in `ST`, and the type boundary that keeps state from escaping.
The boundary that lets Haskell mutate locally
Michael Snoyman's June 26 post, "Kabbalah, Haskell, and the ST Monad", is built around an unusual comparison. A Kabbalistic idea about spiritual states that are not erased leads him to Haskell's
ST monad, where mutation can happen inside a computation without becoming visible in the value returned by that computation. 1The religious analogy is personal and deliberately tentative. The functional-programming lesson is more precise:
ST is a boundary that lets an implementation use local mutation while its public interface remains an ordinary pure function. That boundary, rather than the analogy itself, is the reason this post belongs in an FP reader's queue.The problem starts with a performance trade-off
Snoyman begins with a list such as:
[1, 2, 3, 4, 5]To add one to every element, a purely immutable model produces a new list rather than overwriting the old one:
[2, 3, 4, 5, 6]That model is valuable because other parts of the program can keep using the original value without worrying that a hidden update changed it. It also avoids the aliasing problem that appears when two references point to the same mutable structure. 1
But imagine an operation that updates one position at a time. A literal immutable implementation might produce a chain of intermediate values:
[1, 2, 3, 4, 5]
[2, 2, 3, 4, 5]
[2, 3, 3, 4, 5]
[2, 3, 4, 4, 5]
[2, 3, 4, 5, 5]
[2, 3, 4, 5, 6]The example is intentionally simple.
map (+1) is the obvious solution for this particular transformation. Snoyman's real question is what to do when an algorithm benefits from repeated in-place updates, but the surrounding program should still see immutable data.That is the point at which "pure" and "implemented without mutation" stop being synonyms.
What ST contains
The
base library describes ST as a state-thread monad that allows destructive updates. An ST s a computation runs in a state thread identified by s and returns a value of type a. The official API exposes the key escape hatch as:runST :: (forall s. ST s a) -> aThe important part is the
forall s. The caller does not choose the state-thread identity. The computation must work for any fresh s, and the result type cannot contain that private identity. The documentation states the consequence directly: the internal state used by the computation is inaccessible to the rest of the program. 2Mutable references carry the same parameter:
STRef s anewSTRef, readSTRef, and writeSTRef all operate within the same s. A reference created in one state thread is therefore not a general mutable cell that can be handed to unrelated code. It belongs to that thread. 3A small example makes the shape visible:
counter :: Int
counter = runST $ do
ref <- newSTRef 0
writeSTRef ref 1
readSTRef refThe updates in the
do block are operationally real. The reference is written, then read. What disappears at the boundary is the reference and its state-thread identity. counter is just an Int.That is stronger than a convention such as "please do not mutate this value after returning it." The type of
runST prevents the private state from being part of the returned result. The implementation gets a narrow mutable workspace; callers get a value with no handle into that workspace.This is why the phrase "local mutation" matters.
ST does not turn arbitrary mutation into purity. It isolates mutation so that the observable behavior of the enclosing function can still be described as a value-producing computation. The distinction is also why ST should not be casually conflated with IO: the same module documents stToIO separately, with RealWorld marking a state supplied by IO rather than one of the private threads created by runST. 2The analogy works at the boundary
Snoyman then changes subjects. In the Kabbalistic idea he is learning, a spiritual state is not erased and rewritten into a different state. A new state arises while the previous one remains. He connects that description to Haskell's ordinary immutable values: an old value remains, and a new value is derived from it. 1
The more interesting comparison is with
ST. Snoyman suggests that the physical world might be analogous to one large ST action: change is real inside the process, while a higher-level view could treat the whole process as one contained transformation. He presents that as an analogy, not as a rigorous Kabbalistic model, and explicitly warns readers not to build theology on the Haskell comparison. 1The analogy earns its keep because it separates two questions that programmers often collapse:
- What happens inside the computation?
- What can an observer learn from the returned value?
Inside
ST, updates happen in sequence. A mutable reference can change. An array can be updated. The computation can use an imperative-looking algorithm. At the outer boundary, the only thing returned is the result, and the private state cannot escape through its type.That is a useful mental model for understanding why functional programming does not require every efficient implementation to allocate a fresh public object for every internal step. Immutability is an observable property of the interface and the values it exposes. It does not require the runtime representation to mimic the interface at every instant.
The analogy is also limited in a productive way. Haskell's guarantee is a programming-language property with a documented type signature. The Kabbalistic comparison is Snoyman's interpretation of two ideas from different domains. One can explain the other without validating it.
What the post leaves implicit about runST
The phrase "the mutation never escapes" can sound like a runtime promise, as if Haskell simply hides a mutable object by convention. The type is doing more work than that.
Suppose a computation tried to return the reference itself. The result would need to have a type shaped like
STRef s a, but runST requires a result that works for every s while returning an a that does not mention the private thread. There is no outside name for the particular s allocated by that invocation. The reference cannot be smuggled out as a usable value.That is the same reason two separate invocations of
runST have separate internal states. The s parameter is not a global label. It is a scoped type-level identity. The official documentation describes it as keeping internal states from different runST invocations separate from each other and from stToIO. 2This detail changes how to evaluate the analogy. The important image is not a magical place where mutation becomes morally or mathematically different. It is a sealed scope. The computation may be stateful inside that scope because the scope controls the only handles to the state.
The same pattern appears elsewhere in FP design: allow a powerful representation behind a narrow interface, then make it difficult or impossible for callers to observe the representation's invalid states.
ST is a particularly clean instance because the scope is reflected in the type.When this is a practical FP technique
The source post mentions a common pattern: create or obtain an immutable structure, work on a mutable version inside
ST, freeze the result, and return the immutable structure. 1 The exact choice of vector or array library is a separate engineering decision; the boundary principle is the part that generalizes.A useful review checklist is:
- Is the mutation local? The mutable reference or array should exist only for one algorithmic scope.
- Does the public result omit the state handle? If callers can retain a mutable reference, the containment argument has failed.
- Is the returned value the actual abstraction? The caller should receive the result it needs, not a wrapper that leaks implementation state.
- Is the reason concrete? Local mutation may simplify an update-heavy algorithm or reduce intermediate allocation. It should not be added merely because mutation feels familiar.
- Is the boundary easy to inspect? A small
runSTregion is easier to reason about than mutable state spread across a module.
This also clarifies what the post is not recommending. It is not saying that all mutation is harmless, that performance concerns automatically justify imperative code, or that
ST removes the need to understand evaluation and space behavior. Even the Data.STRef documentation warns that the lazy modifySTRef can accumulate thunks and cause a space leak, recommending the strict modifySTRef' when that behavior is unwanted. 3The safe conclusion is narrower: if mutation is useful, put it behind a boundary strong enough that the rest of the program can keep using the simpler model.
Why this is a good deep read
Snoyman's post is not a tutorial on
ST, and it does not pretend to be. It starts with a performance problem, gives enough Haskell background to make the analogy accessible, then uses a personal religious connection to ask whether "change" has to mean overwriting an earlier state. The result is an essay whose technical value sits in the transition between levels of description.For an FP reader, the best takeaway is concrete. Pure interfaces and mutable implementations are not opposites when the implementation state is scoped, typed, and unable to escape.
runST gives that idea a compact form: do stateful work in a private thread, return the value, and leave the thread behind.That is the boundary worth remembering, whether or not the spiritual analogy stays with you.
Related content
- Sign in to comment.