# Higher-order function

In mathematics and computer science, a **higher-order function** (also **functional**, **functional form** or **functor**) is a function that does at least one of the following:

- takes one or more functions as arguments (i.e., procedural parameters),
- returns a function as its result.

All other functions are *first-order functions*. In mathematics higher-order functions are also termed *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 higher-order; in a typed lambda calculus, from which most functional programming languages are derived, higher-order functions that take one function as argument are values with types of the form .

## General examples

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 the 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, and integration.

## Support in programming languages

### Direct support

*The examples are not intended to compare and contrast programming languages, but to serve as examples of higher-order function syntax*

In the following examples, the higher-order 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
```

#### F#

```
let twice f = f >> f
let f = (+) 3
twice f 7 |> printf "%A" // 13
```

#### Haskell

```
twice :: (a -> a) -> (a -> a)
twice f = f . f
f :: Num a => a -> a
f = subtract 3
main :: IO ()
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 higher-order 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 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. The example returns `false`

.

#### JavaScript

```
var twice = function(f, v) {
return f(f(v));
};
var f = function(v) {
return v + 3;
};
console.log(twice(f, 7)); // 13
```

#### Go

```
func twice(f func(int) int, v int) int {
return f(f(v))
}
func main() {
f := func(v int) int {
return v + 3
}
twice(f, 7) // returns 13
}
```

Notice a function literal can be defined either with an identifier (*twice*) or anonymously (assigned to variable *f*). Run full program on Go Playground!

#### Scala

```
def twice(f:Int=>Int) = f compose f
twice(_+3)(7) // 13
```

#### Java (1.8+)

```
Function<Function<Integer, Integer>, Function<Integer, Integer>> twice = f -> f.andThen(f);
twice.apply(x -> x + 3).apply(7); // 13
```

#### Swift

```
func f(x:Int) -> Int {
return x + 3
}
func g(function: (x:Int) -> Int, paramX: Int) -> Int {
return function(x: paramX) * function(x: paramX)
}
g(f,paramX: 7)
```

#### Rust

```
// Take function f(x), return function f(f(x))
fn twice<A, F>(function: F) -> Box<Fn(A) -> A>
where F: 'static + Fn(A) -> A
{
Box::new(move |a| function(function(a)))
}
// Return x + 3
fn f(x: i32) -> i32 {
x + 3
}
fn main() {
let g = twice(f);
println!("{}", g(7));
}
```

#### C++

```
// Generic lambdas provided by C++14.
#include <iostream>
auto twice = [](auto f, int v)
{
return f(f(v));
};
auto f = [](int i)
{
return i + 3;
};
int main()
{
std::cout << twice(f, 7) << std::endl;
}
// Or, use std::function in C++11
#include <iostream>
#include <functional>
auto twice = [](const std::function<int(int)>& f, int v)
{
return f(f(v));
};
auto f = [](int i)
{
return i + 3;
};
int main()
{
std::cout << twice(f, 7) << std::endl;
}
```

#### ColdFusion Markup Language (CFML)

```
twice = function(f, v) {
return f(f(v));
};
f = function(v) {
return v + 3;
};
writeOutput(twice(f, 7)); // 13
```

#### PHP

```
$twice = function($f, $v) {
return $f($f($v));
};
$f = function($v) {
return $v + 3;
};
echo($twice($f, 7)); // 13
```

#### R

```
twice <- function(func) {
return(function(x) {
func(func(x))
})
}
f <- function(x) {
return(x + 3)
}
g <- twice(f)
> print(g(7))
[1] 13
```

### XACML

The XACML standard defines higher-order functions in the standard to apply a function to multiple values of attribute bags.

```
rule allowEntry{
permit
condition anyOfAny(function[stringEqual], citizenships, allowedCitizenships)
}
```

The list of higher-order functions is can be found here.

### 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 <stdio.h>
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 higher-order 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 via 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:

- 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 added overhead at run-time, and usually generating less efficient code.

#### Objects

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 added run-time overhead compared to pure functions, however, and added boilerplate code for defining and instantiating an object and its method(s). Languages that permit stack-based (versus heap-based) 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 higher-order functions in languages that lack first-class functions:

```
// Defunctionalized function data structures
template<typename T> struct Add { T value; };
template<typename T> struct DivBy { T value; };
template<typename F, typename G> struct Composition { F f; G g; };
// Defunctionalized function application implementations
template<typename F, typename G, typename X>
auto apply(Composition<F, G> f, X arg) {
return apply(f.f, apply(f.g, arg));
}
template<typename T, typename X>
auto apply(Add<T> f, X arg) {
return arg + f.value;
}
template<typename T, typename X>
auto apply(DivBy<T> f, X arg) {
return arg / f.value;
}
// Higher-order compose function
template<typename F, typename G>
Composition<F, G> compose(F f, G g) {
return Composition<F, G> {f, g};
}
int main(int argc, const char* argv[]) {
auto f = compose(DivBy<float>{ 2.0f }, Add<int>{ 5 });
apply(f, 3); // 4.0f
apply(f, 9); // 7.0f
return 0;
}
```

In this case, different types are used to trigger different functions via function overloading. The overloaded function in this example has the signature `auto apply`

.

## See also

- First-class function
- Combinatory logic
- Function-level programming
- Functional programming
- Kappa calculus - a formalism for functions which
*excludes*higher-order functions - Strategy pattern
- Higher order messages