[Haskell-cafe] Stacking monads

[Andrew Coppin]

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. (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, 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... 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?