Higher-order function

From Freepedia

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 = map (^2)

-- 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.

Other examples of higher level functions include Oliver Heaviside's differential operator and the J programming language's rank conjunction.

Alternatives

Programming languages can achieve some of the same algorithmic results as are obtained through higher-order functions by dynamically executing code (sometimes called "Eval" or "Execute" operations) in the scope of evaluation. This can simplify and ease learning of a language. However...

• the arguments and/or results are not strongly typed as functions
• this usually happens at run-time instead of compile time, slowing execution
• dynamic evaluation may be a security risk

Macros can also be used to achieve some of the effects of higher order functions. These do not have the efficiency problems of run-time evaluation, but are more limited in what they can achieve. These also tend to not be strongly typed.

Objects, in an object-oriented programming environment can be used as higher order functions, in the sense that different objects may have different behaviors and thus might be thought of as representing different functions. However the usual treatment of objects, where they have reference semantics rather than value semantics, can complicate this picture. If care is not taken, these "functions" can change their behavior in mysterious ways after they've been generated.

In general, data driven programming methodologies have some of the character of higher order functions, as the data itself determines function, and operations on that data may result in alternate functionality being employed. Here, there would be a mapping from [some part of] the data to some domain of functions and a mapping from [some part of] the code to some domain of higher order functions.

See also: functional analysis, combinatory logic, function-level programming