Effective Haskell

Internal Mutability with ST

In the last section, you learned how to use a data structure to cache results from an expensive function call. That approach works extremely well for certain types of problems, but it lacks the flexibility we sometimes need when trying to optimize our programs. In some cases, we need a more general type of mutability.

Earlier in this book, you learned about IORefs as a way to get mutability. IORefs do give us access to mutability, but at the steep cost of needing to move our entire function into an IO action. In general, we’d rather avoid putting otherwise pure functions into IO, and from the perspective of an outside caller, a function like editDistance should remain pure even if it happens to use some mutable state ...