Can I avoid the Monad constraint in this Alternative based function?

Question

I've written the following function (using the these library):

import Control.Applicative (Alternative ((<|>)), optional)
import Data.These (These(..))

asumThese :: (Alternative f, Monad f) => f a -> f b -> f (These a b)
asumThese x y = optional x >>= \case
  Just x' -> maybe (This x') (These x') <$> optional y
  Nothing -> That <$> y

Is there a way I can remove the Monad constraint, or is there no way out of using bind?

My gut feeling says I can't avoid the Monad constraint here, but can anyone give me an intuition of why that is the case? Just so in the future I have a better sense of what sort of functions I likely need Monad and which ones I can generalise to Applicative and/or Alternative?

I sense it has something to do with needing Monad for sequencing, but I can't quite put my finger on it, because f <$> x <*> y parses things in a different sequence to f <$> y <*> x, so there's still sequencing in Applicative.

Answer 1

You need Monad m over Applicative m specifically when the action of one step depends on the return value of a previous step. The dependency of control on data is considered to capture the power of "sequencing". If you write (,) <$> x <*> y, that x executes/parses/whatevers before y is only a convention. For the right Applicative, y could have its effect before x, or y and x could be in parallel. In x >>= maybe (return Nothing) (fmap Just . y), it's not known whether y will execute until x has already finished. For >>=, sequencing is forced, not merely conventional.

In this case control does depend on data: if optional x returns Nothing, the next action is to run y, but if it returns Just x', the next action is optional y. That is, you only introduce a branch to allow y to fail if x succeeds. Thus, I don't think there's a (good) way to write this operation purely in terms of Alternative.

There is of course the really simple

asumThese x y = (These <$> x <*> y) <|> This <$> x <|> That <$> y

but this i) produces results in a different order (i.e. it introduces the Alternative effects differently, since the effects can't depend on the data anymore) and ii) is inefficient.

Answer 2

I think you may be looking for selective functors, an abstraction between applicative functors and monads.

import Control.Applicative
import Control.Selective
import Data.These

asumThese :: (Alternative f, Selective f) => f a -> f b -> f (These a b)
asumThese x y = branch
  (Left <$> x <|> pure (Right ()))
  ((\ b a -> maybe (This a) (These a) b) <$> optional y)
  (const . That <$> y)