Applicative Parsec

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Applicative Parsec

Matthias Guedemann

Hi,

what is the benefit if you use Applicative for Parsec instead of Monad?

I wrote a converter from a textfile format to a csv file. In order to get more
familiar with Haskell I wrote it using Parsec.
At first I had some difficulties and the monadic version seemed easier, but now
it works as Applicative version and Parsec seems really straightforward.

For me, the Applicative version looks more functional and the monadic version
looks more imperative. It seems that Applicative is enough for Parsers (think I
remember a citation somewhere), but does it have a real advantage?

best regards,
Matthias






--
__________________________________________________________
                                            ___  __    __
Dipl. Inf. Matthias Guedemann              / __\/ _\  /__\
Computer Systems in Engineering           / /   \ \  /_\
Otto-von-Guericke Universitaet Magdeburg / /___ _\ \//__
Tel.: 0391 / 67-19359                    \____/ \__/\__/
__________________________________________________________
Reply | Threaded
Open this post in threaded view
|

Applicative Parsec

Brent Yorgey-2
On Fri, Nov 06, 2009 at 05:22:04PM +0100, Matthias Guedemann wrote:
>
> I wrote a converter from a textfile format to a csv file. In order to get more
> familiar with Haskell I wrote it using Parsec.
> At first I had some difficulties and the monadic version seemed easier, but now
> it works as Applicative version and Parsec seems really straightforward.
>
> For me, the Applicative version looks more functional and the monadic version
> looks more imperative.

Indeed; thta's a good way of putting it.  Applicative looks more
functional since it corresponds to function application, but a special
sort of function application that carries along some sort of
"context".

> It seems that Applicative is enough for Parsers (think I
> remember a citation somewhere), but does it have a real advantage?

The Monad interface gives strictly more power: it allows you to give
names to intermediate results, and *decide what to do* later based on
those intermediate results.  With Applicative, the actions that you
perform must be fixed ahead of time.

For example, consider parsing a file which contains a positive
integer, followed by that many letters.  For example,

  3xyz
  12abcdefghijkl

are two instances of this format.  In order to parse this, a monadic
interface is required, since the result of parsing the number must be
used to decide how many things to parse after that.

However, for *many* purposes, an Applicative parsing interface is all
you need.  And if Applicative is enough, it's usually nicer/more
elegant than Monad. (And using the least powerful/most general thing
that works for your purpose is usually good style anyway.)

-Brent
Reply | Threaded
Open this post in threaded view
|

Applicative Parsec

Deniz Dogan-3
2009/11/6 Brent Yorgey <[hidden email]>:

> On Fri, Nov 06, 2009 at 05:22:04PM +0100, Matthias Guedemann wrote:
>>
>> I wrote a converter from a textfile format to a csv file. In order to get more
>> familiar with Haskell I wrote it using Parsec.
>> At first I had some difficulties and the monadic version seemed easier, but now
>> it works as Applicative version and Parsec seems really straightforward.
>>
>> For me, the Applicative version looks more functional and the monadic version
>> looks more imperative.
>
> Indeed; thta's a good way of putting it. ?Applicative looks more
> functional since it corresponds to function application, but a special
> sort of function application that carries along some sort of
> "context".
>
>> It seems that Applicative is enough for Parsers (think I
>> remember a citation somewhere), but does it have a real advantage?
>
> The Monad interface gives strictly more power: it allows you to give
> names to intermediate results, and *decide what to do* later based on
> those intermediate results. ?With Applicative, the actions that you
> perform must be fixed ahead of time.
>
> For example, consider parsing a file which contains a positive
> integer, followed by that many letters. ?For example,
>
> ?3xyz
> ?12abcdefghijkl
>
> are two instances of this format. ?In order to parse this, a monadic
> interface is required, since the result of parsing the number must be
> used to decide how many things to parse after that.
>
> However, for *many* purposes, an Applicative parsing interface is all
> you need. ?And if Applicative is enough, it's usually nicer/more
> elegant than Monad. (And using the least powerful/most general thing
> that works for your purpose is usually good style anyway.)
>
> -Brent
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>

In Hughes' and Swierstra's paper "Polish Parsers, Step by Step" (2003)
it says that Parsec's monadic interface can not be used for online
production of results. I don't know why or whether this even is true
anymore.

--
Deniz Dogan
Reply | Threaded
Open this post in threaded view
|

Applicative Parsec

Matthias Guedemann
In reply to this post by Brent Yorgey-2

Hi Brent,

thanks for the illustrative example.  

> For example, consider parsing a file which contains a positive
> integer, followed by that many letters.  For example,
>
>   3xyz
>   12abcdefghijkl
>
> are two instances of this format.  In order to parse this, a monadic
> interface is required, since the result of parsing the number must be
> used to decide how many things to parse after that.

I see, but as long as I want to parse context free grammars, it is
sufficient?

> However, for *many* purposes, an Applicative parsing interface is all
> you need.  And if Applicative is enough, it's usually nicer/more
> elegant than Monad. (And using the least powerful/most general thing
> that works for your purpose is usually good style anyway.)

I agree, and EBNF practically translates itself (modulo some try lookaheads)

best regards,
Matthias
--
__________________________________________________________
                                            ___  __    __
Dipl. Inf. Matthias Guedemann              / __\/ _\  /__\
Computer Systems in Engineering           / /   \ \  /_\
Otto-von-Guericke Universitaet Magdeburg / /___ _\ \//__
Tel.: 0391 / 67-19359                    \____/ \__/\__/
__________________________________________________________
Reply | Threaded
Open this post in threaded view
|

Applicative Parsec

Brent Yorgey-2
On Fri, Nov 06, 2009 at 07:20:11PM +0100, Matthias Guedemann wrote:

>
> Hi Brent,
>
> thanks for the illustrative example.  
>
> > For example, consider parsing a file which contains a positive
> > integer, followed by that many letters.  For example,
> >
> >   3xyz
> >   12abcdefghijkl
> >
> > are two instances of this format.  In order to parse this, a monadic
> > interface is required, since the result of parsing the number must be
> > used to decide how many things to parse after that.
>
> I see, but as long as I want to parse context free grammars, it is
> sufficient?

Well, technically, if you want to be able to do any choice at all, you
need Alternative in addition to Applicative (this is what provides the
<|> choice operator).  But intuitively, yes, I expect that you should
be able to parse any context-free grammar using only Alternative.
 
-Brent
Reply | Threaded
Open this post in threaded view
|

Re: Applicative Parsec

Heinrich Apfelmus
In reply to this post by Matthias Guedemann
Matthias Guedemann wrote:

> Hi Brent,
>
> thanks for the illustrative example.  
>
>> For example, consider parsing a file which contains a positive
>> integer, followed by that many letters.  For example,
>>
>>   3xyz
>>   12abcdefghijkl
>>
>> are two instances of this format.  In order to parse this, a monadic
>> interface is required, since the result of parsing the number must be
>> used to decide how many things to parse after that.
>
> I see, but as long as I want to parse context free grammars, it is
> sufficient?

Yep. The monadic version can handle context-sensitive grammars.
Incidentally, this is why the Utrecht parsing libraries ( uu-parsinglib
) only offers an applicative interface.


Regards,
apfelmus

--
http://apfelmus.nfshost.com