Higher-order function: Difference between revisions

Revision as of 17:29, 15 October 2023

Latest revision as of 17:12, 31 August 2025

(14 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|Function that takes one or more functions as an input or that outputs a function}}{{More sources|date=November 2024}}{{Distinguish|Functor{{!}}Functor (category theory)}}In [[mathematics]] and [[computer science]], a '''higher-order function''' ('''HOF''') is a [[function (mathematics)|function]] that does at least one of the following:

{{Distinguish|Functor{{!}}Functor (category theory)}}

{{more footnotes|date=September 2013}}

In [[mathematics]] and [[computer science]], a '''higher-order function''' ('''HOF''') is a [[function (mathematics)|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 (computer science)|parameter]] of a [[Subroutine|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 ''[[operator (mathematics)|operators]]'' or ''[[functional (mathematics)|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 <math>(\tau_1\to\tau_2)\to\tau_3</math>.

==General examples==

* <code>[[map (higher-order function)|map]]</code> function, found in many functional programming languages, is one example of a higher-order function. It takes arguments 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 (programming language)|C]] standard [[function (computer science)|function]] <code>qsort</code> is an example of this.

* [[Filter (higher-order function) | filter]]

* [[fold (higher-order function)|fold]]

* [[Prefix sum|scan]]

* [[apply]]

* [[Function composition (computer science)|Function composition]]

Line 62 ⟶ 59:

<syntaxhighlight lang="c++">

import std;

#include <iostream>

#include <functional>

auto twice = [](const std::function<int(int)>& f) -> auto {

return [f](int x) -> int {

{

return [f](int x) {

return f(f(x));

};

};

auto plus_threeplusThree = [](int i) -> int {

{

return i + 3;

};

int main() {

auto g = twice(plus_threeplusThree);

{

auto g = twice(plus_three);

std::cout <<println("{}", g(7) << '\n'); // 13

}

</syntaxhighlight>

Line 88 ⟶ 81:

<syntaxhighlight lang="c++">

import std;

#include <iostream>

auto twice = [](const auto& f) -> auto {

return [f](int x) -> int {

{

return [f](int x) {

return f(f(x));

};

};

auto plus_threeplusThree = [](int i) -> int {

{

return i + 3;

};

int main() {

auto g = twice(plus_threeplusThree);

{

auto g = twice(plus_three);

std::cout <<println("{}", g(7) << '\n'); // 13

}

</syntaxhighlight>

Line 332 ⟶ 322:

Notice a function literal can be defined either with an identifier ({{code|twice}}) or anonymously (assigned to variable {{code|plusThree}}).

====Groovy====

{{further information|Groovy (programming language)}}

<syntaxhighlight lang="groovy">def twice = { f, x -> f(f(x)) }

def plusThree = { it + 3 }

def g = twice.curry(plusThree)

println g(7) // 13

</syntaxhighlight>

====Haskell====

{{further information|Haskell (programming language)}}

<syntaxhighlight lang="haskell">

Line 517:

==== MATLAB ====

{{Furtherfurther information|MATLAB}}

<syntaxhighlight lang="matlab">

Line 532:

==== OCaml ====

{{Furtherfurther information|OCaml (programming language)}}

<syntaxhighlight lang="ocaml" start="1">

Line 639:

{{further information|Python (programming language)}}

<syntaxhighlight lang="pyconpython">

>>> def twice(f: Callable[Any]) -> Any:

... def result(x: Any) -> Any:

... return f(f(x))

... return result

>>> plus_three: Callable[int] = lambda i: i + 3

>>> g: int = twice(plus_three)

>>> print(g(7))

# prints 13

13

</syntaxhighlight>

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 {{code|g}} could be implemented equivalently:

<syntaxhighlight lang="pyconpython">

>>> @twice

... def g(i: int) -> int:

... return i + 3

>>> print(g(7))

# prints 13

13

</syntaxhighlight>

Line 668:

<syntaxhighlight lang="R">

twice <- function\(f) {\(x) f(f(x))

return(function(x) {

f(f(x))

})

}

plusThree <- function(i) {i + 3

return(i + 3)

}

g <- twice(plusThree)

> print(g(7))

[1] 13

</syntaxhighlight>

Line 704 ⟶ 698:

====Ruby====

{{further information| Ruby (programming language)}}

<syntaxhighlight lang="ruby">

Line 760 ⟶ 754:

<syntaxhighlight lang="scheme">

(define (compose f g)

(lambda (x) (f (g x))))

(define (twice f)

(lambdacompose (x) (f (f x))))

(define (plus-three i)

Line 831 ⟶ 828:

=== Alternatives ===

====Function pointers====

[[Function pointer]]s in languages such as [[C (programming language)|C]], [[C++]], [[Fortran]], and [[Pascal (programming language)|Pascal]] allow programmers to pass around references to functions. The following C code computes an approximation of the integral of an arbitrary function:

<syntaxhighlight lang="c">

Line 869 ⟶ 866:

====Macros====

[[Macro (computer science)|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 [[type system#Static typing|statically typed]]; these languages generally rely on [[type system#Dynamic typing|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 [[interpreter (computing)|interpretation]], causing some added overhead at run-time, and usually generating less efficient code.

====Objects====

Line 963 ⟶ 960:

==References==

{{Reflist}}

{{Functions navbox}}

[[Category:Functional programming]]