Re: [Haskell-cafe] Does it violate the laws of Alternative/Monoid to implement empty/mempty with mzero from MonadPlus?

27 Oct 2020

      `try` won't work for me, as the next alternative would be `eof`, if the non-essential parts of input are not consumed, `eof` won't match.

The line for the MWE at https://github.com/complyue/dcp/blob/91616496e43d153ca8ae92c0d030b3cdc351fb6... https://github.com/complyue/dcp/blob/91616496e43d153ca8ae92c0d030b3cdc351fb6...

```hs
  arts    <- manyTill (scWithSemiColons >> artifactDecl) eof
```

And the artifact parser https://github.com/complyue/dcp/blob/91616496e43d153ca8ae92c0d030b3cdc351fb6... https://github.com/complyue/dcp/blob/91616496e43d153ca8ae92c0d030b3cdc351fb6...

```hs
artifactDecl :: Parser ArtDecl
artifactDecl = lexeme $ do
  artCmt <- optional immediateDocComment
  (eof >> empty) <|> do
    artBody <- takeWhileP (Just "artifact body")
                          (not . flip elem (";{" :: [Char]))
    if T.null $ T.strip artBody
      then empty -- this is not possible in real cases
      else return (artCmt, artBody)

```

The `eof >> empty` in above will cause the parsing to err out overall, because the line before it `optional immediateDocComment` has consumed some input.
...
On 2020-10-27, at 23:57, Li-yao Xia  wrote:
That sounds like a use case for "try". Is it not?
Li-yao
On 10/27/2020 11:38 AM, YueCompl wrote:
...
Li-yao, the issue my parser faces is unable to express an recoverable *error*, that though it consumed some whitespaces, it doesn't want to raise an unrecoverable error, `empty` is supposed to do that in my intuition, but Megaparsec considers it an unrecoverable error in this case.
Best regards,
Compl
...
On 2020-10-27, at 23:22, Li-yao Xia  wrote:
That law (v >> mzero = mzero) is controversial. It's near impossible to satisfy for slightly sophisticated monads. It's notably broken by `MaybeT` whose very purpose is to augment a monad with such an extra Alternative/MonadPlus capability (a concrete counterexample for that law can be found with `MaybeT (State s)`).
MonadPlus is there mainly for historical reasons, because it predates Applicative. Then Alternative was added because the operations turned out to be useful even for Applicatives that were not Monads. The presence of both seems to sugggest there ought to be a difference, but IMO they should just be considered the same and we should thus simply forget about MonadPlus. How would you document that Alternative and MonadPlus may have different  implementations anyway? Imagine if `Control.Monad.msum` and `Control.Applicative.asum` were not the same, how confusing that would be.
To add an error that can not be recovered from you can use `Maybe` or `Either` as the base monad for `ParsecT`: `ParsecT e s Maybe`, so `lift Nothing` fails with your "unparsable" semantics.
Li-yao
On 10/27/2020 6:33 AM, Jaro Reinders wrote:
...
Yeah, it seems Megaparsecs parser violates the MonadPlus laws:
...
...
> isRight $ parse ((char 'a' >> mzero) `mplus` char 'a') "" "a"
False
> isRight $ parse (mzero `mplus` char 'a') "" "a"
True
I've created an issue: https://github.com/mrkkrp/megaparsec/issues/430.
On 10/27/20 11:15 AM, YueCompl wrote:
Isn't  'u <*> empty = empty' resembles MonadPlus?
mzero >>= f  =  mzero
v >> mzero   =  mzero
Since ParsecT also has a MonadPlus instance, can we have different implementations of `empty` and `mzero` to have these 2 separate semantics expressible:
*) parse to ignored result from some input
*) un-parsable (input consumed or not is irrelevant as to err out anyway)
parse to no significant result
unparsable
consumed input
empty -> throw ??
mzero -> throw
no input consumed
empty -> nothrow
mzero -> throw
I'd much like the behavior above `empty -> throw ??` changed to `empty -> nothrow`
...
On 2020-10-27, at 17:47, Jaro Reinders  wrote:
The 'empty' value should always be the unit of <|>, that is specified in the documentation of the Alternative class. The problem starts when you build composite parsers. E.g. (char 'a' *> empty) does not need to be a unit of <|>. I thought of 'fixing' this by adding another law 'u <*> empty = empty', but that disregards all effects that u can have.
On 10/27/20 10:26 AM, YueCompl via Haskell-Cafe 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  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
>> 
>> 
> _______________________________________________
> 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.
_______________________________________________
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.
_______________________________________________
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.

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.