[Haskell-cafe] Stacking monads

[Reid Barton]

On Thu, Oct 02, 2008 at 06:18:19PM +0100, Andrew Coppin wrote:
>  run :: State -> Foo -> Either ErrorType (ResultSet State)
>
>  run_and :: State -> Foo -> Foo -> Either ErrorType (ResultSet State)
>  {- some Either-ified version of
>     run_and :: State -> Foo -> Foo -> ResultSet State
>     run_and s0 x y = do
>       s1 <- run s0 x
>       s2 <- run s1 y
>       return s2
>  -}

I'll assume for simplicity and concreteness that ResultSet = [].

> 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.  

That's right.  The type mismatches are telling you that there's a
situation you haven't thought about, or at least, haven't told us how
you want to handle.  Suppose run s0 x = Right [s1a, s1b, s1c] and
run s1a y = Left err, run s1b = Right [s2], run s1c = Left err'.  What
should the overall result of run_and s0 x y be?  Somehow you have to
choose whether it's a Left or a Right, and which error to report in
the former case.

For the [] monad, there is a natural way to make this choice: it's
encoded in the function sequence :: Monad m => [m a] -> m [a], where
in this setting m = Either ErrorType.  For your problem, it would
probably be a good start to write an instance of Traversable for the
ResultSet monad.  In general, one way to make the composition of two
monads m and n into a monad is to write a function n (m a) -> m (n a);
this is the sequence method of a Traversable instance for n.  Then you
can write join :: m (n (m (n a))) -> m (n a) as

m (n (m (n a))) --- fmap sequence ---> m (m (n (n a)))
                ------ join ---------> m (n (n a))
                ------ join ---------> m (n a).

Regards,
Reid Barton