Higher-order function

Encyclopedia

In mathematics

and computer science

,

are function

s which do at least one of the following:

All other functions are first-order functions. In mathematics higher-order functions 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 language

s are derived, higher-order functions are values with types of the form .

The

standard function

Other examples of higher-order functions include fold

, function composition

, integration

, and the constant-function function λ

script

contains the higher-order function g which takes a function as its first argument and returns a number. This example prints 100 (

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

and computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

,

**higher-order functions**,**functional forms**, or**functionals**Functional (mathematics)

In mathematics, and particularly in functional analysis, a functional is a map from a vector space into its underlying scalar field. In other words, it is a function that takes a vector as its input argument, and returns a scalar...

are function

Function (mathematics)

In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

s which do at least one of the following:

- take one or more functions as an input
- output a function

All other functions are first-order functions. In mathematics higher-order functions are also known as operators or functionals. The derivative

Derivative

In calculus, a branch of mathematics, the derivative is a measure of how a function changes as its input changes. Loosely speaking, a derivative can be thought of as how much one quantity is changing in response to changes in some other quantity; for example, the derivative of the position of a...

in calculus

Calculus

Calculus is a branch of mathematics focused on limits, functions, derivatives, integrals, and infinite series. This subject constitutes a major part of modern mathematics education. It has two major branches, differential calculus and integral calculus, which are related by the fundamental theorem...

is a common example, since it maps a function to another function.

In the untyped lambda calculus

Lambda calculus

In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...

, all functions are higher-order; in a typed lambda calculus

Typed lambda calculus

A typed lambda calculus is a typed formalism that uses the lambda-symbol to denote anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to lambda terms; the exact nature of a type depends on the calculus considered...

, from which most functional programming language

Functional programming

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...

s are derived, higher-order functions are values with types of the form .

The

`mapMap (higher-order function)In many programming languages, map is the name of a higher-order function that applies a given function to each element of a list, returning a list of results. They are examples of both catamorphisms and anamorphisms...`

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 CC (programming language)

C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

standard function

`qsort`

, is an example of this.Other examples of higher-order functions include fold

Fold (higher-order function)

In functional programming, fold – also known variously as reduce, accumulate, compress, or inject – are a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its...

, function composition

Function composition (computer science)

In computer science, function composition is an act or mechanism to combine simple functions to build more complicated ones...

, integration

Integral

Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...

, and the constant-function function λ

*x*.λ*y*.*x*.*The following examples were not intended to compare and contrast programming languages, since each program performs a different task. Also, the idea of a "scripting language" is beyond the scope of this article.*## Example

This PythonPython (programming language)

Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...

script

Scripting language

A scripting language, script language, or extension language is a programming language that allows control of one or more applications. "Scripts" are distinct from the core code of the application, as they are usually written in a different language and are often created or at least modified by the...

contains the higher-order function g which takes a function as its first argument and returns a number. This example prints 100 (

*g(f,7)=*(7+3)×(7+3) ).