16

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?

dfeuer
  • 48,079
  • 5
  • 63
  • 167

3 Answers3

15

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.

DDub
  • 3,884
  • 1
  • 5
  • 12
  • 1
    Nice solution, it reminds me of the "return a command" trick which also uses nested actions: https://www.haskellforall.com/2021/10/the-return-command-trick.html – danidiaz Jan 25 '22 at 08:36
  • 3
    There is a difference these two code snippets, though: in the first one, `fx` can cleanly mention variables bound by `more actions`. – Daniel Wagner Jan 25 '22 at 19:55
  • 2
    @DanielWagner You're definitely right. It's possible to let `fx :: TypeOfM -> More -> Types -> m ()` and similarly for `fy`. Then, the last line would be `e p q` or something similar. If there are a lot of variables bound in `more actions`, this becomes ugly fast, but for just one or two, it can work out nicely. – DDub Jan 26 '22 at 20:09
  • @DanielWagner, that's true; at some point my original solution probably starts to look good. But in me original context, there were no variables bound. – dfeuer Jan 27 '22 at 14:50
10

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]
dfeuer
  • 48,079
  • 5
  • 63
  • 167
danidiaz
  • 26,936
  • 4
  • 45
  • 95
  • 4
    I kind of like it! It also seems to suggest a more elementary approach, which I think I like even more: `do { final <- (m <&> xCont) <|> (n <&> yCont); more; actions; final }` – dfeuer Jan 25 '22 at 00:16
  • @dfeuer Yeah, `Coyoneda` is overkill here. Keeping the initial action and the continuation separate using `Coyoneda` works, but nesting them is simpler and you don't need any extra types. – danidiaz Jan 25 '22 at 08:49
  • 1
    This actually looks really cool – at last an application of Yoneda reduction that serves a clear purpose and isn't just “trivial yet inscrutable”! Does this have a good category-theory explanation? `Alternative`/`MonadPlus` always seem a bit on the shadier side of Haskell's functor hierarchy. – leftaroundabout Jan 25 '22 at 08:56
  • 2
    @leftaroundabout IIRC, another use of `Coyoneda` is to make functors out of types like `IORef` that don't have the instance, by "stashing" the fmappings in the function component of `Coyoneda`. https://www.reddit.com/r/haskell/comments/5v33qk/forall_a_ioref_a_lens_a_b_is_a_useful_type_does/ddyxp6x/ – danidiaz Jan 25 '22 at 09:05
  • @leftaroundabout, there are some pretty cool things you can do with (Co)Yoneda and similar types in combination with generic traversals. Sadly I couldn't convince recent GHCs to optimize those well, but that's not their fault. (Join points vs. inlining. *Sigh*) – dfeuer Jan 25 '22 at 09:53
  • 1
    BTW, there's no need to use `hoistCoyoneda` here even if you use `Coyoneda`. You can lower first, at which point you're back on the elementary solution track. – dfeuer Jan 25 '22 at 10:00
6

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)

Noughtmare
  • 9,410
  • 1
  • 12
  • 38
  • 4
    That's only equivalent for instances satisfying left distribution, I believe, since it'll reserve judgement to see if the intermediate actions fail. – dfeuer Jan 24 '22 at 23:36
  • 1
    Could be good in those cases, but my (foolishly unspoken) context was left catch. – dfeuer Jan 25 '22 at 01:24