[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:44:15 UTC 2020


On second thought, my parser's ability to conditionally evaluate to `empty` is also suspicious, maybe a parser can only statically being `empty` or not?

But technically a parser can evaluate to `empty` or otherwise dynamically, which seems very confusing to me.


> On 2020-10-27, at 17:26, YueCompl via Haskell-Cafe <haskell-cafe at haskell.org> wrote:
> 
> 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 <mailto: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 <https://en.wikibooks.org/wiki/Haskell/Alternative_and_MonadPlus>
>> [2] https://wiki.haskell.org/MonadPlus <https://wiki.haskell.org/MonadPlus>
>> 
>> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20201027/620933b6/attachment.html>


More information about the Haskell-Cafe mailing list