Combining distinct-thread state monads?
Dr Mark H Phillips
mark at austrics.com.au
Thu Jan 8 12:38:37 EST 2004
On Tue, 2004-01-06 at 22:58, Graham Klyne wrote:
> 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.
Thanks for the below illustration of how this problem can be
approached. I think you are right, this approach could solve
my problem. The other solution seems to be, as you point out, the use
of monadic transformers. The problem I have with these is that one
would need to arbitrarily define one monad to be "inside" the other,
whereas your approach seems more symmetric. David Espinosa, in his
PhD thesis "Semantic Lego" seems to have a more symmetric transforming
approach which he calls "stratification". This looks promising, but
he uses Scheme not Haskell so it's a bit hard for me to understand
some parts.
Cheers,
Mark.
P.S. I'm not sure if I need to be subscribed to haskell-cafe to reply
on list. I guess I'll find out!
> 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
>
More information about the Haskell-Cafe
mailing list