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.

[hdgarrood]

Why not refine the hierarchy instead and get rid of unlawful instances?

I'd like to get rid of unlawful instances, but having an overly granular hierarchy is often just annoying in practice, and when you have too many laws-only classes in there I think that realistically most people will just ignore them and do what they need to to get things to compile (which often amounts to using inferred types). I think it adds ceremony, makes it harder to remember what all the classes are, and in practice doesn't provide very much additional safety or reasoning ability beyond what a simpler hierarchy would have given you.

Just to expand on what I was saying earlier: I think it's a serious problem that you have to provide an empty before you get access to useful functions like optional, many, some. I actually think that types like Effect, Aff, and parsers shouldn't provide an empty where that amounts to a failure with a useless error message, and I'd argue we shouldn't encourage these types to provide such instances by gating useful functions behind classes that require implementations of empty.

On reflection, I think optional can make sense for types which don't satisfy the left catch law. For example, imagine I'm testing a function whose type is Int -> Maybe Int -> Int:

testCases :: Array { x :: Int, y :: Maybe Int }
testCases = ado
  x <- [ 1, 2, 3 ]
  y <- optional [ 10, 20, 30 ]
  in { x, y }

On the right identity law: I think an important example of a type which fails it is pretty much any parsing library. For example, ParserT from parsing.

On the empty >>= f = empty law: I'm pretty sure it's redundant. See #51 (comment).

[hdgarrood]

Oh also, I'm pretty sure that f <$> empty = empty is redundant for more or less the same reason: map f empty = map id empty by parametricity, and map id empty = empty by the Functor law.

[kl0tl]

How do you feel about Alt instances for comonad transformers? They don’t seem absurd to me but to be fair I’ve never used any comonad transformer.

Keeping Alt a subclass of Functor rather than Applicative would also allow the class witnessing distributivity to depend only on Apply rather than Applicative.

That’s the only two practical reasons I can think of against restricting Alt superclass but I think they’re rather weak though, especially if you want to get rid of the distributivity law.

Also judging by the instances of Plus and Alternative I guess we wouldn’t lose much by merging them.

I would still have separate subclasses witnessing the left catch law and the right identity though:

-- (a <|> b) <|> c = a <|> (b <|> c)
class Applicative f <= Alt f where
  alt :: forall a. f a -> f a -> f a

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

-- empty <|> a = a
-- empty <*> f = empty
class Alt f <= Alternative f where
  empty :: forall a. f a

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

(Assuming the empty <*> f = empty annihilation law is also redundant.)

Then optional would be constrained by the class witnessing left catch but some and many only by Alt. People would then start with Alt or Alternative for simplicity but would be able to strenghten their constraints if they need the additional properties.

On reflection, I think optional can make sense for types which don't satisfy the left catch law.

The equations documenting optional assume the left catch law to hold:

optional empty = pure Nothing
optional (pure x) = pure (Just x)

We should perhaps add an equation for Array to illustrate the behaviour to expect for distributive types if you want to relax optional to Alt?

optional (pure x) = [Just x, Nothing]

On the right identity law: I think an important example of a type which fails it is pretty much any parsing library.

Oh my bad, I naively assumed that parsers being a composition of ExceptT and StateT they would satisfy that law but that’s indeed not the case.

[hdgarrood]

The empty <*> f = empty law isn’t redundant; you can write eg

newtype Backwards f a = Backwards (f a)

instance Apply f => Apply (Backwards f) where
  apply (Backwards f) (Backwards x) =
    Backwards $
      (\x’ f’ -> f’ x’) <$> x <*> f

and with an instance like that, empty <*> f won’t be true for many instances, like Parser or Effect, if the effects of f can be observed even though the whole computation can’t resolve with a value any more.

[kl0tl]

Oh right, that annihilation law should be witnessed by Alternative as you suggested then.

[JordanMartinez]

So, have we reached consensus on what should be done here? Or are we still discussing what to do?

[hdgarrood]

I don't think we have reached a consensus just yet. For example, I haven't yet looked into the question of Alt instances for monad transformers. Additionally, the question of whether we want empty to be a one-sided identity is not resolved.

We should perhaps add an equation for Array to illustrate the behaviour to expect for distributive types if you want to relax optional to Alt?

As it happens we did this already: purescript/purescript-maybe#45. I think the docs there probably do need a bit more thought now. optional empty = pure Nothing works in the presence of either left catch or empty being a left identity for <|>, but you're absolutely right that optional (pure x) = pure (Just x) relies on left catch and I think it should be removed. Shall we continue this discussion on the maybe repo, where this function lives?

I am now leaning towards only allowing empty when it is a two-sided identity for <|>. This is because for all of the types I can think of where empty is a left identity but not a right identity, I think it would be better not to have access to empty at all. Those are:

• parsing's ParserT (where empty is a parser which fails with the message "No alternative"),
• Effect, where (if a Plus instance existed), we would have to have empty be an action which immediately throws an error,
• Aff, for the same reason, although Aff does have Plus, and empty throws with the message "Always fails".
• ParAff, for the same reason

Note: I think a two-sided identiy for ParAff is possible if <|> were changed in the case where both arguments fail to produce the error of whichever branch failed earlier (rather than always the LHS's error, as I think it does now), and empty was parallel never. That change may be difficult to justify, of course.

The reason I'm not particularly keen on subclasses witnessing left catch versus distributivity is that all of the functions which work with an arbitrary Alt/Alternative can behave sensibly without needing to know whether we have a left catch instance or a distributivity instance, and therefore I don't see these subclasses ever being used:

• If we have empty as a two-sided identity, then I think guard always makes sense, and that includes both Array (a distributivity instance) and MaybeT m (a left catch instance)
• I think optional and choose :: forall f a b. Alt f => f a -> f b -> f (Either a b) make sense for every instance I can think of, apart from possibly Maybe
• some/many don't make sense in as many cases, but I think they do make sense for at least ParserT (left catch) and LogicT (distributivity)

[hdgarrood]

Note: I think a two-sided identiy for ParAff is possible if <|> were changed in the case where both arguments fail to produce the error of whichever branch failed earlier (rather than always the LHS's error, as I think it does now), and empty was parallel never.

On second thoughts this makes zero sense; if empty were parallel never then x <|> empty would never resolve in the case x failed. I think if <|> was going to admit a two-sided identity element then it would need to resolve immediately as soon as either operand resolves, whether that was with a success or with an error. That’s probably a much less useful operation, and a breaking change which is very difficult to justify.

[kl0tl]

Regarding comonad transformers: turns out they actually can have Applicative instances so Applicative f <= Alt f doesn’t preclude Alt instances for them, but only for Map k (which doesn’t seem so useful, unless maybe with choose, asum or a function Alt f => (a -> f b) -> f b).

The more I think of this, the more I agree with you, I feel like I initially missed the point. Thank you for taking the time to explain the matter and give so much good examples 🙇 So, to summarize, the proposal is to get away with the left catch and distributivity laws and this would leave us with the following (basically what you suggested in #63 (comment), minus the left catch law):

-- (a <|> b) <|> c = a <|> (b <|> c)
class Applicative f <= Alt f where
  alt :: f a -> f a -> f a

-- empty <|> a = a
-- a <|> empty = a
-- empty <*> f = empty
class Alt f <= Alternative f where
  empty :: forall a. f a

Edit: I opened purescript/purescript-maybe#51 to discuss the documentation of optional.

[joneshf]

My take on this—as the person that suggested the distributivity law—is that the underlying issue here is overly constraining values.

As @hdgarrood pointed out many times, requiring at least Control.Alternative.Alternative _ for things like Data.Array.many, Data.Array.some, or Data.Maybe.optional is a smell. These values are overconstrained in a way to feeds back into the data types we define later such that we want to define unlawful instances or change the hierarchy. Just because some value happens to use two different type classes that have a third class where they interact doesn't mean that value has to be constrained to require that third class. More concretely, Data.Array.many and Data.Array.some should both change to the type:

forall f a.
Control.Alt.Alt f =>
Control.Applicative.Applicative f =>
Control.Lazy.Lazy (f (Array a)) =>
f a ->
f (Array a)

There's nothing about these values that requires the extra type classes nor the laws those extra type classes provide. Loosening the constraints on values addresses the actual issue better than shuffling the hierarchy or changing the laws. Those two things can be an improvement, but neither addresses the underlying issue of overly constraining values.

Knowing which data types satisfy which laws is the useful part for us humans. Knowing that Effect.Aff.Aff _ only implements Control.Alt.Alt _ and Control.Plus.Plus _, but not Control.Alternative.Alternative _ is the important part about having these type classes. It's saying that Control.Alt.alt will not distribute over Control.Apply.apply for Effect.Aff.Aff _.

Overly constraining values and functions is not useful to us humans. It is exactly what leads to discussions like this, or any of the other issues linked in this one. It comes from good intentions, but almost every time we do it, it has bad consequences (like giving Control.Alternative.Alternative _ instances to data types that shouldn't have them).

All that to say, the fault isn't with the type class and its laws; the fault is with overly constraining things.

---

As far as shuffling the hierarchy goes, making Control.Applicative.Applicative _ a super class of Control.Alt.Alt _ is a similar overconstraining issue.

I get the explanations so far, and I understand how the discussion got to this point, but @kl0tl brought up an important point about the Control.Alt.Alt _ side of the hierarchy. To reiterate, Control.Apply.Apply _ and Control.Applicative.Applicative _ are to Data.Tuple.Tuple _ _ as Control.Alt.Alt _ and Control.Plus.Plus _ are to Data.Either.Either _ _. To rephrase, Control.Apply.Apply _ and Control.Applicative.Applicative _ are for combining products and Control.Alt.Alt _ and Control.Plus.Plus _ are for combining sums. The sum-side of the hierarchy shouldn't depend on the product-side any more than Data.Either.Either _ _ should depend on Data.Tuple.Tuple _ _. They're dual concepts, not derivative concepts.

With the current formulation, it does tend toward that because most times that a Control.Alt.Alt _ instance is implemented, the type also has a Control.Applicative.Applicative _ instance. But that's largely because we don't define enough Control.Alt.Alt _ instances. Case in point, there's no Control.Alt.Alt _ or Control.Plus.Plus _ instance for Data.Map.Map _. There's a perfectly reasonable implementation for Control.Alt.alt and Control.Plus.empty as Data.Map.union and Data.Map.empty, respectively. If we shuffle the hierarchy to make the sum-side depend on the product-side, we are prevented from defining these instances because there's no way to define a Control.Applicative.Applicative _ instance for Data.Map.Map _.

That seems to come from thinking about Control.Alt.Alt _ as being a higher-kinded semigroup. It colors our thoughts about whether a data type should implement Control.Alt.Alt _ in a way that our thoughts don't get colored for Control.Apply.Apply _. Put another way, if we leaned more heavily into the rhetoric that Control.Apply.Apply _ was a higher-kinded semigroup (which it is), we'd likely see many fewer instances for Control.Apply.Apply _ than we see now because thinking about things as a semigroup puts us in a certain mindset.

I think optional and choose :: forall f a b. Alt f => f a -> f b -> f (Either a b) make sense for every instance I can think of, apart from possibly Maybe

The reason choose makes sense for every instance is because it's the other formulation of Control.Alt.Alt _:

class (Data.Functor.Functor f) <= Choose f where
  choose ::
    forall a b.
    (Data.Either.Either a b -> c)
    f a ->
    f b ->
    f c

alt ::
  forall a f.
  Choose f =>
  f a ->
  f a ->
  f a
alt left right = choose go left right
  where
  go ::
    Data.Either.Either a a ->
    a
  go either = case either of
    Data.Either.Left a -> a
    Data.Either.Right a -> a

We made the product and sum sides explicit in the contravariant hierarchy. The main issue with the contravariant hierarchy is also overconstraining. We decided to make Data.Divide.Divide _ and Data.Divisible.Divisible _ super classes of Data.Decide.Decide _ and Data.Decidable.Decidable _, respectively.

An example of the problems that causes is the Data.Decide.Decide _ and Data.Decidable.Decidable _ instances for Data.Op.Op _ having superfluous Data.Semigroup.Semigroup _ and Data.Monoid.Monoid _ constraints. It means you can't use anything like Data.Op.Op Int _ (or any other custom/domain-specific data type where it can't have the superfluous constraints) with the sum-side of the contravariant hierarchy because Int lacks the superfluous constraints. You have to go through an extra layer of wrapping/unwrapping just to please the type checker for something that is never used in any of the implementation. If there's no sensible wrapper, you're plum out of luck.

What I'm suggesting here is that changing the hierarchy to have the sum-side be dependent on the product-side doesn't help us nearly as much as it seems like it should. But it does rule out valid instances, may require extra constraints for instances that already exist, and will break someone's code that cannot deal with the product-side.

---

As far as changing the law, I'd suggest we dump the whole type class. That would address the original concern, mitigate the underlying issue that keeps making these issues pop up, and not require a reshuffle in the hierarchy.

Empty type classes require a lot of diligence to use correctly. Because they're only about laws–not methods–they are only practical to define, not to constrain. It seems like there's two useful purposes to empty type classes: reasoning about the behavior of a specific data type as a human, rewriting code of any data types as a computer.

It's very nice to know that a specific data type behaves a certain way when you mix and match different type classes. It means we can more easily manually rewrite things when we need to. There's surely another way to communicate that concept without resorting to empty type classes.

On the code rewriting front, I don't really know of any tool that does something like that right now. It seems wishful to keep these empty classes for that regard. If the compiler ever gets support for that sort of thing, it would be the time to revisit the idea.

Empty type classes are sometimes used as a convenience for grouping constraints together. The issue is when we ascribe laws to the empty type class and then use that type class later as a convenience (like Control.Alternative.Alternative _). We're mixing concerns here: writing a few fewer lines of code, and requiring laws.

But, it doesn't even address the issue pointed out by @hdgarrood up above. Trying to use an empty type class to talk about multiple type classes at once means we either leave out useful combinations, or have an explosion of empty type classes for all combinations. Neither is a good situation to be in. Neither is actually necessary if we explicitly list out the actual required constraints and don't have to deal with empty type classes.

Given how much pain these empty type classes cause, it seems better overall if we don't use that pattern so much.

[kl0tl]

Keeping Alt and Plus as is but getting rid of Alternative would mean either dropping the annihilation law relating empty and <*> or adding it as an optional law to Plus for instances also satisfying Applicative. Would that be really better than witnessing the law with an Applicative subclass? It seems useful to guarantee remaining effects can’t be observed once a computation has failed so I’m assuming we’d like to keep it.

There’s also good theoretical reasons to have Applicative a superclass of Alt: that way we can talk about Alternative and Alt as progressively weaker right near-semirings (Alternative dropping the distributivity law and Alt the unit of the additive monoid and the annihilation law). This formulation feels closer to the common usage of both classes, which seems to be more about instances satisfying left catch than distributivity.

[rhendric]

Keeping Alt and Plus as is but getting rid of Alternative would mean either dropping the annihilation law relating empty and <*> or adding it as an optional law to Plus for instances also satisfying Applicative. Would that be really better than witnessing the law with an Applicative subclass? It seems useful to guarantee remaining effects can’t be observed once a computation has failed so I’m assuming we’d like to keep it.

As previously discussed, if we're in a monad, this guarantee is already provided by the monad laws (you get empty >>= f = empty from parametricity, and empty <*> x = empty follows from apply = ap). It seems to me the question should be whether it's useful to provide that guarantee in non-monadic contexts. I actually suspect it isn't—if you really care about the effects of the RHS of <*> being conditional on the LHS, you ‘ought’ to be working in a monad, as that's the abstraction for sequencing effects.

Am I wrong—does someone have a use case for wanting to guarantee annihilation in a functor that is Apply and Plus but not Monad? (For example, the Backward newtype in #63 (comment)—does this have a practical use, for which left annihilation would be desired?)

[kl0tl]

Data.Validation.Semigroup.V has an Applicative instance but no Monad and granted it doesn’t have Alt nor Plus instances either, but they would be lawful. This type doesn’t satisfy the annihilation law though, so it “over approximate” errors: empty <*> f gives you the errors of f even if empty actually aborts the computation.

Data.Map.Map would behave similarly (assuming we keep Alt a Functor subclass).

So the annihilation law enables us to talk about those applicative functors which can collect stuff along the path a branching computation actually took, without over extending to the whole taken branches.

I don’t know how useful this actually is but the difference in behaviour seems enough for me to suggest that we should keep the law.

[milesfrain]

Should we change f to x in the docs for the Annihilation law?

    Distributivity: (f <|> g) <*> x == (f <*> x) <|> (g <*> x)
    Annihilation: empty <*> f = empty      <-- original
    Annihilation: empty <*> x = empty      <-- proposed