Higher-order function: Difference between revisions

Revision as of 05:49, 8 March 2022

Latest revision as of 17:12, 31 August 2025

(33 intermediate revisions by 23 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''' 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 60 ⟶ 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 86 ⟶ 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 254 ⟶ 246:

end

plus_three = fn(i) -> 3i + i3 end

g = Hof.twice(plus_three)

Line 268 ⟶ 260:

end

plus_three = fn(i) -> 3i + i3 end

g = twice.(plus_three)

Line 330 ⟶ 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 423 ⟶ 425:

With arrow functions:

<syntaxhighlight lang="javascript">

"use strict";

Line 436 ⟶ 439:

Or with classical syntax:

<syntaxhighlight lang="javascript">

"use strict";

Line 443 ⟶ 447:

return f(f(x));

};

};

function plusThree(i) {

Line 450 ⟶ 454:

const g = twice(plusThree);

console.log(g(7)); // 13

</syntaxhighlight>

Line 512 ⟶ 517:

==== MATLAB ====

{{Furtherfurther information|MATLAB}}

<syntaxhighlight lang="matlab">

function result = twice(f)

result = @inner(x) f(f(x));

function val = inner(x)

val = f(f(x));

end

end

Line 531 ⟶ 532:

==== OCaml ====

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

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

Line 626 ⟶ 627:

my $plusThree = sub {

my ($xi) = @_;

$xi + 3;

};

Line 638 ⟶ 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 667 ⟶ 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 703 ⟶ 698:

====Ruby====

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

<syntaxhighlight lang="ruby">

Line 759 ⟶ 754:

<syntaxhighlight lang="scheme">

(define (addcompose xf yg) (+ x y))

(definelambda (x) (f (g x))))

(lambda (y) (+ x y)))

(display ((f 3) 7))

(display (add 3 7))

</syntaxhighlight>

(define (twice f)

In this Scheme example, the higher-order function {{code|(f x)}} is used to implement [[currying]]. It takes a single argument and returns a function. The evaluation of the expression {{code|((f 3) 7)}} first returns a function after evaluating {{code|(f 3)}}. The returned function is {{code|(lambda (y) (+ 3 y))}}. Then, it evaluates the returned function with 7 as the argument, returning 10. This is equivalent to the expression {{code|(add 3 7)}}, since {{code|(f x)}} is equivalent to the curried form of {{code|(add x y)}}.

(compose f f))

(define (plus-three i)

(+ i f(f(x3))

(define g (twice plus-three))

(display ((f 3)g 7)) ; 13

(display (add 3 7)"\n")

</syntaxhighlight>

====Swift====

Line 827 ⟶ 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 865 ⟶ 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 959 ⟶ 960:

==References==

{{Reflist}}

{{Functions navbox}}

[[Category:Functional programming]]

Line 966:

[[Category:Higher-order functions| ]]

[[Category:Subroutines]]

[[Category:Articles with example Python (programming language)C code]]

[[Category:Articles with example C++ code]]

[[Category:Articles with example D code]]

[[Category:Articles with example Haskell code]]

[[Category:Articles with example Scheme (programming language)Java code]]

[[Category:Articles with example JavaScript code]]

[[Category:Articles with example CJulia code]]

[[Category:Articles with example Lisp (programming language) code]]

[[Category:Articles with example MATLAB/Octave code]]

[[Category:Articles with example Pascal code]]

[[Category:Articles with example Perl code]]

[[Category:Articles with example PHP code]]

[[Category:Articles with example Python (programming language) code]]

[[Category:Articles with example R code]]

[[Category:Articles with example Scala code]]

[[Category:Articles with example Scheme (programming language) code]]

[[Category:Articles with example Tcl code]]

[[Category:Articles with example Swift code]]