The ST monad permits local mutation inside an otherwise pure computation. Mutable state remains private to the computation, so its effects cannot be observed by unrelated code and the final result remains referentially transparent. section 14.0 section 14.2.3
The abstraction organizes mutable references around three guarantees:
- Allocates, reads, and writes cells through ST actions rather than exposing a naked mutable reference. section 14.2.2
- Tags each action and reference with a state-thread type S, which acts as authorization for accessing that state. section 14.2.2
- Runs only computations whose result does not contain S, preventing local references from escaping their state thread. section 14.2.3
Purely functional in-place quicksort
A quicksort computation can allocate an STArray, mutate it through swap and partition operations, and freeze it into a result. ST.run exposes only the sorted value, not the temporary array or its mutations. section 14.2.5
def quicksort(xs: List[Int]): List[Int] =
if xs.isEmpty then xs else ST.run([s] => () =>
for
arr <- STArray.fromList[s, Int](xs)
size <- arr.size
_ <- qs(arr, 0, size - 1)
sorted <- arr.freeze
yield sorted
)
Shows the complete shape of a pure quicksort: create a mutable array locally, sort it through ST actions, then freeze the result. section 14.2.5
