1998/03/01 by Chris Okasaki · 1 citation
Computer Science · Mathematics · #Logic, programming, and type systems #semigroups and automata theory #Formal Methods in Verification #Combinatory logic #Parsing #Order (exchange) #Function (biology) #Computer science #Parser combinator #Argument (complex analysis) #Functional programming #Programming language #Order type #Base (topology) #Mathematics #Discrete mathematics
paper · pdf · doi:10.1017/s0956796898003001
openalex publication_date 1998/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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 k th-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.