There are many points in the design space.

* There is a pure Semigroup1, which acts as an indexed semigroup, without the Applicative superclass, which is the Alt class in the semigroupoids package.

* There is a Alternative minus empty, which you've proposed here.

But then even within each of those options we have several choices.

The laws for how Applicative and Alternative relate are subject to all the same problems as the laws between Monad and MonadPlus and the situation doesn't get any better here. catch vs. right distribution rears its head all over again.

The empty laws, which get much more complicated on the Alternative front at least don't show up.

Finally, there is another discussion this proposal may actively interfere with that has frankly, a lot more traction: What to do with 'fail' in Monad. Lennart has been a rather vocal proponent about finally doing something about that situation. To produce a viable MonadFail story one very solid path would be to lift the question up to the Applicative level, at which point in time, moving fail to an mfail in side of a class that depends on Applicative may be a good home, but that is more or less switching to a unit-then-add-an-associative operation style, rather than this.

With Applicative as a superclass of Monad we were asking folks to adopt an abstraction they had already accepted and used for several years.

With Semigroup as a superclass of Monoid, the abstraction has already seen many years of productive use.

Haskell is remarkably bad at dealing with very fine-grained class hierarchies.

With all of that in mind, I'm personally -1 on this addition. I don't think it rises to the level of traction needed to ask everyone everywhere to change all the code that they have ever written that involves MonadPlus, when the design space remains as large as it is.

-Edward

On Sun, Apr 5, 2015 at 11:05 AM, Mario Blažević <blamario@ciktel.net> wrote:
On 03/29/2015 08:20 AM, Jeremy wrote:
The proposal to make Semigroup a superclass of Monoid was discussed a while
ago [1], and the conclusion was to "put this off until the dust has settled
from the AMP and FT changes".

    It has occurred to me that the Alternative class, which is pretty much a constructor version of Monoid, would benefit from the same treatment. The greatest difficulty seems to be in finding the name for the Semigroup-equivalent superclass of Alternative. For lack of imagination,I'll just call it Semigroup1:

   class Applicative f => Semigroup1 f where
      (<|>) :: f a -> f a -> f a
      some :: f a -> f [a]
      many :: f a -> f [a]

   class Semigroup1 f => Alternative f where
      empty :: f a

    The rationale for this change:

1. All the theoretical arguments for introducing Semigroup carry over with no change.

2. There are existing data types that could be made instances of Semigroup1, and not of Alternative. I have not performed any comprehensive survey, but QuickCheck's Gen type can provide one example:

   instance Semigroup1 Gen where
      f <|> g = oneof [f, g]

3. Most interesting instances of Alternative are various parser types. A parser type that doesn't define empty is a parser that cannot fail by construction. That makes intuitive sense. I can imagine some benefits from a set of parser combinators that generated two types, only one of which could fail. Fill in the blanks:

   instance Semigroup1 IrrefutableParser
   instance Alternative Parser

   token :: a -> Parser a
   optional :: Parser a -> IrrefutableParser (Maybe a)
   many0 :: Parser a -> IrrefutableParser [a]

    There are, of course, two important differences between the Monoid and Alternative situation. First, the Semigroup class already exists, if not in base. That only means the proposal outlined above requires more critique and bikeshedding.

    The other difference is that the Semigroup operator (<>) is different from the Monoid operator mappend. This is mostly an unfortunate backward compatibility issue, but it does have a benefit of allowing the two classes to exist independently for a while before they are brought together. If we really, *really* desire the same doubtful benefit for Alternative, we can use a new operator name for the Semigroup1 class (I refuse to provide one in this proposal) and then eventually stipulate (<|>) = i-refuse-to-provide-one-in-this-proposal.

    My preference, if available, would be to just move the <|> operator into the superclass in 7.12. It's such a perfect operator name. Without a new GHC extension, however, this would mean that every existing instance of Alternative would be broken in 7.12. Furthermore, there would be no way to write an Alternative instance valid in both 7.10 and 7.12 without CPP directives. The only saving grace here is that the Alternative instances are relatively few, and it may just be possible to coordinate all the changes.

    So, here's a question to all authors of parser libraries and everybody else that has defined Alternative instances: would you be able and willing to add CPP directives to your code for this purpose?

    For everybody else: this is a proposal, so vote on it.

_______________________________________________
Libraries mailing list
Libraries@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries