Jan Stolarek | 30 Jan 13:21 2013
Picon

Monadic parser vs. combinator parser

I will be writing a parser in Haskell and I wonder how to approach the problem. My first thought 
was to use monadic parser, e.g. like the one described by Hutton and Meijer in "Monadic Parsing 
in Haskell" functional pearl. But then I stumbled upon this:

https://github.com/alephnullplex/cradle/tree/master/code/src/Lbach/Parser

Monadic parser seems extremely verbose and not very straightforward compared to this one. I 
started to wonder whether I should use monadic parser for the sake of it being monadic or should 
I just go with the combinator approach? Any thoughts will be appreciated before I shoot myself in 
the foot :)

Janek
Ertugrul Söylemez | 30 Jan 13:38 2013
Picon

Re: Monadic parser vs. combinator parser

Jan Stolarek <jan.stolarek <at> p.lodz.pl> wrote:

> I will be writing a parser in Haskell and I wonder how to approach the
> problem. My first thought was to use monadic parser, e.g. like the one
> described by Hutton and Meijer in "Monadic Parsing in Haskell"
> functional pearl. But then I stumbled upon this:
>
> https://github.com/alephnullplex/cradle/tree/master/code/src/Lbach/Parser
>
> Monadic parser seems extremely verbose and not very straightforward
> compared to this one. I started to wonder whether I should use monadic
> parser for the sake of it being monadic or should I just go with the
> combinator approach? Any thoughts will be appreciated before I shoot
> myself in the foot :)

A monadic parser /is/ a combinator parser.  The code you linked just
doesn't go as far as wrapping it up with a newtype and providing a monad
instance.

Monadic parsers aren't verbose, because there is the applicative style.
Let's rewrite this noisy example (assuming automatic backtracking):

    inParens c = do
        char '('
        x <- c
        char ')'
        return x

All monads are also applicative functors, which means that you can use
applicative style to write this one more nicely:
(Continue reading)

Stephen Tetley | 30 Jan 18:51 2013
Picon

Re: Monadic parser vs. combinator parser

On 30 January 2013 12:38, Ertugrul Söylemez <es <at> ertes.de> wrote:

>
> A monadic parser /is/ a combinator parser.  The code you linked just
> doesn't go as far as wrapping it up with a newtype and providing a monad
> instance.

Further, (+>) in the linked example is monadic bind and `result` is `return`.

The code looks more succinct than early Parser combinator libraries
(like Hutton / Meijer) because it defines quite a few more
combinators. Equivalents are available if you use say Parsec plus the
usual applicative combinators.
Jan Stolarek | 31 Jan 10:47 2013
Picon

Re: Monadic parser vs. combinator parser

Thanks for replies guys. I indeed didn't notice that there are monads and applicatives used in 
this parser. My thought that monadic parsers are more verbose came from Hutton's paper where the 
code is definitely less readable than in example I provided.

There is one more thing that bothers me. It is easy to write a parser that returns Nothing when 
parsing fails. But I can't figure out a way to add meaningful error messages so that the user 
knows where did the parsing fail. I experimented with using Either so that I can use Left to pass 
error messages but this turned out to be inflexible and clutered the code. I will be greatful for 
any ideas.

Janek
Ertugrul Söylemez | 31 Jan 11:07 2013
Picon

Re: Monadic parser vs. combinator parser

Jan Stolarek <jan.stolarek <at> p.lodz.pl> wrote:

> Thanks for replies guys. I indeed didn't notice that there are monads
> and applicatives used in this parser. My thought that monadic parsers
> are more verbose came from Hutton's paper where the code is definitely
> less readable than in example I provided.
>
> There is one more thing that bothers me. It is easy to write a parser
> that returns Nothing when parsing fails. But I can't figure out a way
> to add meaningful error messages so that the user knows where did the
> parsing fail. I experimented with using Either so that I can use Left
> to pass error messages but this turned out to be inflexible and
> clutered the code. I will be greatful for any ideas.

Remember that 'Either e' is also a monad. =)

Greets,
Ertugrul

--

-- 
Key-ID: E5DD8D11 "Ertugrul Soeylemez <es <at> ertes.de>"
FPrint: BD28 3E3F BE63 BADD 4157  9134 D56A 37FA E5DD 8D11
Keysrv: hkp://subkeys.pgp.net/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
(Continue reading)

Jan Stolarek | 31 Jan 14:17 2013
Picon

Re: Monadic parser vs. combinator parser

Dnia czwartek, 31 stycznia 2013, Ertugrul Söylemez napisał:
> Remember that 'Either e' is also a monad. =)
I remember - this makes the change from Maybe to Either very easy :) Still I found that adding 
error message to every combinator and function ads a lot of boilerplate. Also, I experince 
problem with granularity of the messages, e.g. a message like "digit expected" is too low-level 
not helpful without telling user that the problem was in the incorect date format.

Janek

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Doaitse Swierstra | 3 Feb 00:08 2013
Picon

Re: Monadic parser vs. combinator parser


On Jan 31, 2013, at 10:47 , Jan Stolarek <jan.stolarek <at> p.lodz.pl> wrote:

> Thanks for replies guys. I indeed didn't notice that there are monads and applicatives used in 
> this parser. My thought that monadic parsers are more verbose came from Hutton's paper where the 
> code is definitely less readable than in example I provided.
> 
> There is one more thing that bothers me. It is easy to write a parser that returns Nothing when 
> parsing fails. But I can't figure out a way to add meaningful error messages so that the user 
> knows where did the parsing fail. I experimented with using Either so that I can use Left to pass 
> error messages but this turned out to be inflexible and clutered the code. I will be greatful for 
> any ideas.

Use the uu-parsinglib library, which provides error messages, repairs your errors and using its idioms
definition you can even write:

inParens c = iI '(' c ')' Ii

I think you cannot get it shorter and with more functionality.

 Doaitse

> Janek
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
Jan Stolarek | 3 Feb 14:46 2013
Picon

Re: Monadic parser vs. combinator parser

Dnia niedziela, 3 lutego 2013, Doaitse Swierstra napisał:
> Use the uu-parsinglib library, which provides error messages, repairs your
> errors and using its idioms definition you can even write:
>
> inParens c = iI '(' c ')' Ii
>
> I think you cannot get it shorter and with more functionality.
>
>  Doaitse
Thanks Doaitse. I know about your parsing libraries and at some point I will switch to using them 
(or Parsec). But for now I am more interested in educating myself so I'm trying to write things 
from scratch.

Janek

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Sean Leather | 31 Jan 11:36 2013
Picon

Re: Monadic parser vs. combinator parser


On Wed, Jan 30, 2013 at 1:21 PM, Jan Stolarek wrote:
I will be writing a parser in Haskell and I wonder how to approach the problem.

Utrecht University has a course that covers this, among other things. You might find the slides and lecture notes useful:


Regards,
Sean
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
wren ng thornton | 31 Jan 23:38 2013

Re: Monadic parser vs. combinator parser

On 1/30/13 7:21 AM, Jan Stolarek wrote:
> I will be writing a parser in Haskell and I wonder how to approach the problem. My first thought
> was to use monadic parser, e.g. like the one described by Hutton and Meijer in "Monadic Parsing
> in Haskell" functional pearl. But then I stumbled upon this:
>
> https://github.com/alephnullplex/cradle/tree/master/code/src/Lbach/Parser
>
> Monadic parser seems extremely verbose and not very straightforward compared to this one.

Psst,

     result :: a -> Parser a
     (+>)   :: Parser a -> (a -> Parser b) -> Parser b

cf.

     return :: Monad parser => a -> parser a
     (>>=)  :: Monad parser => parser a -> (a -> parser b) -> parser b

You just lose the nice do-notation is all.

--

-- 
Live well,
~wren

Gmane