Higher-order function

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 list = ((head list)^2):(squareListNoHof (tail list))

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

-- without higher order functions
doFunctionNoHof x = cos (log (sqrt (3x+2))
-- with higher order functions
doFunction x = (cos.log.sqrt) (3x+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.(ln.sqrt)), but in computer-parsing, the first expression is converted, so the notational simplification is still held.