In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a higher-order function (HOF) is a
function that does at least one of the following:
* takes one or more functions as arguments (i.e. a
procedural parameter, which is a
parameter
A parameter (), generally, is any characteristic that can help in defining or classifying a particular system (meaning an event, project, object, situation, etc.). That is, a parameter is an element of a system that is useful, or critical, when ...
of a
procedure that is itself a procedure),
* 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
Calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizati ...
is a common example, since it maps a function to its
derivative
In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. ...
, also a function. Higher-order functions should not be confused with other uses of the word "functor" throughout mathematics, see
Functor (disambiguation)
A functor, in mathematics, is a map between categories.
Functor may also refer to:
* Predicate functor in logic, a basic concept of predicate functor logic
* Function word in linguistics
* In computer programming:
** Functor (functional program ...
.
In the untyped
lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation th ...
, all functions are higher-order; in a
typed lambda calculus, from which most
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions tha ...
languages are derived, higher-order functions that take one function as argument are values with types of the form
.
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
In mathematics and computer science, apply is a function that applies a function to arguments. It is central to programming languages derived from lambda calculus, such as LISP and Scheme, and also in functional languages. It has a role in the ...
*
Function composition
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
*
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 takes a function, and applies the function to some value twice. If has to be applied several times for the same it preferably should return a function rather than a value. This is in line with the "
don't repeat yourself" principle.
APL
twice←
plusthree←
g←
g 7
13
Or in a tacit manner:
twice←⍣2
plusthree←+∘3
g←plusthree twice
g 7
13
C++
Using in
C++11 C11, C.XI, C-11 or C.11 may refer to:
Transport
* C-11 Fleetster, a 1920s American light transport aircraft for use of the United States Assistant Secretary of War
* Fokker C.XI, a 1935 Dutch reconnaissance seaplane
* LET C-11, a license-build ...
:
#include
#include
auto twice = [](const std::function& f)
;
auto plus_three = [](int i)
;
int main()
Or, with generic lambdas provided by C++14:
#include
auto twice = [](const auto& f)
;
auto plus_three = [](int i)
;
int main()
C#
Using just delegates:
using System;
public class Program
Or equivalently, with static methods:
using System;
public class Program
Clojure
(defn twice (fn (f (f x))))
(defn plus-three (+ i 3))
(def g (twice plus-three))
(println (g 7)) ; 13
ColdFusion Markup Language (CFML)
twice = function(f) ;
plusThree = function(i) ;
g = twice(plusThree);
writeOutput(g(7)); // 13
Common Lisp
(defun twice (f)
(lambda (x) (funcall f (funcall f x))))
(defun plus-three (i)
(+ i 3))
(defvar g (twice #'plus-three))
(print (funcall g 7))
D
import std.stdio : writeln;
alias twice = (f) => (int x) => f(f(x));
alias plusThree = (int i) => i + 3;
void main()
Dart
int Function(int) twice(int Function(int) f)
int plusThree(int i)
void main()
Elixir
In Elixir, you can mix module definitions and
anonymous functions
defmodule Hof do
def twice(f) do
fn(x) -> f.(f.(x)) end
end
end
plus_three = fn(i) -> 3 + i end
g = 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)) end
end
plus_three = fn(i) -> 3 + i end
g = twice.(plus_three)
IO.puts g.(7) # 13
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, _, ) -> 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 takes a list of functions () and argument (). It evaluates the function with the argument as argument. If the function returns false then the next function in will be evaluated. If the function returns then the next function in with argument will be evaluated. If the function returns the higher-order function will return . Note that , , and can be functions. The example returns .
F#
let twice f = f >> f
let plus_three = (+) 3
let g = twice plus_three
g 7 , > printf "%A" // 13
Go
package main
import "fmt"
func twice(f func(int) int) func(int) int
func main()
Notice a function literal can be defined either with an identifier () or anonymously (assigned to variable ).
Haskell
twice :: (Int -> Int) -> (Int -> Int)
twice f = f . f
plusThree :: Int -> Int
plusThree = (+3)
main :: IO ()
main = print (g 7) -- 13
where
g = twice plusThree
J
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+)
Using just functional interfaces:
import java.util.function.*;
class Main
Or equivalently, with static methods:
import java.util.function.*;
class Main
JavaScript
With arrow functions:
"use strict";
const twice = f => x => f(f(x));
const plusThree = i => i + 3;
const g = twice(plusThree);
console.log(g(7)); // 13
Or with classical syntax:
"use strict";
function twice(f)
function plusThree(i)
const g = twice(plusThree);
console.log(g(7)); // 13
Julia
julia> function twice(f)
function result(x)
return f(f(x))
end
return result
end
twice (generic function with 1 method)
julia> plusthree(i) = i + 3
plusthree (generic function with 1 method)
julia> g = twice(plusthree)
(::var"#result#3") (generic function with 1 method)
julia> g(7)
13
Kotlin
fun twice(f: (Int) -> Int): (Int) -> Int
fun plusThree(i: Int) = i + 3
fun main()
Lua
function twice(f)
return function (x)
return f(f(x))
end
end
function plusThree(i)
return i + 3
end
local g = twice(plusThree)
print(g(7)) -- 13
MATLAB
function result = twice(f)
result = @inner
function val = inner(x)
val = f(f(x));
end
end
plusthree = @(i) i + 3;
g = twice(plusthree)
disp(g(7)); % 13
OCaml
let twice f x =
f (f x)
let plus_three =
(+) 3
let () =
let g = twice plus_three in
print_int (g 7); (* 13 *)
print_newline ()
PHP
or with all functions in variables:
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, whereas anonymous functions require the keyword to do the same.
Perl
use strict;
use warnings;
sub twice
sub plusThree
my $g = twice(\&plusThree);
print $g->(7), "\n"; # 13
or with all functions in variables:
use strict;
use warnings;
my $twice = sub ;
my $plusThree = sub ;
my $g = $twice->($plusThree);
print $g->(7), "\n"; # 13
Python
>>> def twice(f):
... def result(x):
... return f(f(x))
... return result
>>> plus_three = lambda i: i + 3
>>> g = twice(plus_three)
>>> 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 could be implemented equivalently:
>>> @twice
... def g(i):
... return i + 3
>>> g(7)
13
R
twice <- function(f)
plusThree <- function(i)
g <- twice(plusThree)
> print(g(7))
13
Raku
sub twice(Callable:D $f)
sub plusThree(Int:D $i)
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
def twice(f)
->(x)
end
plus_three = ->(i)
g = twice(plus_three)
puts g.call(7) # 13
Rust
fn twice(f: impl Fn(i32) -> i32) -> impl Fn(i32) -> i32
fn plus_three(i: i32) -> i32
fn main()
Scala
object Main
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 is used to implement currying. It takes a single argument and returns a function. The evaluation of the expression first returns a function after evaluating . The returned function is . Then, it evaluates the returned function with 7 as the argument, returning 10. This is equivalent to the expression , since is equivalent to the curried form of .
Swift
func twice(_ f: @escaping (Int) -> Int) -> (Int) -> Int
let plusThree =
let g = twice(plusThree)
print(g(7)) // 13
Tcl
set twice
set plusThree
# result: 13
puts pply $twice $plusThree 7
Tcl uses apply command to apply an anonymous function (since 8.6).
XACML
The XACML standard defines higher-order functions in the standard to apply a function to multiple values of attribute bags.
rule allowEntry
The list of higher-order functions in XACML can be found here
Here is an adverb that means "in, on, or at this place". It may also refer to:
Software
* Here Technologies, a mapping company
* Here WeGo (formerly Here Maps), a mobile app and map website by Here
Television
* Here TV (formerly "here!"), a ...
.
XQuery
declare function local:twice($f, $x) ;
declare function local:plusthree($i) ;
local:twice(local:plusthree#1, 7) (: 13 :)
Alternatives
Function pointers
Function pointers in languages such as C, C++, and Pascal
Pascal, Pascal's or PASCAL may refer to:
People and fictional characters
* Pascal (given name), including a list of people with the name
* Pascal (surname), including a list of people and fictional characters with the name
** Blaise Pascal, Frenc ...
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)
double cube(double x)
/* Compute the integral of f() within the interval ,b*/
double integral(double f(double x), double a, double b, int n)
int main()
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
In computer science, imperative programming is a programming paradigm of software that uses statements that change a program's state. In much the same way that the imperative mood in natural languages expresses commands, an imperative program ...
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
Interpretation may refer to:
Culture
* Aesthetic interpretation, an explanation of the meaning of a work of art
* Allegorical interpretation, an approach that assumes a text should not be interpreted literally
* Dramatic Interpretation, an event ...
, causing some added overhead at run-time, and usually generating less efficient code.
Objects
In object-oriented programming
Object-oriented programming (OOP) is a programming paradigm based on the concept of "objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of ...
languages that do not support higher-order functions, objects
Object may refer to:
General meanings
* Object (philosophy), a thing, being, or concept
** Object (abstract), an object which does not exist at any particular time or place
** Physical object, an identifiable collection of matter
* Goal, an ai ...
can be an effective substitute. An object's methods
Method ( grc, μέθοδος, methodos) literally means a pursuit of knowledge, investigation, mode of prosecuting such inquiry, or system. In recent centuries it more often means a prescribed process for completing a task. It may refer to:
*Scien ...
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
In computer programming, boilerplate code, or simply boilerplate, are sections of code that are repeated in multiple places with little to no variation. When using languages that are considered ''verbose'', the programmer must write a lot of boile ...
for defining and instantiating an object and its method(s). Languages that permit stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
-based (versus heap-based) objects or structs
In computer science, a record (also called a structure, struct, or compound data) is a basic data structure. Records in a database or spreadsheet are usually called " rows".
A record is a collection of ''fields'', possibly of different data ...
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
In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from ...
:
// Defunctionalized function data structures
template struct Add ;
template struct DivBy ;
template struct Composition ;
// Defunctionalized function application implementations
template
auto apply(Composition f, X arg)
template
auto apply(Add f, X arg)
template
auto apply(DivBy f, X arg)
// Higher-order compose function
template
Composition compose(F f, G g)
int main(int argc, const char* argv[])
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
Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of com ...
* Function-level programming
*Functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions tha ...
*Kappa calculus In mathematical logic, category theory, and
computer science, kappa calculus is a
formal system for defining First order functions, first-order
function (mathematics), functions.
Unlike lambda calculus, kappa calculus has no
higher-order functions; ...
- a formalism for functions which ''excludes'' higher-order functions
* Strategy pattern
* Higher order messages
References
{{Reflist
Functional programming
Lambda calculus
Subroutines
Articles with example Python (programming language) code
Articles with example Haskell code
Articles with example Scheme (programming language) code
Articles with example JavaScript code
Articles with example C code
Articles with example Pascal code
Articles with example R code