In mathematics and computer science, higher-order functions, functional forms, or functionals are functions which do at least one of the following:
All other functions are first-order functions. In mathematics higher-order functions 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 values with types of the form .
The map
function found in many functional programming languages is one example of a higher-order function. It takes as arguments a function f and a list of elements, and as result, returns a new list with f applied to each element from the list. Another very common kind of higher-order function in those languages which support them are sorting functions which take a comparison function as a parameter, allowing the programmer to separate the sorting algorithm from the comparisons of the items being sorted. The C standard function qsort
, is an example of this.
Other examples of higher-order functions include fold, function composition, integration, and the constant-function function λx.λy.x.
The following examples were not intended to compare and contrast programming languages, since each program performs a different task. Also, the idea of a "scripting language" is beyond the scope of this article.
Contents |
This Python script contains the higher-order function g() which takes a function as its first argument and returns a number. This example prints 100 ( g(f,7)= (7+3)×(7+3) ).
def f(x): return x + 3 def g(function, x): return function(x) * function(x) print g(f, 7)
In this Scheme example the higher-order function g() takes a number and returns a function. The function a() takes a number and returns that number plus 7. (e.g. a(3)=10).
In this Erlang example the higher-order function or_else/2 takes a list of functions (Fs) and argument (X). It evaluates the function F with the argument X as argument. If the function F returns false then the next function in Fs will be evaluated. If the function F returns {false,Y} then the next function in Fs with argument Y will be evaluated. If the function F returns R the higher-order function or_else/2 will return R. Note that X, Y and R can be functions. Example returns false.
or_else([], _) -> false; or_else([F | Fs], X) -> or_else(Fs, X, F(X)). or_else(Fs, X, false) -> or_else(Fs, X); or_else(Fs, _, {false, Y}) -> or_else(Fs, Y); or_else(_, _, R) -> R. or_else([fun erlang:is_integer/1, fun erlang:is_atom/1, fun erlang:is_list/1],3.23).
Programming languages that support function pointers as function parameters can emulate higher-order functions. Such languages include the C and C++ family. An example is the following C code which computes an approximation of the integral of an arbitrary function:
// Compute the integral of f() within the interval [a,b] double integral(double (*f)(double x), double a, double b) { double sum, dt; int i; // Numerical integration: 0th order approximation sum = 0.0; dt = (b - a) / 100.0; for (i = 0; i < 100; i++) sum += (*f)(i * dt + a) * dt; return sum; }
Another example is the function qsort from C standard library.
In other imperative programming languages it is possible to achieve some of the same algorithmic results as are obtained through use of higher-order functions by dynamically executing code (sometimes called "Eval" or "Execute" operations) in the scope of evaluation. There can be significant drawbacks to this approach:
Macros can also be used to achieve some of the effects of higher order functions. However, macros cannot easily 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.
In object-oriented programming languages that do not support higher-order functions, objects can be an effective substitute. An object's methods act in essence like functions, and a method may accept objects as parameters and produce objects as return values. Objects often carry additional run-time overhead compared to pure functions, however, as well as additional boilerplate code for defining and instantiating an object and its method(s). Languages that permit stack-based (as opposed to heap-based) objects or structs can provide more flexibility with this technique.
An example of using a simple stack based record in Free Pascal with a function that returns a function:
program example; type int = integer; Txy = record x, y: int; end; Tf = function (xy: Txy): int; function f(xy: Txy): int; begin Result := xy.y + xy.x; end; function g(func: Tf): Tf; begin result := func; end; var a: Tf; xy: Txy = (x: 3; y: 7); begin a := g(@f); // return a function to "a" writeln(a(xy)); // prints 10 end.
The function a()
takes a Txy
record as input and returns the integer value of the sum of the record's x
and y
fields (3 + 7).