Add laws to Alternative

[Twan van Laarhoven]

On 01/11/13 12:44, Nathan van Doorn wrote:
> Firstly, I don't see how IO is relevant here, it has neither a MonadPlus
> instance nor an Alternative instance.

You are right. I thought it was an instance with mzero=fail "foo" and 
mplus=catch. But I was apparently mistaken. Objection withdrawn.

> Secondly, the MonadPlus laws are documented in Control.Monad to be:
>
>     mzero >>= f = mzero
>     v >> mzero = mzero

I missed them, because they are written in the documentation of mzero rather 
than the documentation of the class where I expected them.

> Thirdly, the monoid laws are already documented. (<|>) must be "An associative
> binary operation", and empty "The identity of <|>". These are exactly the monoid
> laws. Perhaps they should be made more explicit, but that is a different issue.

Missed this as well.

> Fourthly, [] fulfils neither the left-distribution law or the left-catch law,
> and I doubt many people would be happy to lose []'s MonadPlus instance.

List does satisfy left distribution:

λ> (,) <$> ([1,2] <|> [3]) <*> [4,5]
[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]
λ> (,) <$> [1,2] <*> [4,5] <|> (,) <$> [3] <*> [4,5]
[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]
λ> quickCheck (\x y z -> ((,) <$> (x <|> y :: [Int]) <*> (z :: [Int]))
                       == (((,) <$> x <*> z) <|> ((,) <$> y <*> z)))
+++ OK, passed 100 tests.

See also http://www.haskell.org/haskellwiki/MonadPlus. Then law which it doesn't 
is right distribution.

Consider Maybe. it does satisfies left catch but not left distribution for 
MonadPlus. Since
   mplus (Just False >>= guard) (Just True >>= guard) = Just ()
while
   mplus (Just False) (Just True) >>= guard = Nothing

But for Alternative, you can't have the failure of the second argument of (<*>) 
depend on the first. So Maybe *does* satisfy left distribution for Alternative. 
IMO that makes it a good candidate law.


Twan

> I believe I have addressed all your issues. If I've missed something, please
> point it out to me.
>
> Nathan.
>
>
> On 1 November 2013 12:09, Twan van Laarhoven <twanvl at gmail.com
> <mailto:twanvl at gmail.com>> wrote:
>
>     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
>     <http://hackage.haskell.org/package/base-4.6.0.1/docs/Control-Monad.html#t:MonadPlus>
>     [2] http://www.haskell.org/__haskellwiki/MonadPlus
>     <http://www.haskell.org/haskellwiki/MonadPlus>
>     _________________________________________________
>     Libraries mailing list
>     Libraries at haskell.org <mailto:Libraries at haskell.org>
>     http://www.haskell.org/__mailman/listinfo/libraries
>     <http://www.haskell.org/mailman/listinfo/libraries>
>
>