How to combine and then branch in MonadPlus/Alternative

Question

I recently wrote

do
  e <- (Left <$> m) <|> (Right <$> n)
  more actions
  case e of
    Left x -> ...
    Right y -> ...

This seems awkward. I know that protolude (and some other packages) define

-- Called eitherP in parser combinator libraries
eitherA :: Alternative f => f a -> f b -> f (Either a b)

But even with that, it all feels a bit manual. Is there some nice pattern I haven't seen for tightening it up?

Answer 1

I just noticed that OP expressed this same idea in a comment. I'm going to post my thoughts anyway.

---

Coyoneda is a neat trick, but it's a little overkill for this particular problem. I think all you need is regular old continuations.

Let's name those ...s:

do
  e <- (Left <$> m) <|> (Right <$> n)
  more actions
  case e of
    Left x -> fx x
    Right y -> fy y

Then, we could instead have written this as:

do
  e <- (fx <$> m) <|> (fy <$> n)
  more actions
  e

This is slightly subtle — it's important to use <$> there even though it looks like you might want to use =<< so that the result of the first line is actually a monadic action to be performed later rather than something that gets performed right away.

Answer 2

You could perhaps do it like this:

do
  let acts = do more actions
  (do x <- m; acts; ...) <|> (do y <- n; acts; ...)

I don't know if that looks better to you.

(Of course this doesn't work out nicely if those more actions bind many variables)

Answer 3

This is way overthinking the question, but...

In your code, the types of each branch of the Either might be distinct, but they don't escape the do-block, because they are "erased" by the Left and Right continuations.

That looks a bit like an existential type. Perhaps we could declare a type which packed the initial action along with its continuation, and give that type an Alternative instance.

Actually, we don't have to declare it, because such a type already exists in Hackage: it's Coyoneda from kan-extensions.

data Coyoneda f a where       
    Coyoneda :: (b -> a) -> f b -> Coyoneda f a  

Which has the useful instances

Alternative f => Alternative (Coyoneda f)
MonadPlus f => MonadPlus (Coyoneda f)

In our case the "return value" will be itself a monadic action m, so we want to deal with values of type Coyoneda m (m a) where m a is the type of the overall do-block.

Knowing all that, we can define the following function:

sandwich :: (Foldable f, MonadPlus m, Monad m) 
         => m x 
         -> f (Coyoneda m (m a)) 
         -> m a
sandwich more = join . lowerCoyoneda . hoistCoyoneda (<* more) . asum 

Reimplementing the original example:

sandwich more [Coyoneda m xCont, Coyoneda n yCont]