Difference between revisions of "Higher order function"
m (use 'higher-order' instead of 'higher order') |
|||
(5 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
[[Category:Glossary]] [[Category:Idioms]] |
[[Category:Glossary]] [[Category:Idioms]] |
||
+ | |||
==Definition== |
==Definition== |
||
− | A '''higher |
+ | 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 |
+ | 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 definition of each |
+ | 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. |
|
+ | It is called <hask>map</hask> in Haskell's Prelude. |
||
− | to simplify code |
||
+ | |||
+ | ====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 |
+ | [[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
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 map
and fold
.
Two other common ones are curry, uncurry
. A possible implementation of these is:
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
curry
's first argument must be a function which accepts a pair. It applies that function to its next two arguments.
uncurry
is the inverse of curry
. Its first argument must be a function taking two values. uncurry
then applies that function to the components of the pair which is the second argument.
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 map
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.
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)
See also
Accumulator recursion where the accumulator is a higher-order function is one interesting case of continuation passing style.