[Haskell-cafe] Mutable data within a (non-IO) monad

[Gregory Crosswhite]

Hey everyone,

I am thinking about creating a particular data structure with an  
immutable and mutable version.  The key of my problem is that I would  
like the user to be able to work with a mutable version of the data  
within a non-IO monad and then get an immutable value at the end,  
allowing them to do stateful-like computation in pure code.  The key  
is that I need to enforce the ordering within the monad, but I can't  
do this using a state-transformer since the state doesn't actually  
change;  instead, the data structure is internally modified, but the  
original pointer is kept to it.

There are many data structures which already have this kind of  
functionality, such as STRefs and MArrays, however I am having trouble  
distilling from the source code what the best "trick" is to accomplish  
mutability of this form within a monad.  There seem to be at least a  
couple of strategies:  using "type-threading" with GHC's State# type,  
and using the ST monad with a rank-2 qualifier over the type of the  
state.

Do you all have any thoughts on ways to solve this problem, and/or a  
high-level explanation of what is going behind the scenes with STRefs  
and MArrays?

Thanks!

- Greg