Higher-order function
From Wikipedia, the free encyclopedia
In mathematics and computer science, higher-order functions, functional forms, or functionals 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 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.
Contents |
[edit] Example
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 ( = (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).
(define (g x) (lambda (y) (+ x y))) (define a (g 7)) (display (a 3))
[edit] Alternatives
In limited imperative programming languages, software can 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. 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, and usually generating less efficient code.
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.
Programming languages that support function pointers as function parameters can emulate high-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; int i; // Sum 100 values of f(x) for x in [a,b] sum = 0.0; for (i = 0; i <= 100; i++) sum += (*f)(i/100.0 * (b - a) + a); return sum; }
Objects in the object-oriented programming paradigm 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. Objects often carry additional run-time overhead compared to pure functions, however. 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. However, languages that offer stack objects or structs (as opposed to just heap based) can make it easier to utilize an object as if it were a function too.
An example of using a simple stack based record in Freepascal 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).
