As elaborated below that comment, State isn't actually mutating anything, it's just hiding away the boiler plate of threading an extra parameter through your functions.
ST, on the other hand, is compiler magic akin to transients in Clojure - STRefs actually get mutated, below a pure context. But type magic ensures that STRefs can't persist across multiple "runs" of the ST value, so it still behaves like pure code. So it's actually a little less scary than Clojure's transients, although you're more likely to encounter the word "skolem".
