Add laws to Alternative

[Twan van Laarhoven]

On 01/11/13 11:42, Nathan van Doorn wrote:
> Proposal: add the following laws to the documentation of
> Control.Applicative.Alternative:
>
>   * empty <*> a = empty
>   * f <*> empty = empty
>
 > These laws correspond to the laws given in MonadPlus- if you take mzero =
 > empty and ap = (<*>), the ones in MonadPlus imply these- and I don't think
 > this proposal should be too controversial.

As far as I can see, the documentation for MonadPlus does not specify these laws 
anywhere [1,2].

Consider the IO monad. These laws claim that

     launchMissiles *> fail "empty" = fail "empty"

This is clearly *not* true.

--

If we add laws, I think we should first consider the much more reasonable monoid 
laws

     identity
       empty <|> a = a
       a <|> empty = a
     associativity:
       (a <|> b) <|> c = a <|> (b <|> c)

In the MonadPlus world, the controversial part is the choice between

     left distribution
       (f <|> g) <*> a = (f <*> a) <|> (g <*> a)

or

     left catch
       pure a <|> b = pure a

Your proposal would be

     left zero
       empty <*> a = empty
     right zero
       f <*> empty = empty

And as mentioned above, right zero is problematic. The fmap version should be 
okay though

      map zero
       f <$> empty = empty


Twan

[1] 
http://hackage.haskell.org/package/base-4.6.0.1/docs/Control-Monad.html#t:MonadPlus
[2] http://www.haskell.org/haskellwiki/MonadPlus