Why is Alternative concatenating lists instead of choosing the first non-empty one?

Question

From the class's name and usage in parsers and with Maybe I thought that it's behaviour would be to choose the first non-empty input from a <|> b <|> c. So I expected that for input

[] <|> [1] <|> [2, 3]

it would return the first non-empty list, i.e.:

[1]

but it actually just concats the whole thing, producing:

[1,2,3]

So I am wondering what's the reasoning behind such an implementation? Is it actually correct?

http://hackage.haskell.org/packages/archive/base/latest/doc/html/Control-Applicative.html#t:Alternative

P.S. Is there any standard function that does what I expected from Alternative?

Answer 1

When implementing an Alternative f (or MonadPlus f) instance, you have to select a monoid over f a and implement it using empty and <|>. For some structures, such as lists, there can be several possibilities. The most natural monoidal operation for lists is their concatenation (with [] being the identity element). Taking the first non-empty element, as you suggest, is also a possibility, but not as natural for lists. Your operation almost ignores the structure (the length) of lists, it only checks if a list is empty or not. And it doesn't add anything new, because this kind of monoidal operation is already available as Maybe's instance of Alternative, which is designed to represent (non)empty values.

This is also reflected in the instance of MonadPlus of []. As described on HaskellWiki, there are two possible sets of laws for instances of MonadPlus:

• Monoid + LeftZero + LeftDistribution - statisfied by []
• Monoid + LeftZero + LeftCatch - statisfied by Maybe, IO and STM.

If we chose your implementation of Alternative and MonadPlus, then we'd have only instances satisfying ... + LeftCatch, nothing satisfying LeftDistribution. And again, MonadPlus of [] wouldn't be very different from MonadPlus of Maybe. And we wouldn't have anything that would enable us to solve things like the send+more=money puzzle. So it's much more interesting to choose the mplus/<|> of [] to be concatenation.

Answer 2

The reason (well, one reason) is that it matches the MonadPlus instance.

As far as I can tell, it is desirable that when a type has instances for both, MonadPlus and Alternative, these instances match, since the relation of Alternative to Applicative is like the relation of MonadPlus to Monad.

For your desired behaviour, if you want to use Alternative, you need a newtype wrapper around lists, as a freestanding function, it is of course also easy to define.

[] <++ xs = xs
xs <++ _  = xs