[Haskell-cafe] Stacking monads

[Jonathan Cast]

On Thu, 2008-10-02 at 18:18 +0100, Andrew Coppin wrote:
> Consider the following beautiful code:
> 
>   run :: State -> Foo -> ResultSet State
> 
>   run_and :: State -> Foo -> Foo -> ResultSet State
>   run_and s0 x y = do
>     s1 <- run s0 x
>     s2 <- run s1 y
>     return s2
> 
>   run_or :: State -> Foo -> Foo -> ResultSet State
>   run_or s0 x y = merge (run s0 x) (run s0 y)
> 
> That works great. Unfortunately, I made some alterations to the 
> functionallity the program has, and now it is actually possible for 
> 'run' to fail. When this happens, a problem should be reported to the 
> user. (By "user" I mean "the person running my compiled application".) 
> After an insane amount of time making my head hurt, I disocvered that 
> the type "Either ErrorType (ResultSet State)" is actually a monad.

It's a monad if you can write a function

join :: Either ErrorType (ResultSet (Either ErrorType (ResultSet
alpha)))
     -> Either ErrorType (ResultSet alpha)

(which follows from being able to write a function

interleave :: Either ErrorType (ResultSet alpha)
           -> ResultSet (Either ErrorType alpha)

satisfying certain laws).  Otherwise not, as you noticed.

>  (Or 
> rather, a monad within a monad.) Unfortunately, this causes some pretty 
> serious problems:
> 
>   run :: State -> Foo -> Either ErrorType (ResultSet State)
> 
>   run_or :: State -> Foo -> Foo -> Either ErrorType (ResultSet State)
>   run_or s0 x y = do
>     rset1 <- run s0 x
>     rset2 <- run s1 y
>     return (merge rset1 rset2)
> 
>   run_and :: State -> Foo -> Foo -> Either ErrorType (ResultSet State)
>   run_and s0 x y = run s0 x >>= \rset1 -> rset1 >>= \s1 -> run s1 y
> 
> The 'run_or' function isn't too bad. However, after about an hour of 
> trying, I cannot construct any definition for 'run_and' which actually 
> typechecks. The type signature for (>>=) requires that the result monad 
> matches the source monad, and there is no way for me to implement this. 
> Since ResultSet *just happens* to also be in Functor,

It doesn't just happen to be one.  liftM is *always* a law-abiding
definition for fmap, when used at a law-abiding monad.  (This is why
posters here are always bringing up head-hurting category theory, btw.
Absorbing it sufficiently actually teaches you useful things about
Haskell programming.)

> I can get as far as
> 
>   run_and s0 x y = run s0 x >>= \rset1 -> fmap (\s1 -> run s1 y) rset1
> 
> but that still leaves me with a value of type ResultSet (Either 
> ErrorType (ResultSet State)) and no obvious way to fix this.

> At this point I am sorely tempted to just change ResultSet to include 
> the error functionallity I need. However, ResultSet is *already* an 
> extremely complicated monad that took me weeks to get working 
> correctly...

What does it look like?  Quite possibly it can be factored out into
smaller pieces using monad transformers.  (In which case adding error
handling is just sticking in another transformer at the right layer in
the stack --- that is, the layer where adding error handling works :).

> I'd really prefer to just layer error handling on the top. 
> But I just can't get it to work right. It's soooo fiddly untangling the 
> multiple monads to try to *do* any useful work.
> 
> Does anybody have any idea how this whole monad stacking craziness is 
> *supposed* to work?

No. [1]

But we know how it *can* work; this is what monad transformers exist to
do.  You want to either change ResultSet to be a monad transformer,
(which can admittedly be a major re-factoring, depending on what exactly
ResultSet is doing --- compare
http://haskell.org/haskellwiki/ListT_done_right to regular lists), or
you want the monad ErrorT ErrorType ResultSet.  Very little can be said
in general without knowing what ResultSet looks like.

jcc

[1] I've seen plenty of things that *claim* to be a general solution,
but they all seem to boil down to re-implementing everything in terms of
State (or State + Cont).  I'm not satisfied that's actually the right
way to solve these issues.