Personal tools

Higher order function

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Mathematical examples)
Current revision (18:20, 29 September 2010) (edit) (undo)
m (use 'higher-order' instead of 'higher order')
 
(2 intermediate revisions not shown.)
Line 2: Line 2:
==Definition==
==Definition==
-
A '''higher order function''' is a function that takes other functions as arguments or returns a function as result.
+
A '''higher-order function''' is a function that takes other functions as arguments or returns a function as result.
==Discussion==
==Discussion==
Line 11: 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 the them is:
+
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 73: 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.
+
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.
It is called <hask>map</hask> in Haskell's Prelude.
====Mathematical examples====
====Mathematical examples====
-
In mathematics the counterpart to higher order functions are functionals (mapping functions to scalars) and function operators (mapping functions to functions).
+
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.
Typical functionals are the limit of a sequence, or the integral of an interval of a function.
<haskell>
<haskell>
Line 90: Line 90:
inverse :: (Double -> Double) -> (Double -> Double)
inverse :: (Double -> Double) -> (Double -> Double)
</haskell>
</haskell>
-
Here a numerical approximation:
+
Here is a numerical approximation:
<haskell>
<haskell>
derive :: Double -> (Double -> Double) -> (Double -> Double)
derive :: Double -> (Double -> Double) -> (Double -> Double)
Line 97: Line 97:
==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]].

Current revision


Contents

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

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.

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
map
in Haskell's Prelude.

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)

3 See also

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

Retrieved from "http://www.haskell.org/haskellwiki/Higher_order_function"

Categories: Glossary | Idioms