|
In mathematics and computer science, higher-order functions are functions which can take other functions as arguments, and may also return functions as results. The derivative in calculus is a common example of a higher-order function, since it maps a function to another function. Higher-order functions were studied long before the notion of functional programming existed, in the lambda calculus, a formalism which has influenced the design of several functional programming languages, especially the Haskell programming language.
Higher order functions in Haskell implement tremendous power in very few lines of code. For example, the following Haskell functions will square each number in a given list
-- without higher order functions
squareListNoHof [] = []
squareListNoHof (head:tail) = (head^2):(squareListNoHof tail)
-- with higher order functions
squareList list = map (^2) list
In the above example, map takes in the function (^2) (note that the first argument to (^2) is omitted, this instructs Haskell to substitute elements of the list as the first argument to the function), and the list list, and thus squares each element. map generalises the idea of "mapping" a function onto a list, that is, applying a function on 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>:
-- without higher order functions
doFunctionNoHof x = cos (log (sqrt (3*x+2)))
-- with higher order functions
doFunction x = (cos.log.sqrt) (3*x+2)
In the above example, the (.) function takes in two functions as an argument and returns a function representing their composition: eg (f.g) x = f(g(x)). Strictly, in the above example, (cos.log.sqrt) (3x+2) is basically equivalent to (cos.(log.sqrt)), but in computer-parsing, the first expression is converted, so the notational simplification is still held.
Alternatives
Programming languages which can dynamically execute code (sometimes called "Eval" or "Execute" operations) in the scope of evaluation and have functions which can optionally inherit the caller's variable scope can be used to do much of what higher-order functions do in programming languages. However, because most of it happens at run-time instead of compile time, these approaches will usually execute slower. Some also consider dynamic evaluation a security risk. But, some feel that they keep the language simpler and/or easier-to-learn.
See also: functional analysis, combinatory logic
| 
