Combining monads (IEnumerable and Maybe as an example)

Question

I have a general question and a more specific case question.

How does one combine different monads in general? Does some combination of the monad operators allow easy composition? Or does one have to write ad-hoc methods to combine each possible pair of monads?

As a specific example, I wrote a Maybe monad. How would one go about using an IEnumerable<IMaybe<T>> ? Apart from manually digging in to the Maybe monad within the LINQ extensions (such as: if(maybe.HasValue)... within select clauses), is there a "monadic" way of combining the two with their respective Bind etc. monad operations?

Otherwise, if I have to write specific combining methods, is something like this the right way to go about it?

    public static IEnumerable<B> SelectMany<A, B>(this IEnumerable<A> sequence, Func<A, IMaybe<B>> func)
    {
        return from item in sequence
               let result = func(item)
               where result.HasValue
               select result.Value;
    }


    public static IEnumerable<C> SelectMany<A, B, C>(this IEnumerable<A> sequence, Func<A, IMaybe<B>> func, Func<A, B, C> selector)
    {
        return from item in sequence
               let value = item
               let maybe = func(item)
               where maybe.HasValue
               select selector(value, maybe.Value);
    }

Answer 1

Great question!

A monad transformer is a type which adds some functionality to an arbitrary base monad, while preserving monad-ness. Sadly, monad transformers are inexpressible in C# because they make essential use of higher-kinded types. So, working in Haskell,

class MonadTrans (t :: (* -> *) -> (* -> *)) where
    lift :: Monad m => m a -> t m a
    transform :: Monad m :- Monad (t m)

Let's go over this line by line. The first line declares that a monad transformer is a type t, which takes an argument of kind * -> * (that is, a type expecting one argument) and turns it into another type of kind * -> *. When you realise that all monads have the kind * -> * you can see that the intention is that t turns monads into other monads.

The next line says that all monad transformers must support a lift operation, which takes an arbitrary monad m and lifts it into the transformer's world t m.

Finally, the transform method says that for any monad m, t m must also be a monad. I'm using the entailment operator :- from the constraints package.

---

This'll make more sense with an example. Here's a monad transformer which adds Maybe-ness to an arbitrary base monad m. The nothing operator allows us to abort the computation.

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

nothing :: Monad m => MaybeT m a
nothing = MaybeT (return Nothing)

In order for MaybeT to be a monad transformer, it must be a monad whenever its argument is a monad.

instance Monad m => Monad (MaybeT m) where
    return = MaybeT . return . Just
    MaybeT m >>= f = MaybeT $ m >>= maybe (return Nothing) (runMaybeT . f)

Now to write the MonadTrans implementation. The implementation of lift wraps the base monad's return value in a Just. The implementation of transform is uninteresting; it just tells GHC's constraint solver to verify that MaybeT is indeed a monad whenever its argument is.

instance MonadTrans MaybeT where
    lift = MaybeT . fmap Just
    transform = Sub Dict

Now we can write a monadic computation which uses MaybeT to add failure to, for example, the State monad. lift allows us to use the standard State methods get and put, but we also have access to nothing if we need to fail the computation. (I thought about using your example of IEnumerable (aka []), but there's something perverse about adding failure to a monad which already supports it.)

example :: MaybeT (State Int) ()
example = do
    x <- lift get
    if x < 0
    then nothing
    else lift $ put (x - 1)

What makes monad transformers really useful is their stackability. This allows you to compose big monads with many capabilities out of lots of little monads with one capability each. For example, a given application may need to do IO, read configuration variables, and throw exceptions; this would be encoded with a type like

type Application = ExceptT AppError (ReaderT AppConfig IO)

There are tools in the mtl package which help you to abstract over the precise collection and order of monad transformers in a given stack, allowing you to elide calls to lift.