View source for Higher order function

[[Category:Glossary]] [[Category:Idioms]]

==Definition==
A '''higher-order function''' is a function that takes other functions as arguments or returns a function as result.

==Discussion==
The major use is to abstract common behaviour into one place.

===Examples===

====In the libraries====

Many functions in the libraries are higher-order. The (probably) most commonly given examples are <hask>map</hask> and <hask>fold</hask>.

Two other common ones are <hask>curry, uncurry</hask>. A possible implementation of these is:
<haskell>
curry :: ((a,b)->c) -> a->b->c
curry f a b = f (a,b)

uncurry :: (a->b->c) -> ((a,b)->c)
uncurry f (a,b)= f a b
</haskell>

<hask>curry</hask>'s first argument must be a function which accepts a pair. It applies that function to its next two arguments.

<hask>uncurry</hask> is the inverse of <hask>curry</hask>. Its first argument must be a function taking two values. <hask>uncurry</hask> then applies that function to the components of the pair which is the second argument.
====Simple code examples====
Rather than writing 
<haskell>
doubleList []     = []
doubleList (x:xs) = 2*x : doubleList xs
</haskell>
and 
<haskell>
tripleList []     = []
tripleList (x:xs) = 3*x : tripleList xs
</haskell>
we can parameterize out the difference
<haskell>
multList n [] = []
multList n (x:xs) = n*x : multList n xs
</haskell>
and define 
<haskell>
tripleList = multList 3
doubleList = multList 2
</haskell>
leading to a less error prone definition of each.

But now, if we had the function
<haskell>
addToList n [] = []
addToList n (x:xs) = n+x : addToList n xs
</haskell>
we could parameterize the difference again
<haskell>
operlist n bop [] = []
operlist n bop (x:xs) = bop n x : operlist n bop xs
</haskell>
and define doubleList as
<haskell>
doubleList = operList 2 (*) 
</haskell>
but this ties us into a constant parameters

and we could redefine things as
<haskell>
mapList f [] = []
mapList f (x:xs) = f x : mapList f xs
</haskell>
and define doubleList as
<haskell>
doubleList = mapList (2*)
</haskell>
This higher-order function "mapList" can be used in a wide range of areas to simplify code.
It is called <hask>map</hask> in Haskell's Prelude.

====Mathematical examples====

In mathematics the counterpart to higher-order functions are functionals (mapping functions to scalars) and function operators (mapping functions to functions).
Typical functionals are the limit of a sequence, or the integral of an interval of a function.
<haskell>
limit :: [Double] -> Double
definiteIntegral :: (Double, Double) -> (Double -> Double) -> Double
</haskell>
Typical operators are the indefinite integral, the derivative, the function inverse.
<haskell>
indefiniteIntegral :: Double -> (Double -> Double) -> (Double -> Double)
derive :: (Double -> Double) -> (Double -> Double)
inverse :: (Double -> Double) -> (Double -> Double)
</haskell>
Here is a numerical approximation:
<haskell>
derive :: Double -> (Double -> Double) -> (Double -> Double)
derive eps f x = (f(x+eps) - f(x-eps)) / (2*eps)
</haskell>

==See also==
[[Accumulator recursion]] where the accumulator is a higher-order function is one interesting case of [[continuation passing style]].