Difference between revisions of "Higher order function"
Line 45:  Line 45:  
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 [] = [] 
Revision as of 20:49, 9 March 2007
Contents
Definition
A higher order function is a function that takes other functions as arguments.
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 the them 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
See also
Accumulator recursion where the accumulator is a higher order function is one interesting case of continuation passing style.