Combining distinct-thread state monads?

[Graham Klyne]

[Reply thread moved to Haskell-cafe]

At 18:19 06/01/04 +1030, Dr Mark H Phillips wrote:
>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.

I'm not an expert in this, but I think what you are proposing is possible, 
to a point, possibly assuming that your monads have associated functions to 
combine and separate the monadic parts.

Hmmm, let's try something...

Given:

   combine  :: ma -> mb -> mab
   separate :: mab -> (ma,mb)

(where ma, mb, mab are the separate and combined state monads)

   f :: ma () -> mb () -> mc ()
   f a b =
     do { ma1 <- fa1 a  -- process state in a, returning ma1
                        -- fa1 :: ma -> mc ma
        ; mb1 <- fb1 b  -- process state in b, returning mb1
        ; let mab1 = combine ma1 mb1
        ; mab2 = fab mab1
        ; let (ma2,mb2) = separate mab2
        ; ma3 <- fa3 ma2  -- process state in ma2
        ; mb3 <- fb3 mb2  -- process state in mb2
        ; return (fc ma3 mb3)
        }

(This code is speculative, not tested in any way.)

In this case, a third monad is used to schedule the operations on the 
separate monads, so in that respect the entire sequence is performed in a 
composite monad, within which methods defined for the separate monads can 
be invoked.
To get the results, Monad 'mc' would need to provide a way to pick them out.

It looks as if the combined monad 'mab' is probably superfluous.  I think 
the composite monad 'mc' might be avoided, but some of the efficiency 
advantage of monads would be lost as the single-threading of each monad is 
potentially broken.

I think that this may be all be achieved more cleanly using the monad 
transformer libraries and 'lift' methods -- can a state transformer be 
applied to a state monad?

What I have noticed in my work with monads is that in most respects they 
can be treated just like any other value.  Although they look different, a 
do sequence is just a monad-returning function, and any monad-returning 
function may be a do sequence.

<aside>
In my own work, I was pleasantly surprised how easy it was to use a Parsec 
parser monad (effectively a state monad, I think) to parse some data and 
return a combined state+IO monad, effectively precompiling a script, which 
which could then be executed by applying the resulting monad to an initial 
state, all within an IO monad.  The code which does this can be seen at:
   http://www.ninebynine.org/Software/Swish-0.2.0/SwishScript.hs

The main parser declaration is:
   script :: N3Parser [SwishStateIO ()]
where 'script' is a Parsec parser monad which parses a script and returns a 
list of 'SwishStateIO ()' values, each of which is a combined state+IO monad.
</aside>

#g
--

>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.
>
>
>_______________________________________________
>Haskell mailing list
>Haskell at haskell.org
>http://www.haskell.org/mailman/listinfo/haskell

------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact