Higher-order function: Difference between revisions

Revision as of 13:16, 18 August 2021

Latest revision as of 18:43, 23 March 2025

(38 intermediate revisions by 26 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)}}

* 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),

{{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. [[procedural parameter]]s),

* 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 20 ⟶ 19:

* [[Montague grammar]], a semantic theory of natural language, uses higher-order functions

==Support in programming languages==<!-- see also Category:Programming language comparisons -->

{{Split|Comparison of programming languages (higher-order functions)|date=May 2016}} <!-- see also Category:Programming language comparisons -->

===Direct support===

Line 59 ⟶ 56:

{{further information|C++}}

Using {{code|std::function}} in [[C++11]]:

<syntaxhighlight lang="c++">

Line 67 ⟶ 64:

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

{

return [&f](int x) {

return f(f(x));

};

Line 92 ⟶ 89:

auto twice = [](const auto& f)

{

return [&f](int x) {

return f(f(x));

};

Line 188 ⟶ 185:

writeOutput(g(7)); // 13

</syntaxhighlight>

====Common Lisp====

{{further information|Common Lisp}}

<syntaxhighlight lang="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))

</syntaxhighlight>

Line 241 ⟶ 253:

end

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

g = Hof.twice(plus_three)

Line 255 ⟶ 267:

end

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

g = twice.(plus_three)

Line 317 ⟶ 329:

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 408 ⟶ 430:

====JavaScript====

{{further information|JavaScript}}

With arrow functions:

<syntaxhighlight lang="javascript">

Line 415 ⟶ 439:

const plusThree = i => i + 3;

const g = twice(plusThree);

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

</syntaxhighlight>

Or with classical syntax:

<syntaxhighlight lang="javascript">

"use strict";

function twice(f) {

return function (x) {

return f(f(x));

};

}

function plusThree(i) {

return i + 3;

}

const g = twice(plusThree);

Line 480 ⟶ 524:

==== 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 499 ⟶ 539:

==== OCaml ====

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

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

Line 555 ⟶ 595:

Note that arrow functions implicitly capture any variables that come from the parent scope,<ref>{{Cite web|title=PHP: Arrow Functions - Manual|url=https://www.php.net/manual/en/functions.arrow.php|access-date=2021-03-01|website=www.php.net}}</ref> whereas anonymous functions require the {{code|use}} keyword to do the same.

====Pascal====

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

<syntaxhighlight lang="pascal" line="1">

{$mode objfpc}

type fun = function(x: Integer): Integer;

function twice(f: fun; x: Integer): Integer;

begin

result := f(f(x));

end;

function plusThree(i: Integer): Integer;

begin

result := i + 3;

end;

begin

writeln(twice(@plusThree, 7)); { 13 }

end.

</syntaxhighlight>

====Perl====

Line 617 ⟶ 634:

my $plusThree = sub {

my ($xi) = @_;

$xi + 3;

};

Line 635 ⟶ 652:

... return result

>>> plusthreeplus_three = lambda i: i + 3

>>> g = twice(plusthreeplus_three)

>>> g(7)

Line 658 ⟶ 675:

<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 694 ⟶ 705:

====Ruby====

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

<syntaxhighlight lang="ruby">

def twice(f)

->(x) { f.call (f.call(x)) }

end

Line 750 ⟶ 761:

<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 3))

(define g (twice plus-three))

(display (g 7)) ; 13

(display "\n")

</syntaxhighlight>

====Swift====

Line 818 ⟶ 835:

=== Alternatives ===

====Function pointers====

[[Function pointer]]s in languages such as [[C (programming language)|C]] and, [[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 856 ⟶ 873:

====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 950 ⟶ 967:

==References==

{{Reflist}}

{{Functions navbox}}

[[Category:Functional programming]]

Line 957 ⟶ 973:

[[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]]