# Difference between revisions of "Higher order function"

## 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 [] = []
```

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)
```