Add laws to Alternative
Twan van Laarhoven
twanvl at gmail.com
Fri Nov 1 13:08:31 UTC 2013
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] <|> ) <*> [4,5]
λ> (,) <$> [1,2] <*> [4,5] <|> (,) <$>  <*> [4,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
mplus (Just False >>= guard) (Just True >>= guard) = Just ()
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.
> I believe I have addressed all your issues. If I've missed something, please
> point it out to me.
> 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
> * 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
> empty <|> a = a
> a <|> empty = a
> (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)
> 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
>  http://www.haskell.org/__haskellwiki/MonadPlus
> Libraries mailing list
> Libraries at haskell.org <mailto:Libraries at haskell.org>
More information about the Libraries