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
Sorry to reply to my own posting, but... AHA! I see now what's going on. The purpose of the rank-2 qualifier is to prevent STRefs from leaking outside of the runST call, and what the code does at the lowest level is that it passes around a token "state" object to force the compiler to correctly order the calculations. Very cool. :-) Cheers, Greg On Oct 2, 2009, at 4:08 PM, Gregory Crosswhite wrote:
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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Fri, 2009-10-02 at 20:00 -0700, Gregory Crosswhite wrote:
Sorry to reply to my own posting, but... AHA! I see now what's going on. The purpose of the rank-2 qualifier is to prevent STRefs from leaking outside of the runST call, and what the code does at the lowest level is that it passes around a token "state" object to force the compiler to correctly order the calculations. Very cool. :-)
Yep, you got it. If you like the details of this sort of thing there's a paper on it "Lazy Functional State Threads" by John Launchbury and Simon Peyton Jones. The lazy part can also let you do almost magical things. See for example Lennart Augustsson's Mersenne twister code: http://www.augustsson.net/Darcs/MT/MersenneTwister.hs It does all the work using a mutable ST array but the final output is a lazy list of random numbers. mersenneTwister :: Word32 -> [Word32] Internally, each time you demand the next random number, it is mutating the internal ST array. So you get the combination of the mutable state updates and nice lazy results. No 'unsafeBlah' in sight! Duncan
On Sat, Oct 3, 2009 at 1:57 AM, Duncan Coutts
Internally, each time you demand the next random number, it is mutating the internal ST array.
This is the same thing that the Statistics.RandomVariate code in the statistics package does, and it can be very fast: http://www.serpentine.com/blog/2009/09/19/a-new-pseudo-random-number-generat...
On Fri, 2 Oct 2009, Gregory Crosswhite wrote:
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?
participants (4)
-
Bryan O'Sullivan -
Duncan Coutts -
Gregory Crosswhite -
Henning Thielemann