Comment by curtisf

Haskell has genuine mutable memory, through State and IO.

But even without it, you can emulate mutation in a pure language by threading a "heap" parameter through everything.

There's only at most a log factor of extra space and time required in most computing models to "update" a persistent map (though I'm not sure the best way to encode persistent maps directly in Turing machine tapes, which is the model this result is specifically about)