Hostname: page-component-7c8c6479df-ws8qp Total loading time: 0 Render date: 2024-03-26T19:46:10.851Z Has data issue: false hasContentIssue false

Even higher-order functions for parsing or Why would anyone ever want to use a sixth-order function?

Published online by Cambridge University Press:  01 March 1998

CHRIS OKASAKI
Affiliation:
School of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213, USA (e-mail: cokasaki@cs.cmu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A higher-order function is a function that takes another function as an argument or returns another function as a result. More specifically, a first-order function takes and returns base types, such as integers or lists. A kth-order function takes or returns a function of order k−1. Currying often artificially inflates the order of a function, so we will ignore all inessential currying. (Whether a particular instance of currying is essential or inessential is open to debate, but we expect that our choices will be uncontroversial.) In addition, when calculating the order of a polymorphic function, we instantiate all type variables with base types. Under these assumptions, most common higher-order functions, such as map and foldr, are second-order, so beginning functional programmers often wonder: What good are functions of order three or above? We illustrate functions of up to sixth-order with examples taken from a combinator parsing library.

Combinator parsing is a classic application of functional programming, dating back to at least Burge (1975). Most combinator parsers are based on Wadler's list-of-successes technique (Wadler, 1985). Hutton (1992) popularized the idea in his excellent tutorial Higher-Order Functions for Parsing. In spite of the title, however, he considered only functions of up to order three.

Type
FUNCTIONAL PEARL
Copyright
© 1998 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.