In mathematics and computer science, a higherorder function (also functional, functional form or functor; not to be confused with the functor concept in category theory) is a function that does at least one of the following:

takes one or more functions as arguments,

returns a function as its result.
All other functions are firstorder functions. In mathematics higherorder functions are also known as operators or functionals. The differential operator in calculus is a common example, since it maps a function to its derivative, also a function.
In the untyped lambda calculus, all functions are higherorder; in a typed lambda calculus, from which most functional programming languages are derived, higherorder functions are values with types of the form (\tau_1\to\tau_2)\to\tau_3.
Contents

General examples 1

Support in programming languages 2

Direct support 2.1

Alternatives 2.2

Function Pointers 2.2.1

Macros 2.2.2

Dynamic Code Evaluation 2.2.3

Objects 2.2.4

Defunctionalization 2.2.5

See also 3

References 4

External links 5
General examples
The map
function, found in many functional programming languages, is one example of a higherorder function. It takes as arguments a function f and a list of elements, and as the result, returns a new list with f applied to each element from the list. Another very common kind of higherorder 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 higherorder functions include fold, function composition, integration, and the constantfunction function λx.λy.y.x.
Support in programming languages
Direct support
The examples are not intended to compare and contrast programming languages, but to serve as examples of higherorder function syntax
In the following examples, the higherorder function twice
takes a function , and applies the function to some value twice. If twice
has to be applied several times for the same f
it preferably should return a function rather than a value. This is in line with the "don't repeat yourself" principle.
Python:
def twice (function):
return lambda x: function (function (x))
def f (x):
return x + 3
g = twice (f)
print g (7) # 13
print g (8) # 14
F#:
let twice f = f >> f
let f = (+) 3
twice f 7 > printf "%A" // 13
Haskell:
twice function = function . function
f = (subtract 3)
main = print (twice f 7)  1
Clojure:
(defn twice [function x]
(function(function x)))
(twice #(+ % 3) 7) ;13
In Clojure, "#" starts a lambda expression, and "%" refers to the next function argument.
Scheme:
(define (add x y) (+ x y))
(define (f x)
(lambda (y) (+ x y)))
(display ((f 3) 7))
(display (add 3 7))
In this Scheme example, the higherorder function (f x)
is used to implement currying. It takes a single argument and returns a function. The evaluation of the expression ((f 3) 7)
first returns a function after evaluating (f 3)
. The returned function is (lambda (y) (+ 3 y))
. Then, it evaluates the returned function with 7 as the argument, returning 10. This is equivalent to the expression (add 3 7)
, since (f x)
is equivalent to the curried form of (add x y)
.
Erlang:
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).
In this Erlang example, the higherorder 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 higherorder function or_else
/2 will return R
. Note that X
, Y
, and R
can be functions. The example returns false
.
JavaScript:
function ArrayForEach(array, func) {
for (var i = 0; i < array.length; i++) {
if (i in array) {
func(array[i]);
}
}
}
function log(msg) {
console.log(msg);
}
ArrayForEach([1,2,3,4,5], log);
In this JavaScript example, the higherorder function ArrayForEach
takes an array and a method in as arguments and calls the method on every element in the array. Although the method may or may not return a value, there is not mapping involved since mapping requires saving returned values to a list.
However, this could also be implemented using the map
function, which in Javascript can accept functions with no return value.
function log(msg) {
console.log(msg);
}
[1,2,3,4,5].map(log);
Alternatives
Function Pointers
Function pointers in languages such as C and C++ allow programmers to pass around references to functions. The following C code computes an approximation of the integral of an arbitrary function:
#include
double square(double x)
{
return x * x;
}
double cube(double x)
{
return x * x * x;
}
/* Compute the integral of f() within the interval [a,b] */
double integral(double f(double x), double a, double b, int n)
{
int i;
double sum = 0;
double dt = (b  a) / n;
for (i = 0; i < n; ++i) {
sum += f(a + (i + 0.5) * dt);
}
return sum * dt;
}
int main()
{
printf("%g\n", integral(square, 0, 1, 100));
printf("%g\n", integral(cube, 0, 1, 100));
return 0;
}
The qsort function from the C standard library uses a function pointer to emulate the behavior of a higherorder function.
Macros
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.
Dynamic Code Evaluation
In other imperative programming languages it is possible to achieve some of the same algorithmic results as are obtained through use of higherorder functions by dynamically executing code (sometimes called "Eval" or "Execute" operations) in the scope of evaluation. There can be 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 wellformedness 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 runtime. This string must either be compiled during program execution (using justintime compilation) or evaluated by interpretation, causing some added overhead at runtime, and usually generating less efficient code.
Objects
In objectoriented programming languages that do not support higherorder 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 added runtime overhead compared to pure functions, however, and added boilerplate code for defining and instantiating an object and its method(s). Languages that permit stackbased (versus heapbased) objects or structs can provide more flexibility with this method.
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).
Defunctionalization
Defunctionalization can be used to implement higherorder functions in languages that lack firstclass functions:
// Defunctionalized function data structures
template struct Add { T value; };
template struct DivBy { T value; };
template struct Composition { F f; G g; };
// Defunctionalized function application implementations
template
auto apply(Composition f, X arg) {
return apply(f.f, apply(f.g, arg));
}
template
auto apply(Add f, X arg) {
return arg + f.value;
}
template
auto apply(DivBy f, X arg) {
return arg / f.value;
}
// Higherorder compose function
template
Composition compose(F f, G g) {
return Composition {f, g};
}
int main(int argc, const char* argv[]) {
auto f = compose(DivBy{ 2.0f }, Add{ 5 });
apply(f, 3); // 4.0f
apply(f, 9); // 7.0f
return 0;
}
In this case, different types are used to trigger different functions through the use of overloading. The overloaded function in this example has the signature auto apply
.
See also
References
External links

Higherorder functions and variational calculus

Boost Lambda Library for C++

Higher Order Perl
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.