# Higher order function

### From HaskellWiki

BrettGiles (Talk | contribs) (Page to explain higher order functions.) |
m (use 'higher-order' instead of 'higher order') |
||

(6 intermediate revisions by 3 users not shown) | |||

Line 1: | Line 1: | ||

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

+ | |||

==Definition== | ==Definition== | ||

− | A '''higher order function''' is a function that takes other functions as arguments. | + | A '''higher-order function''' is a function that takes other functions as arguments or returns a function as result. |

==Discussion== | ==Discussion== | ||

Line 10: | Line 11: | ||

====In the libraries==== | ====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>. | + | 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 | + | Two other common ones are <hask>curry, uncurry</hask>. A possible implementation of these is: |

<haskell> | <haskell> | ||

curry :: ((a,b)->c) -> a->b->c | curry :: ((a,b)->c) -> a->b->c | ||

Line 45: | Line 46: | ||

doubleList = multList 2 | doubleList = multList 2 | ||

</haskell> | </haskell> | ||

− | leading to a less error prone | + | leading to a less error prone definition of each. |

− | + | But now, if we had the function | |

<haskell> | <haskell> | ||

addToList n [] = [] | addToList n [] = [] | ||

Line 72: | Line 73: | ||

doubleList = mapList (2*) | doubleList = mapList (2*) | ||

</haskell> | </haskell> | ||

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

− | 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== | ==See also== | ||

− | [[Accumulator recursion]] where the accumulator is a higher order function is one interesting case of [[continuation passing style]]. | + | [[Accumulator recursion]] where the accumulator is a higher-order function is one interesting case of [[continuation passing style]]. |

## Latest revision as of 18:20, 29 September 2010

## Contents |

## [edit] 1 Definition

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

## [edit] 2 Discussion

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

### [edit] 2.1 Examples

#### [edit] 2.1.1 In the libraries

Many functions in the libraries are higher-order. The (probably) most commonly given examples arecurry :: ((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

#### [edit] 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.

It is called#### [edit] 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 is a numerical approximation:

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

## [edit] 3 See also

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