Higher order function

From HaskellWiki

1 Definition

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

2 Discussion

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

2.1 Examples

2.1.1 In the libraries

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

2.1.2 Simple code examples

Rather than writing

doubleList []     = []
doubleList (x:xs) = 2*x : doubleList xs

and

tripleList []     = []
tripleList (x:xs) = 3*x : tripleList xs

we can parameterize out the difference

multList n [] = []
multList n (x:xs) = n*x : multList n xs

and define

tripleList = multList 3
doubleList = multList 2

leading to a less error prone definition of each.

But now, if we had the function

addToList n [] = []
addToList n (x:xs) = n+x : addToList n xs

we could parameterize the difference again

operlist n bop [] = []
operlist n bop (x:xs) = bop n x : operlist n bop xs

and define doubleList as

doubleList = operList 2 (*)

but this ties us into a constant parameters

and we could redefine things as

mapList f [] = []
mapList f (x:xs) = f x : mapList f xs

and define doubleList as

doubleList = mapList (2*)

This higher order function "mapList" can be used in a wide range of areas to simplify code.

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

limit :: [Double] -> Double
definiteIntegral :: (Double, Double) -> (Double -> Double) -> Double

Typical operators are the indefinite integral, the derivative, the function inverse.

indefiniteIntegral :: Double -> (Double -> Double) -> (Double -> Double)
derive :: (Double -> Double) -> (Double -> Double)
inverse :: (Double -> Double) -> (Double -> Double)

Here a numerical approximation:

derive :: Double -> (Double -> Double) -> (Double -> Double)
derive eps f x = (f(x+eps) - f(x-eps)) / (2*eps)

3 See also

Accumulator recursion where the accumulator is a higher order function is one interesting case of continuation passing style.

Categories: Glossary | Idioms