Re: Add laws to Alternative

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 mailto:twanvl@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#... http://hackage.haskell.org/package/base-4.6.0.1/docs/Control-Monad.html#t:Mo... [2] http://www.haskell.org/__haskellwiki/MonadPlus http://www.haskell.org/haskellwiki/MonadPlus _________________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org http://www.haskell.org/__mailman/listinfo/libraries http://www.haskell.org/mailman/listinfo/libraries