Roman Cheplyaka roma at ro-che.info
Thu Jul 25 00:11:22 CEST 2013

```To construct such an example, you have to ask yourself: when can we get a
list of more than one element?

Consider this:

a = char 'a'

((a >> a) <|> a) >> a

Suppose that our input is "aa". The result of ((a >> a) <|> a) would be
the list

[('a', ""), ('a', "a")]

If you proceed with the first element of the list, the overall parse
will fail. It can only succeed if you then try the second element.

By the way, you shouldn't confuse Parsec (the library) with the general
concept of parser combinators or the implementation from the paper you
reference. The above parse would fail in Parsec as well, despite the
fact that Parsec allows backtracking.

Roman

* Kashyap CK <ckkashyap at gmail.com> [2013-07-24 08:38:53-0700]
> There is reference in the paper that empty list indicates failure...so
> could we just use it like Maybe? I'd like it very much if I could get
> an example of a missed match by not using the complete match.
>
> regards,
> Kashyap
>
> Sent from my Windows Phone
> From: Roman Cheplyaka
> Sent: 24/07/2013 8:19 PM
> To: C K Kashyap
> Subject: Re: [Haskell-cafe] Parsec question
> need lists at all?
>
> Roman
>
> * C K Kashyap <ckkashyap at gmail.com> [2013-07-24 19:56:29+0530]
> > Dear Cafe,
> >
> > I am trying to implement[1] parsec in go using the "Monadic Parser
> > Combinators" paper [2] . I've been able to implement "plus" "bind" and
> > "many"
> > While doing the implementation - I looked at bind closely
> >
> > bind :: Parser a -> (a -> Parser b) -> Parser b
> > p `bind` f = \inp -> concat [f v inp' | (v,inp') <- p inp]
> >
> > I wondered if the result needs the complete list - wouldn't just the first
> > successful value suffice?
> > Perhaps -
> > p `bind` f = \inp -> take 1 \$ concat [f v inp' | (v,inp') <- p inp]
> >
> > Will this miss out matches?
> >
> >
> > Regards,
> > Kashyap
> >
> > [1] https://github.com/ckkashyap/parsec/blob/master/parsec.go
> > [2] Monadic Parser Combinators: Graham Hutton, Erik Meijer
>
> > _______________________________________________