Combining distinct-thread state monads?
Hi, I am still learning about monads. I have a problem in mind and am wondering whether state monads are able to solve it. The difficulty is that it would necessitate the interaction of two state threads and I'm not sure whether Haskell state monads allow this. Let me explain what I'm getting at. Consider two state threads. The first has each state being a non-negative int, thought of as a string of binary digits. The second thread has each state being a bool. Now I want to have a state monad which modifies both threads as follows. Consider input states i (the int thought of as binary string) and b (the bool), and output states i' and b'. b' = not (b && (i `mod` 2)) i' = i `div` 2 As you can see, both of these should be able to do update-in-place provided the above order is adhered to. We could achieve this using state monads where state is an (Int, Bool) pair. We would have one monad which did the first line, leaving i unchanged and a second monad which did the second line, leaving b' unchanged. But... what if before this interaction, the int thread and the bool thread were separate monads doing their own thing, and we just wanted to combine these threads briefly (using the above interaction) before letting the threads do their own thing again? Is this possible? Also, suppose we have previously defined an int thread monad which takes i, returns a value of i `mod` 2, and changes the state to i' = i `div` 2. Suppose also we have previously defined a bool thread monad which takes b, returns a nothing value, and changes the state to b' = not b. Can we use these two monads (each acting on different threads), to form a combined-interaction monad that does (same as before): b' = not (b && (i `mod` 2)) i' = i `div` 2 I hope this is possible. It would facilitate both code reuse and readability. However I fear that it is not, requiring one to instead explicitly rewrite the two separate thread monads into (Int, Bool) pair acting ones. Cheers, Mark.
Hello, your problem can be solved with StateT: (warning: untested code) First we want to execute two independent state threads: start1 :: Monad m => StateT Int m startOutput1 start1 = <definition as with State> start2 :: Monad m => StateT Bool m startOutput2 start2 = <definition as with State> After this there is a part where we want to use both states togeter: intermediate :: Monad m => startOutput1 -> startOutput2 -> StateT Int (StateT Bool m) intermediateOutput intermediate = ... In the definition of intermediate, the state monad functions like put and get act on the Int state. To access the Bool state, you have to lift the state monad functions, like in lift (put s) and lift get. Last but not least, we want both states to be processed independently again: end1 :: Monad m => intermediateOutput -> StateT Int m endOutput1 end1 = <definition as with State> end2 :: Monad m => intermediateOutput -> StateT Int m endOutput2 end2 = <definition as with State> Now we combine these transformers: whole :: Monad m => StateT Int (StateT Bool m) (endOutput1,endOutput2) whole = do startOutput1 <- start1 startOutput2 <- lift start2 intermediateOutput <- intermediate startOutput1 startOutput2 endOutput1 <- end1 intermediateOutput endOutput2 <- lift end2 intermediateOutput return endOutput1 endOutput2 We can run this state transformer by using the following utility function: runWhole :: Monad m => Int -> Bool -> m (((endOutput1,endOutput2),Int),Bool) runWhole initInt initBool = runStateT (runStateT whole initInt) initBool We can get the resulting outputs and states with the definition: Identity (((endOutput1,endOutput2),finalInt),finalBool) = runWhole initInt initBool Wolfgang Am Dienstag, 6. Januar 2004 08:49 schrieb Dr Mark H Phillips:
Hi,
I am still learning about monads. I have a problem in mind and am wondering whether state monads are able to solve it. The difficulty is that it would necessitate the interaction of two state threads and I'm not sure whether Haskell state monads allow this. Let me explain what I'm getting at.
Consider two state threads. The first has each state being a non-negative int, thought of as a string of binary digits. The second thread has each state being a bool.
Now I want to have a state monad which modifies both threads as follows. Consider input states i (the int thought of as binary string) and b (the bool), and output states i' and b'.
b' = not (b && (i `mod` 2)) i' = i `div` 2
As you can see, both of these should be able to do update-in-place provided the above order is adhered to. We could achieve this using state monads where state is an (Int, Bool) pair. We would have one monad which did the first line, leaving i unchanged and a second monad which did the second line, leaving b' unchanged.
But... what if before this interaction, the int thread and the bool thread were separate monads doing their own thing, and we just wanted to combine these threads briefly (using the above interaction) before letting the threads do their own thing again? Is this possible?
Also, suppose we have previously defined an int thread monad which takes i, returns a value of i `mod` 2, and changes the state to i' = i `div` 2. Suppose also we have previously defined a bool thread monad which takes b, returns a nothing value, and changes the state to b' = not b. Can we use these two monads (each acting on different threads), to form a combined-interaction monad that does (same as before):
b' = not (b && (i `mod` 2)) i' = i `div` 2
I hope this is possible. It would facilitate both code reuse and readability. However I fear that it is not, requiring one to instead explicitly rewrite the two separate thread monads into (Int, Bool) pair acting ones.
Cheers,
Mark.
Hi Wolfgang, Thanks for your informative reply. At first I didn't understand it, but a search on "StateT" lead me to the paper "Monad Transformers and Modular Interpreters" by Liang, Hudak and Jones, which clarified some of the ideas for me. The state transformer approach seems to have advantageous in that it provides a framework for building new monads from old, and accessing the components. One disadvantage is that it lacks symmetry in that one monad is arbitrarily chosen to sit inside the other. I found another approach mentioned called "stratification", developed by David Espinosa in his PhD thesis "Semantic Lego". I am finding it a little hard to read because he codes in Scheme, not Haskell, but it sounds promising and seems to preserve symmetry better. Are you (or others) aware of this kind of approach being used in Haskell? Cheers, Mark.
Am Donnerstag, 8. Januar 2004 03:20 schrieben Sie:
[...]
Thanks for your informative reply.
You're welcome.
[...]
One disadvantage is that it lacks symmetry in that one monad is arbitrarily chosen to sit inside the other.
Yes, I see this as a disadvantage, too.
I found another approach mentioned called "stratification", developed by David Espinosa in his PhD thesis "Semantic Lego". I am finding it a little hard to read because he codes in Scheme, not Haskell, but it sounds promising and seems to preserve symmetry better.
Are you (or others) aware of this kind of approach being used in Haskell?
Neither I know this approach nor I'm aware of a Haskell implementation of it.
Cheers,
Mark.
Wolfgang
Hi Mark,
The state transformer approach seems to have advantageous in that it provides a framework for building new monads from old, and accessing the components. One disadvantage is that it lacks symmetry in that one monad is arbitrarily chosen to sit inside the other.
You may want to read "composing monads" by Mark Jones and Luc Duponcheel. It specifies precisely what kind of laws should hold before monads can be composed. (and indeed, it also shows that not all monads are symetrical and can be arbitrarily composed!) <http://www.cse.ogi.edu/~mpj/pubs/composing.html> All the best, Daan Leijen.
participants (3)
-
Daan Leijen -
Dr Mark H Phillips -
Wolfgang Jeltsch