Is every Alternative Monad Filterable?

Question

The category of sets is both cartesian monoidal and cocartesian monoidal. The types of the canonical isomorphisms witnessing these two monoidal structures are listed below:

type x + y = Either x y
type x × y = (x, y)

data Iso a b = Iso { fwd :: a -> b, bwd :: b -> a }

eassoc :: Iso ((x + y) + z) (x + (y + z))
elunit :: Iso (Void + x) x
erunit :: Iso (x + Void) x

tassoc :: Iso ((x × y) × z) (x × (y × z))
tlunit :: Iso (() × x) x
trunit :: Iso (x × ()) x

For the purposes of this question I define Alternative to be a lax monoidal functor from Hask under the Either tensor to Hask under the (,) tensor (and no more):

class Functor f => Alt f
  where
  union :: f a × f b -> f (a + b)

class Alt f => Alternative f
  where
  nil :: () -> f Void

The laws are just those for a lax monoidal functor.

Associativity:

fwd tassoc >>> bimap id union >>> union
=
bimap union id >>> union >>> fmap (fwd eassoc)

Left unit:

fwd tlunit
=
bimap nil id >>> union >>> fmap (fwd elunit)

Right unit:

fwd trunit
=
bimap id nil >>> union >>> fmap (fwd erunit)

Here is how to recover the more familiar operations for the Alternative typeclass in terms of the coherence maps of the lax monoidal functor encoding:

(<|>) :: Alt f => f a -> f a -> f a
x <|> y = either id id <$> union (Left <$> x, Right <$> y)

empty :: Alternative f => f a
empty = absurd <$> nil ()

I define Filterable functors to be oplax monoidal functors from Hask under the Either tensor to Hask under the (,) tensor:

class Functor f => Filter f
  where
  partition :: f (a + b) -> f a × f b

class Filter f => Filterable f
  where
  trivial :: f Void -> ()
  trivial = const ()

Having for its laws just backwards lax monoidal functor laws:

Associativity:

bwd tassoc <<< bimap id partition <<< partition
=
bimap partition id <<< partition <<< fmap (bwd eassoc)

Left unit:

bwd tlunit
=
bimap trivial id <<< partition <<< fmap (bwd elunit)

Right unit:

bwd trunit
=
bimap id trivial <<< partition <<< fmap (bwd erunit)

Defining standard filter-y functions like mapMaybe and filter in terms of the oplax monoidal functor encoding left as an exercise to the interested reader:

mapMaybe :: Filterable f => (a -> Maybe b) -> f a -> f b
mapMaybe = _

filter :: Filterable f => (a -> Bool) -> f a -> f a
filter = _

The question is this: is every Alternative Monad also Filterable?

We can type tetris our way to an implementation:

instance (Alternative f, Monad f) => Filter f
  where
  partition fab = (fab >>= either return (const empty), fab >>= either (const empty) return)

But is this implementation always lawful? Is it sometimes lawful (for some formal definition of "sometimes")? Proofs, counterexamples, and/or informal arguments would all be very useful. Thanks.

Personally, I'd be pretty surprised if it were always valid. It's certainly sometimes valid in the sense that there exist functors for which it's valid, but I tend to doubt that's a particularly interesting class. — dfeuer
@dfeuer Do you have any counterexamples in mind for which it's obviously not valid? Perhaps that would be instructive. — Asad Saeeduddin
I'm pretty sure this is always a lawful instance, just from unfolding the definitions and some trivial rewriting (thus suggesting that the Filterable laws are quite weak). @AsadSaeeduddin Consider picking up some interactive theorem proving skills so you can extend the "use types, not your brain" mentality to proofs too! — Li-yao Xia

duplode duplode · Accepted Answer · 2020-03-22T04:50:18

Here goes an argument which is broadly supportive of your beautiful idea.

Part one: mapMaybe

My plan here is restating the problem in terms of mapMaybe, hoping that doing so will bring us to more familiar ground. To do so, I will use a few Either-juggling utility functions:

maybeToRight :: a -> Maybe b -> Either a b
rightToMaybe :: Either a b -> Maybe b
leftToMaybe :: Either a b -> Maybe a
flipEither :: Either a b -> Either b a

(I took the first three names from relude, and the fourth from errors. By the way, errors offers maybeToRight and rightToMaybe as note and hush respectively, in Control.Error.Util.)

As you noted, mapMaybe can be defined in terms of partition:

mapMaybe :: Filterable f => (a -> Maybe b) -> f a -> f b
mapMaybe f = snd . partition . fmap (maybeToRight () . f)

Crucially, we can also go the other way around:

partition :: Filterable f => f (Either a b) -> (f a, f b)
partition = mapMaybe leftToMaybe &&& mapMaybe rightToMaybe

This suggests it makes sense to recast your laws in terms of mapMaybe. With the identity laws, doing so gives us a great excuse to forget entirely about trivial:

-- Left and right unit
mapMaybe rightToMaybe . fmap (bwd elunit) = id  -- [I]
mapMaybe leftToMaybe . fmap (bwd erunit) = id   -- [II]

As for associativity, we can use rightToMaybe and leftToMaybe to split the law in three equations, one for each component we get from the successive partitions:

-- Associativity
mapMaybe rightToMaybe . fmap (bwd eassoc)
    = mapMaybe rightToMaybe . mapMaybe rightToMaybe  -- [III]
mapMaybe rightToMaybe . mapMaybe leftToMaybe . fmap (bwd eassoc)
    = mapMaybe leftToMaybe . mapMaybe rightToMaybe   -- [IV]
mapMaybe leftToMaybe . fmap (bwd eassoc)
    = mapMaybe leftToMaybe . mapMaybe leftToMaybe    -- [V]

Parametricity means mapMaybe is agnostic with respect to the Either values we are dealing with here. That being so, we can use our little arsenal of Either isomorphisms to shuffle things around and show that [I] is equivalent to [II], and [III] is equivalent to [V]. We are now down to three equations:

mapMaybe rightToMaybe . fmap (bwd elunit) = id       -- [I]
mapMaybe rightToMaybe . fmap (bwd eassoc)
    = mapMaybe rightToMaybe . mapMaybe rightToMaybe  -- [III]
mapMaybe rightToMaybe . mapMaybe leftToMaybe . fmap (bwd eassoc)
    = mapMaybe leftToMaybe . mapMaybe rightToMaybe   -- [IV]

Parametricity allows us to swallow the fmap in [I]:

mapMaybe (rightToMaybe . bwd elunit) = id

That, however, is simply...

mapMaybe Just = id

... which is equivalent to the conservation/identity law from witherable's Filterable:

mapMaybe (Just . f) = fmap f

That Filterable also has a composition law:

-- The (<=<) is from the Maybe monad.
mapMaybe g . mapMaybe f = mapMaybe (g <=< f)

Can we also derive this one from our laws? Let's start from [III] and, once more, have parametricity do its work. This one is trickier, so I'll write it down in full:

mapMaybe rightToMaybe . fmap (bwd eassoc)
    = mapMaybe rightToMaybe . mapMaybe rightToMaybe  -- [III]

-- f :: a -> Maybe b; g :: b -> Maybe c
-- Precomposing fmap (right (maybeToRight () . g) . maybeToRight () . f)
-- on both sides:
mapMaybe rightToMaybe . fmap (bwd eassoc)
  . fmap (right (maybeToRight () . g) . maybeToRight () . f)
    = mapMaybe rightToMaybe . mapMaybe rightToMaybe 
      . fmap (right (maybeToRight () . g) . maybeToRight () . f)

mapMaybe rightToMaybe . mapMaybe rightToMaybe 
  . fmap (right (maybeToRight () . g) . maybeToRight () . f)  -- RHS
mapMaybe rightToMaybe . fmap (maybeToRight () . g)
  . mapMaybe rightToMaybe . fmap (maybeToRight () . f)
mapMaybe (rightToMaybe . maybeToRight () . g)
 . mapMaybe (rightToMaybe . maybeToRight () . f)
mapMaybe g . mapMaybe f

mapMaybe rightToMaybe . fmap (bwd eassoc)
  . fmap (right (maybeToRight () . g) . maybeToRight () . f)  -- LHS
mapMaybe (rightToMaybe . bwd eassoc 
    . right (maybeToRight () . g) . maybeToRight () . f)
mapMaybe (rightToMaybe . bwd eassoc 
    . right (maybeToRight ()) . maybeToRight () . fmap @Maybe g . f)
-- join @Maybe
--     = rightToMaybe . bwd eassoc . right (maybeToRight ()) . maybeToRight ()
mapMaybe (join @Maybe . fmap @Maybe g . f)
mapMaybe (g <=< f)  -- mapMaybe (g <=< f) = mapMaybe g . mapMaybe f

In the other direction:

mapMaybe (g <=< f) = mapMaybe g . mapMaybe f
-- f = rightToMaybe; g = rightToMaybe
mapMaybe (rightToMaybe <=< rightToMaybe)
    = mapMaybe rightToMaybe . mapMaybe rightToMaybe
mapMaybe (rightToMaybe <=< rightToMaybe)  -- LHS
mapMaybe (join @Maybe . fmap @Maybe rightToMaybe . rightToMaybe)
-- join @Maybe
--     = rightToMaybe . bwd eassoc . right (maybeToRight ()) . maybeToRight ()
mapMaybe (rightToMaybe . bwd eassoc 
    . right (maybeToRight ()) . maybeToRight ()
      . fmap @Maybe rightToMaybe . rightToMaybe)
mapMaybe (rightToMaybe . bwd eassoc 
    . right (maybeToRight () . rightToMaybe) 
      . maybeToRight () . rightToMaybe)
mapMaybe (rightToMaybe . bwd eassoc)  -- See note below.
mapMaybe rightToMaybe . fmap (bwd eassoc)
-- mapMaybe rightToMaybe . fmap (bwd eassoc)
--     = mapMaybe rightToMaybe . mapMaybe rightToMaybe

(Note: While maybeToRight () . rightToMaybe :: Either a b -> Either () b is not id, in the derivation above the left values will be discarded anyway, so it is fair to strike it out as if it were id.)

Thus [III] is equivalent to the composition law of witherable's Filterable.

At this point, we can use the composition law to deal with [IV]:

mapMaybe rightToMaybe . mapMaybe leftToMaybe . fmap (bwd eassoc)
    = mapMaybe leftToMaybe . mapMaybe rightToMaybe   -- [IV]
mapMaybe (rightToMaybe <=< leftToMaybe) . fmap (bwd eassoc)
    = mapMaybe (letfToMaybe <=< rightToMaybe)
mapMaybe (rightToMaybe <=< leftToMaybe . bwd eassoc)
    = mapMaybe (letfToMaybe <=< rightToMaybe)
-- Sufficient condition:
rightToMaybe <=< leftToMaybe . bwd eassoc = letfToMaybe <=< rightToMaybe
-- The condition holds, as can be directly verified by substiuting the definitions.

This suffices to show your class amounts to a well-established formulation of Filterable, which is a very nice result. Here is a recap of the laws:

mapMaybe Just = id                            -- Identity
mapMaybe g . mapMaybe f = mapMaybe (g <=< f)  -- Composition

As the witherable docs note, these are functor laws for a functor from Kleisli Maybe to Hask.

Part two: Alternative and Monad

Now we can tackle your actual question, which was about alternative monads. Your proposed implementation of partition was:

partitionAM :: (Alternative f, Monad f) => f (Either a b) -> (f a, f b)
partitionAM
    = (either return (const empty) =<<) &&& (either (const empty) return =<<)

Following my broader plan, I will switch to the mapMaybe presentation:

mapMaybe f
snd . partition . fmap (maybeToRight () . f)
snd . (either return (const empty) =<<) &&& (either (const empty) return =<<)
    . fmap (maybeToRight () . f)
(either (const empty) return =<<) . fmap (maybeToRight () . f)
(either (const empty) return . maybeToRight . f =<<)
(maybe empty return . f =<<)

And so we can define:

mapMaybeAM :: (Alternative f, Monad f) => (a -> Maybe b) -> f a -> f b
mapMaybeAM f u = maybe empty return . f =<< u

Or, in a pointfree spelling:

mapMaybeAM = (=<<) . (maybe empty return .)

A few paragraphs above, I noted the Filterable laws say that mapMaybe is the morphism mapping of a functor from Kleisli Maybe to Hask. Since the composition of functors is a functor, and (=<<) is the morphism mapping of a functor from Kleisli f to Hask, (maybe empty return .) being the morphism mapping of a functor from Kleisli Maybe to Kleisli f suffices for mapMaybeAM to be lawful. The relevant functor laws are:

maybe empty return . Just = return  -- Identity
maybe empty return . g <=< maybe empty return . f
    = maybe empty return . (g <=< f)  -- Composition

This identity law holds, so let's focus on the composition one:

maybe empty return . g <=< maybe empty return . f
    = maybe empty return . (g <=< f)
maybe empty return . g =<< maybe empty return (f a)
    = maybe empty return (g =<< f a)
-- Case 1: f a = Nothing
maybe empty return . g =<< maybe empty return Nothing
    = maybe empty return (g =<< Nothing)
maybe empty return . g =<< empty = maybe empty return Nothing
maybe empty return . g =<< empty = empty  -- To be continued.
-- Case 2: f a = Just b
maybe empty return . g =<< maybe empty return (Just b)
    = maybe empty return (g =<< Just b)
maybe empty return . g =<< return b = maybe empty return (g b)
maybe empty return (g b) = maybe empty return (g b)  -- OK.

Therefore, mapMaybeAM is lawful iff maybe empty return . g =<< empty = empty for any g. Now, if empty is defined as absurd <$> nil (), as you have done here, we can prove that f =<< empty = empty for any f:

f =<< empty = empty
f =<< empty  -- LHS
f =<< absurd <$> nil ()
f . absurd =<< nil ()
-- By parametricity, f . absurd = absurd, for any f.
absurd =<< nil ()
return . absurd =<< nil ()
absurd <$> nil ()
empty  -- LHS = RHS

Intuitively, if empty is really empty (as it must be, given the definition we are using here), there will be no values for f to be applied to, and so f =<< empty can't result in anything but empty.

A different approach here would be looking into the interaction of the Alternative and Monad classes. As it happens, there is a class for alternative monads: MonadPlus. Accordingly, a restyled mapMaybe might look like this:

-- Lawful iff, for any f, mzero >>= maybe empty mzero . f = mzero
mmapMaybe :: MonadPlus m => (a -> Maybe b) -> m a -> m b
mmapMaybe f m = m >>= maybe mzero return . f

While there are varying opinions on which set of laws is most appropriate for MonadPlus, one of the laws no one seems to object to is...

mzero >>= f = mzero  -- Left zero

... which is precisely the property of empty we were discussing a few paragraphs above. The lawfulness of mmapMaybe follows immediately from the left zero law.

(Incidentally, Control.Monad provides mfilter :: MonadPlus m => (a -> Bool) -> m a -> m a, which matches the filter we can define using mmapMaybe.)

In summary:

But is this implementation always lawful? Is it sometimes lawful (for some formal definition of "sometimes")?

Yes, the implementation is lawful. This conclusion hinges on the empty being indeed empty, as it should, or on the relevant alternative monad following the left zero MonadPlus law, which boils down to pretty much the same thing.

It is worth emphasising that Filterable isn't subsumed by MonadPlus, as we can illustrate with the following counterexamples:

ZipList: filterable, but not a monad. The Filterable instance is the same as the one for lists, even though the Alternative one is different.
Map: filterable, but neither a monad nor applicative. In fact, Map can't even be applicative because there is no sensible implementation of pure. It does, however, have its own empty.
MaybeT f: while its Monad and Alternative instances require f to be a monad, and an isolated empty definition would need at least Applicative, the Filterable instance only requires Functor f (anything becomes filterable if you slip a Maybe layer into it).

Part three: empty

At this point, one might still wonder how big of a role empty, or nil, really plays in Filterable. It is not a class method, and yet most instances appear to have a sensible version of it lying around.

The one thing we can be certain of is that, if the filterable type has any inhabitants at all, at least one of them will be an empty structure, because we can always take any inhabitant and filter everything out:

chop :: Filterable f => f a -> f Void
chop = mapMaybe (const Nothing)

The existence of chop, though doesn't mean there will be a single nil empty value, or that chop will always give out the same result. Consider, for instance, MaybeT IO, whose Filterable instance might be thought of as a way to censor results of IO computations. The instance is perfectly lawful, even though chop can produce distinct MaybeT IO Void values that carry arbitrary IO effects.

On a final note, you have alluded to the possibility of working with strong monoidal functors, so that Alternative and Filterable are linked by making union/partition and nil/trivial isomorphisms. Having union and partition as mutual inverses is conceivable but fairly limiting, given that union . partition discards some information about the arrangement of the elements for a large share of instances. As for the other isomorphism, trivial . nil is trivial, but nil . trivial is interesting in that it implies there is just a single f Void value, something that holds for a sizeable share of Filterable instances. It happens that there is a MonadPlus version of this condition. If we demand that, for any u...

absurd <$> chop u = mzero

... and then substitute the mmapMaybe from part two, we get:

absurd <$> chop u = mzero
absurd <$> mmapMaybe (const Nothing) u = mzero
mmapMaybe (fmap absurd . const Nothing) u = mzero
mmapMaybe (const Nothing) u = mzero
u >>= maybe mzero return . const Nothing = mzero
u >>= const mzero = mzero
u >> mzero = mzero

This property is known as the right zero law of MonadPlus, though there are good reasons to contest its status as a law of that particular class.

Is every Alternative Monad Filterable?

1 Answers

Part one: mapMaybe

Part two: Alternative and Monad

Part three: empty