Higher-order function
|
|
In mathematics and computer science, higher-order functions are functions which do at least one of the below:
- take function(s) as an input
- output a function
In mathematics these are also known as operators and functionals. The derivative in calculus is a common example, since it maps a function to another function. Higher-order functions were studied in lambda calculus long before functional programming existed. Lambda calculus is a formalism which has influenced the design of several functional programming languages, especially the Haskell programming language.
Higher order functions in Haskell concisely implement tremendous power. For example, the following Haskell functions contrast squaring a list with and without higher order functions and currying.
-- with higher order functions squareList list = map (^2) list
-- without higher order functions squareListNoHof [] = [] squareListNoHof (head:tail) = (head^2):(squareListNoHof tail)
In the above example, map takes in the function (^2) (note that one argument to (^2) is supplied, instructing Haskell to substitute list elements as the other argument), and the list list, thus squaring each element. map "maps" a function onto a list, that is, applies a function to each element of a list.
The above was an example of a higher-order function that takes in a function as an argument, but does not return a function of sorts as an output. However there are standard higher order functions that do, such as the (.) function. For example, the following function will calculate the numerical equivalent to the function <math>\cos(\ln \sqrt{3x+2})<math>:
-- with higher order functions Composite x = (cos.log.sqrt) (3*x+2)
-- without higher order functions CompositeNoHof x = cos (log (sqrt (3*x+2)))
The (.) function represents function composition.
It takes two functions as an argument and returns a function representing their composition: e.g., (f.g) x = f(g(x)). Strictly, in the above example, (cos.log.sqrt) (3x+2) is equivalent to (cos.(log.sqrt)), but the first expression is converted, so notational simplification is still held.
Alternative
Programming languages can simulate higher-order functions by dynamically executing code (sometimes called "Eval" or "Execute" operations) in the scope of evaluation and support functions which inherit the caller's variable scope. This can simplify and ease learning of a language. However...
- this usually happens at run-time instead of compile time, slowing execution
- dynamic evaluation may be a security risk
See also: functional analysis, combinatory logic