[Haskell-cafe] Does it violate the laws of Alternative/Monoid to implement empty/mempty with mzero from MonadPlus?
olf at aatal-apotheke.de
Mon Oct 26 20:18:29 UTC 2020
I used to think that an Alternative is just an Applicative which is
also a Monoid but apparently there is no consensus about this [1,2].
Actually it kind of makes sense to make the 'empty' parser fail:
Consider the parser combinator
choice = Data.Foldable.asum = foldr (<|>) empty
which folds over a list of Alternatives. Its semantics can be regarded
analogous to 'any' for a list of Booleans, and in the latter the empty
list evaluates to False.
Put differently: The parser (p <|> q) matches at least as many inputs
than either p or q. Hence the neutral element for <|> ought to be the
parser that matches the least amount of inputs, but a parser that
succeeds on the empty string _does_ match some input. It would be the
neutral element for the monoid operation that concatenates parsers.
More information about the Haskell-Cafe