The distributivity law for Alternative rules out effectful instances

[hdgarrood]

Alternative has this distributivity law:

• (f <|> g) <*> x == (f <*> x) <|> (g <*> x)

However, this law rules out a few instances, most notably "effectful" ones like Effect or Aff. For example:

f :: Aff (Unit -> Unit)
f = pure identity

g :: Aff (Unit -> Unit)
g = pure identity

x :: Aff Unit
x = log "hi" *> empty

for which (f <|> g) <*> x will log "hi" once, whereas (f <*> x) <|> (g <*> x) will log "hi" twice.

Note that Effect has no Alt instance right now (and therefore no Plus or Alternative either), whereas Aff does have all of those instances.

I think it would be good to decide whether we want to keep this law and say that the problem lies with Aff's instance, or condone the Aff instance by dropping the distributivity law from the Alternative class.

It would be useful to see a concrete example of a case where the distributivity law is useful for ensuring that something behaves sensibly, because I'm not aware of any (and I think Aff's instance is used quite widely in practice, and I'm not aware of this having had any real consequences).

If we did drop the Alternative distributivity law, we'd be left with just the annihilation law, empty <*> f = empty. I think this makes sense as a class: I'd argue it gives you exactly what you need to write a sensible version of guard, since the annihilation law ensures that subsequent effects after a failed guard are nullified, and you need pure from Applicative and empty from Plus (see also #62).

[garyb]

I'd be fine with either solution, but I think dropping the law is perhaps slightly better. As you noted the class still has a sensible with just the annihilation law. I don't actually know why we made it distributive. Almost certainly I read it somewhere else and copied it without thinking of or understanding the implications carefully enough.

[hdgarrood]

I think the distributivity law does make sense - since Alternative brings together two different hierarchies, it makes sense to require that they interact in some particular way.

I suppose we also could do what Haskell's semigroupoids does, and say that Alternative instances should satisfy either left distribution or "left catch":

Ideally, an instance of Alt also satisfies the "left distribution" law of MonadPlus with respect to <.>:

<.> right-distributes over <!>: (a <!> b) <.> c = (a <.> c) <!> (b <.> c)

But Maybe, IO, Either a, ErrorT e m, and STM satisfy the alternative "left catch" law instead:

pure a <!> b = pure a

There is a fair bit of consideration in #6 (comment) and https://stackoverflow.com/questions/13080606/confused-by-the-meaning-of-the-alternative-type-class-and-its-relationship-to/13081604#13081604 (which is linked by that comment in #6) but it seems like the "left catch" issue was overlooked.

[hdgarrood]

Actually no, I think the "left catch" issue was considered in #6:

This makes one ask, where does MonadOr fit into the picture? Well, I don't think it belongs in this part of the hierarchy. It seems like it has a purpose, but it's not for combining monoidal semantics with functorial strucures.

So it seems like the approach proposed there is to include the distribution law strictly, and declare that "left catch" instances should not be part of the hierarchy, and including instances for Maybe and Either was where we went wrong.

[hdgarrood]

Actually I think the Maybe instance is fine either way; it appears to satisfy both left catch and left distribution. https://try.purescript.org/?gist=2aeecbc58d3c8f686c3a02d7f9c83d24

[hdgarrood]

My gut feeling is that “left catch” instances are more useful in practice. For example, we just merged #58 which talks about how Alt instances often behave in a left catch-y way. Also, I think Data.Maybe.optional :: forall f a. Alt f => Applicative f => f a -> f (Maybe a) doesn’t make much sense without left catch. For f ~ Array, the optional function makes no sense to me whatsoever.

[hdgarrood]

MaybeT is another example of a "left catch" instance which doesn't obey distributivity but is useful in practice; see purescript/purescript-transformers#116

[kl0tl]

Doesn’t the distributivity law of MonadPlus implies the distributivity law of Alternative since ap and <*> have to agree? Perhaps we could drop the distributivity law from Alternative but have another class with an Alternative superclass for types satisfying both laws and then strenghten MonadZero superclass (or MonadPlus superclass if we remove MonadZero first)?

Also would it make sense to have a class with Applicative and Alt superclasses for types satisfying the left catch law? That way we could have instances of Alternative (without the distributivity law) and this class for MaybeT and strenghten Data.Maybe.optional constraints to the new class?

[hdgarrood]

I think the MonadPlus distributivity law probably does imply the Alternative distributivity law, yes. The only problem with the Alternative distributivity law is that I’m still not aware of any examples where it’s useful in practice. The same goes for the MonadPlus distributivity law too. I’d rather not have classes with these laws at all if we can’t justify them, really.

[hdgarrood]

As for a hierarchy for “left catch” behaviours, I think that that’s what the existing Alternative hierarchy de facto is right now, which makes adding new classes less appealing to me: I would rather keep the hierarchy simpler than support every edge case people can concoct. If people need to refer back to the docs every time because there are too many separate classes to keep them all in their head, I think that’s a problem.

On that note: having Alt basically just be higher-kinded Semigroup doesn’t really appeal to me very much either. I’m not aware of Alt being used for types which aren’t at least also Alternative (that is, which are also Applicative and satisfy either left catch or left distribution). Additionally, I think it’s a problem that there’s no class which brings <|> and Applicative together without requiring an identity element for <|>. I think a identity for <|> is an antipattern in most cases - for left catch instances, the identity element usually represents some kind of failure case, and when things fail you generally want a meaningful error message, but it is impossible for empty to provide one. This is an issue I’ve encountered in JSON parsing, and also in command line option parsing. (It probably applies to almost any kind of parsing.) So I feel like I’d like to consider just having two classes:

class Applicative f <= Alt f where
  alt :: forall a. f a -> f a -> f a

class Alt f <= Alternative f where
  empty :: forall a. f a

with Alt having the associativity and left catch laws, and Alternative having the annihilation and identity laws.

That brings up another example of law violations: empty probably isn’t a right identity for alt in many cases! x <|> empty usually equals empty for left catch instances if x represents some kind of failure, but if (alt, empty) is to form a monoid, then we should have x <|> empty = x. So perhaps Alternative should only have a left identity law - empty <|> x = x.

[garyb]

Interesting points. I had always considered Alternative hierarchy to be a Semigroup1 kinda thing in theory, but indeed I don't use it that way - I only really use it for catch/error handling style things with parsers and the like, and Aff.

[kl0tl]

I’m not aware of Alt being used for types which aren’t at least also Alternative

Did you mean Applicative here? Otherwise there’s an Alt instance for Either e but no Plus nor Alternative instance. There‘s also Map, which doesn‘t have an Applicative instance nor Alt or Plus instances but for which we could implement both Alt and Plus. I’ll try to find other counter examples.

There’s also good theoretical reasons to not tie Alt and Plus to Applicative because then Plus can be to Either what Applicative is to Tuple: a lax monoidal functor from a category with Either as the monoidal structure to the same category but with Tuple as the monoidal structure (whereas Applicative has Tuple as the monoidal structure in both categories). I mention this because this theoretical framework helped me understand the relationships between Alt, Plus, Apply, Applicative, Alternative and their contravariant analogues but I can get we might want to focus on the most practical use cases to simplify the hierarchy.

[natefaubion]

Just to be clear, Aff is only Alt and Plus. There is no Alternative instance because of distributivity. We left it in for ParAff because otherwise even Aff doesn't work with Parallel combinators! (Aff/ParAff is basically the only used instance of Parallel) That instance is just as dodgy though because it's effectful.

See also purescript/purescript-parallel#23 which I closed, but probably shouldn't be closed.

[hdgarrood]

Did you mean Applicative here? Otherwise there’s an Alt instance for Either e but no Plus nor Alternative instance. There‘s also Map, which doesn‘t have an Applicative instance nor Alt or Plus instances but for which we could implement both Alt and Plus.

I did mean Alternative, yeah. I'm aware that those instances can exist, but I don't think they're very practically useful: in the vast majority of cases <|> is used, I expect people are depending on Alternative-like behaviour (consciously or not). Therefore I would prefer that <|> always indicate some kind of monoidal associative operation which has some interaction with the type's Applicative instance, not just any semigroup. Doing this also simplifies the class hierarchy, which I consider a plus. I think the fact that many Plus instances aren't even monoids due to a lack of right identities strengthens the case for this approach, too.

I've just remembered about a few more Alternative instances which satisfy distributivity and don't satisfy left catch: Array, List, and LogicT. It would definitely be a shame to lose functions like guard and optional for these types, so maybe saying that instances should satisfy at least one out of left catch and distributivity isn't such a bad option?

[kl0tl]

maybe saying that instances should satisfy at least one out of left catch and distributivity isn't such a bad option?

Wouldn’t this make reasoning harder? Why not refining the hierarchy instead and get rid of unlawful instances?

Here’s what I’d like to do:

• Drop the right identity law from Plus so instances for Effect, Aff and ParAff are lawful:

-- empty <|> a = a
-- f <$> empty = empty
class Alt f <= Plus f where
  empty :: forall a. f a

• Witness the right identity with a new Plus subclass:

-- a <|> empty = a
class Plus f <= ??? f

This law holds for all the Plus instances I checked, except for Effect, Aff and ParAff.

• Drop the distributivity law from Alternative so instances for Effect, Aff, ParAff, Monad m => MaybeT m and (Monoid e, Monad m) => ExceptT e m are lawful:

-- empty <*> f = empty
class (Applicative f, Plus f) <= Alternative f

• Witness the left catch and distributivity laws with new Alternative subclasses:

-- pure a <|> b = pure a
class Alternative f <= ??? f

-- (f <*> a) <|> (g <*> a) = (f <|> g) <*> a
class Alternative f <= ??? f

Left catch is satisfied by Identity, Effect, Aff, ParAff, Maybe, Either e, MaybeT m, ExceptT e m, ??? m => ReaderT r m, ??? m => WriterT e m and ??? m => StateT s m.

Distributivity is satisfied by Identity, Maybe, Either e, Array, ??? => IdentityT m, ListT m, ??? m => ReaderT m, ??? m => WriterT m and ??? m => StateT m.

• Restrict the Alternative superclass of MonadZero to the class witnessing the distributivity law:

-- empty >>= f = empty
class (Monad m, ??? m) <= MonadZero m

• Relax guard to Alternative and optional to the class witnessing the left catch law.

---

Then if we consider that the distributivity laws don’t pull their weight we can even drop MonadPlus, MonadZero and the Alternative subclass witnessing it.