definition of combinator

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

definition of combinator

Michael Mossey
Although I can use libraries like Parsec, I don't really understand what a
combinator is, theoretically. There is an article here

http://en.wikipedia.org/wiki/Combinator

with the statement "A combinator is a higher-order function that uses only
function application and earlier defined combinators to define a result
from its arguments."

Okay, so I believe a "higher-order function" is a function that takes
function(s) as its argument(s). I don't know what "uses only function
application" means. Application of what functions to what? Can someone give
a concrete example that's simple?

Thanks,
Mike
Reply | Threaded
Open this post in threaded view
|

definition of combinator

Brandon S Allbery KF8NH
On Aug 23, 2009, at 20:44 , Michael Mossey wrote:
> Although I can use libraries like Parsec, I don't really understand  
> what a combinator is, theoretically. There is an article here


Example:  in Parsec, "many" is a combinator which takes a parser as an  
argument and produces a parser that matches multiple successive copies  
of whatever the argument matches.  It doesn't need to know anything  
about its argument except that it's a parser.  This kind of function  
lets you build up complex but general parsers from smaller pieces.

--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [hidden email]
system administrator [openafs,heimdal,too many hats] [hidden email]
electrical and computer engineering, carnegie mellon university    KF8NH


-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 195 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/beginners/attachments/20090823/a5cb87bd/PGP.bin
Reply | Threaded
Open this post in threaded view
|

definition of combinator

Jan Jakubuv-2
In reply to this post by Michael Mossey
Hi Michael,

On Sun, Aug 23, 2009 at 05:44:27PM -0700, Michael Mossey wrote:
> "A combinator is a higher-order function that uses only function
> application and earlier defined combinators to define a result from its
> arguments."
>
> Okay, so I believe a "higher-order function" is a function that takes
> function(s) as its argument(s). I don't know what "uses only function
> application" means. Application of what functions to what?

Briefly, a combinator applies ?earlier defined combinators? to ?its
arguments?. But remember that a combinator's argument can be a function as
well, so it may become more complicated. Then it simply applies functions
(other combinators, combinator's arguments, library functions) to their
arguments (other combinators, combinator's arguments, library functions,
constants, ...).

Finally, I guess that the word ?only? suggests that it doesn't read any
parsed text by itself but it only calls (combine) other parsers.

Sincerely,
    Jan.



--
Heriot-Watt University is a Scottish charity
registered under charity number SC000278.

Reply | Threaded
Open this post in threaded view
|

definition of combinator

Michael Mossey
In reply to this post by Brandon S Allbery KF8NH


Brandon S. Allbery KF8NH wrote:

> On Aug 23, 2009, at 20:44 , Michael Mossey wrote:
>> Although I can use libraries like Parsec, I don't really understand
>> what a combinator is, theoretically. There is an article here
>
>
> Example:  in Parsec, "many" is a combinator which takes a parser as an
> argument and produces a parser that matches multiple successive copies
> of whatever the argument matches.  It doesn't need to know anything
> about its argument except that it's a parser.  This kind of function
> lets you build up complex but general parsers from smaller pieces.
>

What makes it a "combinator" and not a general function? The fact that it
takes only a function (parser) as input (no data) and produces only a
function? Is any function that takes only functions and produces a function
called a combinator?

Thanks,
Mike

Reply | Threaded
Open this post in threaded view
|

Re: definition of combinator

Heinrich Apfelmus
Michael Mossey wrote:

>
> Brandon S. Allbery KF8NH wrote:
>>
>> Example:  in Parsec, "many" is a combinator which takes a parser as an
>> argument and produces a parser that matches multiple successive copies
>> of whatever the argument matches.  It doesn't need to know anything
>> about its argument except that it's a parser.  This kind of function
>> lets you build up complex but general parsers from smaller pieces.
>
> What makes it a "combinator" and not a general function? The fact that
> it takes only a function (parser) as input (no data) and produces only a
> function? Is any function that takes only functions and produces a
> function called a combinator?

The term "combinator" is just another name for "function", but with a
special connotation. It mainly applies to functions building and
combining values of an abstract data type.

In particular, parsers are abstract. They are defined by the following
combinators

     return :: a -> P a
     (>>=)  :: P a -> (a -> P b) -> P b
     symbol :: P Char
     mzero  :: P a
     mplus  :: P a -> P a -> P a

and an observation function like

     run    :: P a -> String -> Maybe a

The above functions are called combinators because they make new parsers
from old ones. In contrast,  run  turns a parser into something else, so
it's not called "combinator".


Regards,
apfelmus

--
http://apfelmus.nfshost.com