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
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] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university 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
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
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.
participants (4)
-
Brandon S. Allbery KF8NH -
Heinrich Apfelmus -
Jan Jakubuv -
Michael Mossey