How to combine and then branch in MonadPlus/Alternative

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.

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]

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)