It is tricky to give your question a straight answer. Considered in isolation, there is nothing fundamentally wrong with your proposed instance. Still, there are quite a few things that can be said in support of the existing Alternative
instance for lists.
Admittedly, it doesn't fit MonadPlus
as well, but I think that a small price to pay for salvation.
One problem with going down that route is that Alternative
is meant to capture the same general concept that MonadPlus
does, but in terms of Applicative
rather than Monad
. To quote a relevant answer by Edward Kmett:
Effectively, Alternative
is to Applicative
what MonadPlus
is to Monad
.
From that point of view, having mismatching Alternative
and MonadPlus
instances is confusing and misleading, much like the analogous situation with Applicative
and Monad
instances would be.
(A possible counter to this argument would be wondering why do we need to care about MonadPlus
anyway, given that it expresses the same concepts and offers essentially the same methods as Alternative
. It should be noted, though, that the MonadPlus
laws are stronger than the Alternative
ones, as the relevant interactions of its methods with the Monad
ones aren't expressible in terms of Alternative
. That being so, MonadPlus
still has meaning of its own, and a conceivable outcome of a hypothetical reform of the classes would be retaining it as a laws-only class, as discussed for instance in the final section of this answer by Antal Spector-Zabusky.)
Given such considerations, in what follows I will assume the continued relevance of MonadPlus
. That makes writing the rest of this answer much easier, as MonadPlus
is the original expression of the general concept in Haskell, and so it is pretty much necessary to refer to it while tracing the origin of the list instance of Alternative
.
It seems to me that this would make a nice (<|>)
, better than (++)
would. Choosing the first nonempty list feels more like what I would expect from a typeclass named Alternative
than concatenating lists.
Tracing the roots of MonadPlus
and Alternative
, though, shows that the concatenating list instance is not just well-established, but even paradigmatic. For instance, quoting the classic paper by Hutton and Meijer, Monadic parsing in Haskell (1998), p. 4:
That is, a type constructor m
is a member of the class MonadZero
if it is a member of the class Monad
, and if it is also equipped with a value zero
of the specified type. In a similar way, the class MonadPlus
builds upon the class MonadZero
by adding a (++)
operation of the specified type.
(Note that the authors do use (++)
as their name for mplus
.)
The notion mplus
captures here is that of non-deterministic choice: if computations u
and v
each have some possible results, the possible results of u `mplus` v
will be all of the possible results of u
and v
. The most elementary realisation of that is through MonadPlus
for lists, though the idea extends to cover other non-determinism monads, such as Hutton and Meijer's Parser
:
newtype Parser a = Parser (String -> [(a,String)])
To spin it another way, we might describe non-deterministic choice as inclusive disjunction, while the operation you propose is a form of (left-biased) exclusive choice. (It is worth noting that Hutton and Meijer also define (+++)
, a deterministic choice operator for their Parser
which is rather like your operator except that it only picks the first result of the first successsful computation.)
A further relevant observation: one of the monad transformers from transformers that doesn't have a mtl class counterpart is ListT
. That is so because the class which generalises the ListT
functionality is precisely MonadPlus
. Quoting a Gabriella Gonzalez comment:
MonadPlus
is basically the "list monad" type class. For example: cons a as = return a `mplus` as
and nil = mzero
.
Note that the brokenness of transformers' ListT
is not an issue. In general, the various formulations of ListT
-done-right are equipped with a concatenating MonadPlus
instance (examples: one, two, three).
So much for reasons why we might want to leave the Alternative []
and MonadPlus []
instances as they are. Still, this answer would be lacking if it didn't recognise that, as Will Ness reminds us, there are multiple reasonable notions of choice, and your operator embodies one of them.
The "official" laws (that is, the ones actually mentioned by the documentation) of Alternative
and MonadPlus
don't specify a single notion of choice. That being so, we end up with both non-deterministic (e.g. mplus @[]
) and deterministic (e.g. mplus @Maybe
) choice instances under the same Alternative
/MonadPlus
umbrella. Furthermore, if one chose to disregard my argument above and replace mplus @[]
with your operator, nothing in the "official" laws would stop them. Over the years, there has been some talk of reforming MonadPlus
by splitting it into classes with extra laws, in order to separate the different notions of choice. The odds of such a reform actually happening, though, don't seem high (lots of churn for relatively little practical benefit).
For the sake of contrast, it is interesting to consider the near-semiring interpretation, which is one of the reimaginings of MonadPlus
and Alternative
that might be invoked in a hypothetical class hierarchy reform. For a fully fleshed account of it, see Rivas, Jaskelioff and Schrijvers, A Unified View of Monadic and Applicative Non-determinism (2018). For our current purposes, it suffices to note the interpretation tailors the classes to non-deterministic choice by adding, to the monoid laws, "left zero" and "left distribution" laws for Alternative
...
empty <*> x = empty
(f <|> g) <*> x = (f <*> x) <|> (g <*> x)
... as well as for MonadPlus
:
mzero >>= k = mzero
(m1 `mplus` m2) >>= k = (m1 >>= k) `mplus` (m2 >>= k)
(Those MonadPlus
laws are strictly stronger than their Alternative
counterparts.)
In particular, your choice operator follows the purported Alternative
left distribution law, but not the MonadPlus
one. In that respect, it is similar to mplus @Maybe
. MonadPlus
left distribution makes it difficult (probably impossible, though I don't have a proof at hand right now) to drop any results in mplus
, as we can't tell, on the right hand side of the law, whether m1 >>= k
or m2 >>= k
will fail without inspecting the results of m1
and m2
. To conclude this answer with something tangible, here is a demonstration of this point:
-- Your operator.
(<?>) :: [a] -> [a] -> [a]
[] <?> ys = ys
xs <?> _ = xs
filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = xs >>= \x -> if p x then [x] else []
-- If MonadPlus left distribution holds, then:
-- filter' p (xs `mplus` ys) = filter' p xs `mplus` filter' p ys
GHCi> filter' even ([1,3,5] <|> [0,2,4])
[0,2,4]
GHCi> filter' even [1,3,5] <|> filter' even [0,2,4]
[0,2,4]
GHCi> filter' even ([1,3,5] <?> [0,2,4])
[]
GHCi> filter' even [1,3,5] <?> filter' even [0,2,4]
[0,2,4]