*Not to be confused with *Functor (category theory)*.*

” (WP)

In mathematics and computer science, a **higher-order function** 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. Higher-order functions should not be confused with other uses of the word “functor” throughout mathematics, see Functor (disambiguation).

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 {\displaystyle (\tau _{1}\to \tau _{2})\to \tau _{3}}.

## General examples

`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 collection of elements, and as the result, returns a new collection with*f*applied to each element from the collection.- 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. - filter
- fold
- apply
- Function composition
- Integration
- Callback
- Tree traversal
- Montague grammar, a semantic theory of natural language, uses higher-order functions

## 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.

#### APL

Further information: APL (programming language)

twice←{⍺⍺ ⍺⍺ ⍵} plusthree←{⍵+3} g←{plusthree twice ⍵} g 7 13

Or in a tacit manner:

twice←⍣2 plusthree←+∘3 g←plusthree twice g 7 13

#### C++

Further information: C++

Using `std::function`

in C++11:

#include<iostream>#include<functional>autotwice = [](conststd::function<int(int)>& f) {return[&f](int x) {returnf(f(x)); }; };autoplus_three = [](int i) {returni + 3; }; int main() {autog = twice(plus_three); std::cout << g(7) << '\n';// 13}

Or, with generic lambdas provided by C++14:

#include<iostream>autotwice = [](constauto& f) {return[&f](int x) {returnf(f(x)); }; };autoplus_three = [](int i) {returni + 3; }; int main() {autog = twice(plus_three); std::cout << g(7) << '\n';// 13}

#### C#

Further information: C Sharp (programming language)

Using just delegates:

usingSystem;publicclassProgram{publicstaticvoidMain(string[] args) { Func<Func<int, int>, Func<int, int>> twice = f => x => f(f(x)); Func<int, int> plusThree = i => i + 3; var g = twice(plusThree); Console.WriteLine(g(7));// 13} }

Or equivalently, with static methods:

usingSystem;publicclassProgram{privatestaticFunc<int, int> Twice(Func<int, int> f) {returnx => f(f(x)); }privatestaticint PlusThree(int i) => i + 3;publicstaticvoidMain(string[] args) { var g = Twice(PlusThree); Console.WriteLine(g(7));// 13} }

#### Clojure

Further information: Clojure

(defntwice [f] (fn[x] (f (f x)))) (defnplus-three [i] (+ i 3)) (defg (twice plus-three)) (println (g 7)); 13

#### ColdFusion Markup Language (CFML)

Further information: ColdFusion Markup Language

twice =function(f) {returnfunction(x) {returnf(f(x)); }; }; plusThree =function(i) {returni + 3; }; g = twice(plusThree); writeOutput(g(7));// 13

#### D

Further information: D (programming language)

importstd.stdio : writeln;aliastwice = (f) => (int x) => f(f(x));aliasplusThree = (int i) => i + 3; void main() {autog = twice(plusThree); writeln(g(7));// 13}

#### Elixir

Further information: Elixir (programming language)

In Elixir, you can mix module definitions and anonymous functions

defmoduleHofdodeftwice(f)dofn(x) -> f.(f.(x))endendendplus_three =fn(i) -> 3 + iendg =Hof.twice(plus_three)IO.puts g.(7)# 13

Alternatively, we can also compose using pure anonymous functions.

twice =fn(f) ->fn(x) -> f.(f.(x))endendplus_three =fn(i) -> 3 + iendg = twice.(plus_three)IO.puts g.(7)# 13

#### Erlang

Further information: Erlang (programming language)

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([funerlang:is_integer/1,funerlang:is_atom/1,funerlang: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`

.

#### F#

Further information: F Sharp (programming language)

lettwice f = f >> fletplus_three = (+) 3letg = twice plus_three g 7 |> printf "%A"// 13

#### Go

Further information: Go (programming language)

packagemainimport"fmt"functwice(ffunc(int) int)func(int) int {returnfunc(x int) int {returnf(f(x)) } }funcmain() { plusThree :=func(i int) int {returni + 3 } g := twice(plusThree) fmt.Println(g(7))// 13}

Notice a function literal can be defined either with an identifier (`twice`

) or anonymously (assigned to variable `f`

).

#### Haskell

Further information: Haskell (programming language)

twice::(Int->Int)->(Int->Int) twice f=f . f plusThree::Int->Int plusThree=(+3) main::IO () main=print (g 7)-- 13whereg=twice plusThree

#### J

Further information: J (programming language)

Explicitly,

twice=. adverb : 'u u y' plusthree=. verb : 'y + 3' g=. plusthree twice g 7 13

or tacitly,

twice=. ^:2 plusthree=. +&3 g=. plusthree twice g 7 13

#### Java (1.8+)

Further information: Java (programming language) and Java version history

Using just functional interfaces:

importjava.util.function.*;classMain{publicstaticvoid main(String[] args) { Function<IntUnaryOperator, IntUnaryOperator> twice = f -> f.andThen(f); IntUnaryOperator plusThree = i -> i + 3;varg = twice.apply(plusThree); System.out.println(g.applyAsInt(7));// 13} }

Or equivalently, with static methods:

importjava.util.function.*;classMain{privatestaticIntUnaryOperator twice(IntUnaryOperator f) {returnf.andThen(f); }privatestaticint plusThree(int i) {returni + 3; }publicstaticvoid main(String[] args) {varg = twice(Main::plusThree); System.out.println(g.applyAsInt(7));// 13} }

#### JavaScript

Further information: JavaScript

"use strict";consttwice = f => x => f(f(x));constplusThree = i => i + 3;constg = twice(plusThree); console.log(g(7));// 13

#### Julia

Further information: Julia (programming language)

julia>functiontwice(f)functionresult(x)returnf(f(x))endreturnresultendtwice (generic function with 1 method)julia>plusthree(i) = i + 3 plusthree (generic function with 1 method)julia>g = twice(plusthree) (::var"#result#3"{typeof(plusthree)}) (generic function with 1 method)julia>g(7) 13

#### Kotlin

Further information: Kotlin (programming language)

funtwice(f: (Int) -> Int): (Int) -> Int {return{ f(f(it)) } }funplusThree(i: Int) = i + 3funmain() {valg = twice(::plusThree) println(g(7))// 13}

#### Lua

Further information: Lua (programming language)

localfunctiontwice(f)returnfunction(x)returnf(f(x))endendlocalfunctionplusThree(i)returni + 3endlocalg = twice(plusThree) print(g(7))-- 13

#### MATLAB

Further information: MATLAB

functionresult = twice(f) result = @innerfunctionval = inner(x) val = f(f(x));endendplusthree = @(i) i + 3; g = twice(plusthree) disp(g(7));% 13

#### OCaml

Further information: OCaml (programming language)

lettwice f x = f (f x)letplus_three = (+) 3let() =letg = twice plus_threeinprint_int (g 7);(* 13 *)print_newline ()

#### PHP

Further information: PHP

<?phpdeclare(strict_types=1);functiontwice(callable $f): Closure {returnfunction(int $x)use($f): int {return$f($f($x)); }; }functionplusThree(int $i): int {return$i + 3; } $g = twice('plusThree');echo$g(7), "\n";// 13

or with all functions in variables:

<?phpdeclare(strict_types=1); $twice = fn(callable $f): Closure => fn(int $x): int => $f($f($x)); $plusThree = fn(int $i): int => $i + 3; $g = $twice($plusThree);echo$g(7), "\n";// 13

Note that arrow functions implicitly capture any variables that come from the parent scope,^{[1]} whereas anonymous functions require the `use`

keyword to do the same.

#### Pascal

Further information: Pascal (programming language)

{$mode objfpc}typefun =function(x: Integer): Integer;functiontwice(f: fun; x: Integer): Integer;beginresult := f(f(x));end;functionplusThree(i: Integer): Integer;beginresult := i + 3;end;beginwriteln(twice(@plusThree, 7));{ 13 }end.

#### Perl

Further information: Perl

usestrict;usewarnings;subtwice {my($f) = @_;sub{ $f->($f->(@_)); }; }subplusThree {my($i) = @_; $i + 3; }my$g = twice(\&plusThree);# 13

or with all functions in variables:

usestrict;usewarnings;my$twice =sub{my($f) = @_;sub{ $f->($f->(@_)); }; };my$plusThree =sub{my($x) = @_; $x + 3; };my$g = $twice->($plusThree);# 13

#### Python

Further information: Python (programming language)

>>>deftwice(f):...defresult(x):...returnf(f(x))...returnresult>>>plusthree =lambdai: i + 3>>>g = twice(plusthree)>>>g(7) 13

Python decorator syntax is often used to replace a function with the result of passing that function through a higher-order function. E.g., the function `g`

could be implemented equivalently:

>>>@twice...defg(i):...returni + 3>>>g(7) 13

#### R

Further information: R (programming language)

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

#### Raku

Further information: Raku (programming language)

subtwice(Callable:D $f) {returnsub{ $f($f($^x)) }; }subplusThree(Int:D $i) {return$i + 3; }my$g = twice(&plusThree); say $g(7);# 13

In Raku, all code objects are closures and therefore can reference inner “lexical” variables from an outer scope because the lexical variable is “closed” inside of the function. Raku also supports “pointy block” syntax for lambda expressions which can be assigned to a variable or invoked anonymously.

#### Ruby

Further information: Ruby (programming language)

deftwice(f) ->(x) { f.call f.call(x) }endplus_three = ->(i) { i + 3 } g = twice(plus_three) puts g.call(7)# 13

#### Rust

Further information: Rust (programming language)

fntwice(f:implFn(i32) -> i32) ->implFn(i32) -> i32 {move|x| f(f(x)) }fnplus_three(i: i32) -> i32 { i + 3 }fnmain() {letg = twice(plus_three); println!("{}", g(7))// 13}

#### Scala

Further information: Scala (programming language)

objectMain{deftwice(f:Int =>Int):Int =>Int= f compose fdefplusThree(i:Int):Int = i + 3defmain(args:Array[String]):Unit = {valg = twice(plusThree) print(g(7))// 13} }

#### Scheme

Further information: Scheme (programming language)

(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)`

.

#### Swift

Further information: Swift (programming language)

functwice(_f: @escaping (Int) -> Int) -> (Int) -> Int {return{ f(f($0)) } }letplusThree = { $0 + 3 }letg = twice(plusThree) print(g(7))// 13

#### Tcl

Further information: Tcl

settwice{{f x}{apply$f[apply$f $x]}}setplusThree{{i}{return[expr$i + 3]}}# result: 13puts[apply$twice $plusThree 7]

Tcl uses apply command to apply an anonymous function (since 8.6).

#### XACML

Further information: XACML

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

ruleallowEntry{permitcondition anyOfAny(function[stringEqual],citizenships,allowedCitizenships) }

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

#### XQuery

Further information: XQuery

declarefunctionlocal:twice($f, $x) { $f($f($x)) };declarefunctionlocal:plusthree($i) { $i + 3 }; local:twice(local:plusthree#1, 7)(: 13 :)

### 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) {returnx * x; } double cube(double x) {returnx * 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); }returnsum * dt; } int main() { printf("%g\n", integral(square, 0, 1, 100)); printf("%g\n", integral(cube, 0, 1, 100));return0; }

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:

programexample;typeint = integer; Txy =recordx, y: int;end; Tf =function(xy: Txy): int;functionf(xy: Txy): int;beginResult := xy.y + xy.x;end;functiong(func: Tf): Tf;beginresult := func;end;vara: Tf; xy: Txy = (x: 3; y: 7);begina := g(@f);// return a function to "a"writeln(a(xy));// prints 10end.

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 structurestemplate<typenameT>structAdd{ T value; };template<typenameT>structDivBy{ T value; };template<typenameF,typenameG>structComposition{ F f; G g; };// Defunctionalized function application implementationstemplate<typenameF,typenameG,typenameX>autoapply(Composition<F, G> f, X arg) {returnapply(f.f, apply(f.g, arg)); }template<typenameT,typenameX>autoapply(Add<T> f, X arg) {returnarg + f.value; }template<typenameT,typenameX>autoapply(DivBy<T> f, X arg) {returnarg / f.value; }// Higher-order compose functiontemplate<typenameF,typenameG> Composition<F, G> compose(F f, G g) {returnComposition<F, G> {f, g}; } int main(int argc,constchar* argv[]) {autof = compose(DivBy<float>{ 2.0f }, Add<int>{ 5 }); apply(f, 3);// 4.0fapply(f, 9);// 7.0freturn0; }

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

## References

**^**“PHP: Arrow Functions – Manual”.*www.php.net*. Retrieved 2021-03-01.

- Functional programming
- Lambda calculus
- Higher-order functions
- Subroutines
- Articles with example Scheme (programming language) code

” (WP)