Higher-order function

Encyclopedia : H : HI : HIG : Higher-order function

In mathematics and computer science, higher-order functions are functions which do at least one of the following:

take one or more functions as an input
output a function

In mathematics these are also known as operators or functionals. The derivative in calculus is a common example, since it maps a function to another function.

In the untyped lambda calculus, all functions are higher-order; in a typed lambda calculus, from which most functional programming languages are derived, higher-order functions are generally those with types containing more than one arrow. In functional programming, higher-order functions that return other functions are said to be curried.

The map function found in many functional programming languages is one example of a higher-order function. It takes a function f as an argument, and returns a new function which takes a list and applies the f to each element.

Other examples of higher-order functions include function composition, integration, and the constant-function function λx.λy.x.

Alternatives

Programming languages can achieve some of the same algorithmic results as are obtained through higher-order functions by dynamically executing code (sometimes called "Eval" or "Execute" operations) in the scope of evaluation. Unfortunately there are significant drawbacks to this approach:

The argument code to be executed is usually not statically typed; these languages generally rely on dynamic typing to determine the well-formedness and safety of the code to be executed.
The argument is usually provided as a string, the value of which may not be known until run-time. This string must either be compiled during program execution (using just-in-time compilation) or evaluated by interpretation, causing some additional overhead at run-time. In rare cases, this may actually result in faster overall execution because more information is available for optimization.

Macros can also be used to achieve some of the effects of higher order functions. However, macros usually cannot avoid the problem of variable capture; they may also result in large amounts of duplicated code, which can be more difficult for a compiler to optimize. Macros are generally not strongly typed, although they may produce strongly typed code.

Objects in an object-oriented programming environment can be used as higher order functions – a method of an object acts in many ways like a function, and a method may take objects (containing methods) as arguments or return objects with methods. Unfortunately, objects often carry additional run-time overhead compared to pure functions. Language syntax can introduce additional difficulties; an object must be created to hold any parameters that are functions, and any resulting function must also have an associated object.

Higher-order function

Alternatives

See also