Add Alternative a.k.a ApplicativePlus as distinct from implicit Monoid and Applicative together

[rzeigler]

An Applicative with a Monoid instance gives rise to Alternative (Haskell) or ApplicativePlus (Scala) that is usually distinct from the Monoid formed from the semigroup of the augmented type. I was wondering if there should be an additional definition for a class like Alternative with a method name such as choice or or that is specifically an Applicative with a Monoid for the higher kind itself rather than proxying to the Semigroup instance.

In particular, I would love defined semantics for things like:

Option.None.or(Option.Some(1)) == Option.Some(1)

be defined rather than

Option.Some(1).concat(Option.Some(1)) 

complaining about no concat on a field.

[davidchambers]

I'm pleased to see this issue. Thank you for raising it, @arzig. :)

When defining S.and and S.or I realized it's not necessary for a type to define empty in order to have sensible AND/OR semantics. Either is an example of such a type.

Rather than require a type to provide an or method in order to be compatible with S.and and S.or, I decided to require a toBoolean method. For Maybe, this might be defined as:

Nothing.prototype.toBoolean = () => false;
Just.prototype.toBoolean = () => true;

In order to support XOR a type must provide empty. Consider xor(Right(42), Right(42)) if it's not immediately clear why this is necessary. Since Maybe provides empty, S.xor can operate on values of that type.

The hierarchy of type classes looks something this:

+-----------+         +--------+
| Semigroup |---------| Monoid |
+-----------+         +--------+
                                \
                                 \
                                  \
                                   +--------------+
                                   | AlternativeX |
                                   +--------------+
                                  /
                                 /
                                /
                 +-------------+
                 | Alternative |
                 +-------------+

This isn't quite accurate, though, since AlternativeX should not require concat.

[rzeigler]

Does xor on its own address that case of something like

Option.Some(1).or(Option.Some(2)) == Option.Some(1) 

though from something like a parser.

[davidchambers]

I don't follow, @arzig. I'm suggesting this XOR behaviour:

Option.Some(1).xor(Option.Some(2)) == Option.None()

Option can support AND, OR, and XOR. Are you asking whether AND and OR can be derived from XOR?

[rzeigler]

Incorrect parse of your comment. I apparently skipped the part mentioning and and or. Feel free to ignore that last bit.

[bergus]

an additional definition for a class like Alternative that is specifically an Applicative with a Monoid for the higher kind itself

Hm, how would you specify that?

Also, I don't really see what is wrong with just combining Applicative with Monoid. Are there any laws missing?
Afaics, all this boils down to the problem that there are two (or more?) conflicting Monoids for a certain type. Can't that happen to just any of our typeclasses? What is so special about alternatives?

[rzeigler]

There are conflicting monoids for many types. However, the semantics of the monoid exposed by Alternative in Haskell or Scala is useful in many cases when you may want to provide for recovery from the "zero" case. This comes up in parsing, but also, potentially when I want to provide alternative validations against an input via one of the types that provides those semantics.

[joneshf]

There was a decent amount of discussion in ps-land about the laws: purescript/purescript-control#6
In particular, this comment: purescript/purescript-control#6 (comment)

Also here, sanctuary-js/sanctuary#11 (comment)

[rzeigler]

#187 seems to cover what I was initially looking for when I opened this.