Higher order function

From HaskellWiki
Revision as of 05:09, 14 January 2007 by BrettGiles (talk | contribs) (Page to explain higher order functions.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


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


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


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


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