Higher-order function: Difference between revisions

Revision as of 14:35, 13 October 2024

Latest revision as of 18:43, 23 March 2025

(5 intermediate revisions by 4 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 or value 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 876 ⟶ 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 970 ⟶ 967:

==References==

{{Reflist}}

{{Functions navbox}}

[[Category:Functional programming]]