Eliminate/move class Alternative

[Ben Franksen]

Hi,

I propose to remove class Alternative and functions depending on it
(optional, some, and many) from Control.Applicative. They can be moved into
a separate module Control.Alternative if people desire such a class, but I
doubt that it has many useful applications, at least in its present form.

Rationale:

Although the idea behind Alternative, i.e. generalize some of the functions
commonly found in parser combinator libs, is a nice one, it doesn't work
too well in practice, /even/ for the case that has inspired it (namely
parsers).

This is mostly due to the class method 'empty'.

First of all, this is a bad name, /especially/ in the context of parsers,
where 'empty' intuitively means 'recognize the empty sequence of tokens'
which is definitely /not/ what Alternative's 'empty' means. (Indeed, this
is normally be the meaning of 'pure' from class Applicative.)

The 'empty' from Alternative rather means 'fail'. Yeah, I know that this
name is already taken by class Monad. Many names would be better
than 'empty', for instance 'none', or just 'failed'. (I'll stick
with 'none' in what follows.)

Second, and more important, is that some parser libs would like to, but
cannot offer a sensible implementation for it. For instance, any
error-correcting library of parser combinators (like those invented by
Swierstra & Duponcheel) need to construct a valid result even in case of a
failed parse. Thus, the user must be able to pass an argument to 'none'
which would be possible only if it had a function type, like in

class Alternative f where
  ...
  none :: a -> f a

However, even this wouldn't be enough in practice because typically you will
want to pass additional data, like an error message. How this can be
properly generalized is something that needs more thought.

Some of you might be tempted to say "if you don't like Alternative, just
don't use it". However, not using it means additional effort, as I /would/
like to use class Applicative /and/ the <|> operator with its intended
meaning, i.e. choice/alternative, and also the dependent functions
(optional, many, etc). So currently I have to explicitly hide all the
Alternative stuff, like this

  import Control.Applicative hiding (Alternative(..),optional,some,many)

which is not nice at all.

As a final point, class Alternative comes with no stated laws. While there
are a number of standard classes where laws don't make much sense (like,
e.g. Show, or Typeable), this is clearly not one of those cases: The docs
say Alternative is "a monoid on applicative functors". This suggests
associativity and left/right unit laws. However, this is most probably not
the whole story, i.e. how are <|> and the ill-named 'empty' supposed to
interact with the operations and laws for Applicative? Are we going to have
the same dilemma here, as with MonadPlus vs. MonadZero/MonadOr, whatever?

Conclusion:

In its current form, class Alternative looks like it has been hastily
cobbled together. Thus it has no place in Control.Applicative. Moving it
into its own separate module is the least we can do.

Cheers
Ben