[Haskell-cafe] Does it violate the laws of Alternative/Monoid to implement empty/mempty with mzero from MonadPlus?
YueCompl
compl.yue at icloud.com
Tue Oct 27 09:26:27 UTC 2020
In [1], Alternative is said being most commonly considered to form a monoid, so that:
```hs
-- empty is a neutral element
empty <|> u = u
u <|> empty = u
```
In my particular case wrt Megaparsec, when the artifact parser evaluates to `empty` at eof, I suppose the outer `many` should evaluate to whatsoever previously parsed, but current implementation of Megaparsec makes it conditional:
*) in case the parser hasn't consumed any input, it works the way as expected
*) incase the parser has consumed some input (whitespaces), the outer `many` throws error
So can I say this is a violation regarding [1]?
Best regards,
Compl
> On 2020-10-27, at 04:18, Olaf Klinke <olf at aatal-apotheke.de> wrote:
>
> 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.
>
> Olaf
>
> [1] https://en.wikibooks.org/wiki/Haskell/Alternative_and_MonadPlus
> [2] https://wiki.haskell.org/MonadPlus
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20201027/503b3fd1/attachment.html>
More information about the Haskell-Cafe
mailing list