If you know anything about how the ST monad remain pure while allowing genuine mutation in an enclosing context, then it should be clear by the end of this article what the next step will be to fix the issue with the IntMap implementation. Basically the secret is to make sure that the references can never escape the context where they’re valid, and rank 2 types are used to ensure this. Cool stuff!
Yep, and I also plan to argue for its use more broadly. I hear about and have personally implemented this IntMap solution a few times thinking that I’d suffer the log(n) slowdown for more convenient types only to find out later that this API bug sill still bite.
To forward declare a conclusion to this series—references, such as those introduced in Mem—cannot be semantically meaningful without both threading and “regions”. Mem is thus a bit flawed as an interface. It tries to enforce threading by being a monad (which is insufficient, but I won’t actually explore that much ere) but does nothing to ensure that references cannot escape.