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?

In addition to the good answers below, I'll give an interpretation reason. A straightforward conceptualisation of a list is a sequence of values, but you could instead interpret a list as a non-deterministic choice of values. With that interpretation, it's natural for `[] <|> [1] <|> [2,3]` to mean the same as `[1,2,3]`. — AndrewC, Jan 16 '13 at 22:58

score 4 · Answer 1 · answered Jan 07 '13 at 12:48

4

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

answered Jan 07 '13 at 12:48

Daniel Fischer

181,706
17
308
431

Thanks! An implementation like `a <||> b = if a == empty then b else a` would make the function general for all `Alternative`s though – Nikita Volkov Jan 07 '13 at 13:04
3

@NikitaVolkov Well, all `Alternative`s that are also `Eq`s. Some lists aren't. – dave4420 Jan 07 '13 at 13:05

score 4 · Answer 2 · answered Jan 07 '13 at 12:50

This is the intended behaviour. The Alternative class defines a monoid for applicative functors (hence the (Applicative f) => class constraint in the definition).

Alternative has the same relation to Applicative as MonadPlus has to Monad. It makes sense that the Alternative instance for lists gives the same behaviour as the MonadPlus instance for lists (and also the same behaviour as the Monoid instance for lists).

This isn't the only valid definition for a list monoid though. Your definition:

instance Monoid [a] where
  mempty = []
  [] `mappend` xs = xs
  xs `mappend` _  = xs

also satisfied the monoid laws (exercise: check this!) so you could either define a newtype

newtype Lst a = Lst { getLst :: [a] }

and make that into a Monoid/Alternative/etc instance, or just define your own function to do what you want, as in Daniel Fischer's answer.

You could also look at [this answer](http://stackoverflow.com/a/10168111/546084) by Edward Kmett. — Chris Taylor, Jan 07 '13 at 12:56

Satvik · Answer 3 · 2013-01-07T12:52:05.307

Alternative is just a monoid defined for applicative functors. So an instance of Alternative for an applicative functor is correct if it satisfies the monoid laws.

I don't know if there is a standard function to do that, but you can ofcourse implement your own function or define your own instance of alternative.

You can read more about them in typeclassopedia. Which explains all these typeclasses in detail along with their laws which are to be followed.

score 3 · Accepted Answer · answered Jan 07 '13 at 20:27

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.

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

4 Answers4