# 4.1. Higher-Order Functions¶

Consider these functions `double`

and `square`

on integers:

```
let double x = 2 * x
let square x = x * x
```

```
val double : int -> int = <fun>
```

```
val square : int -> int = <fun>
```

Let’s use these functions to write other functions that quadruple and raise a number to the fourth power:

```
let quad x = double (double x)
let fourth x = square (square x)
```

```
val quad : int -> int = <fun>
```

```
val fourth : int -> int = <fun>
```

There is an obvious similarity between these two functions: what they do is
apply a given function twice to a value. By passing in the function to another
function `twice`

as an argument, we can abstract this functionality:

```
let twice f x = f (f x)
```

```
val twice : ('a -> 'a) -> 'a -> 'a = <fun>
```

The function `twice`

is higher-order: its input `f`

is a function.
And—recalling that all OCaml functions really take only a single
argument—its output is technically `fun x -> f (f x)`

, so `twice`

returns
a function hence is also higher-order in that way.

Using `twice`

, we can implement `quad`

and `fourth`

in a uniform way:

```
let quad x = twice double x
let fourth x = twice square x
```

```
val quad : int -> int = <fun>
```

```
val fourth : int -> int = <fun>
```

## 4.1.1. The Abstraction Principle¶

Above, we have exploited the structural similarity between `quad`

and `fourth`

to save work. Admittedly, in this toy example it might not seem like much work.
But imagine that `twice`

were actually some much more complicated function. Then
if someone comes up with a more efficient version of it, every function written
in terms of it (like `quad`

and `fourth`

) could benefit from that improvement in
efficiency, without needing to be recoded.

Part of being an excellent programmer is recognizing such similarities and
*abstracting* them by creating functions (or other units of code) that implement
them. Bruce MacLennan names this the **Abstraction Principle** in his textbook
*Functional Programming: Theory and Practice* (1990). The Abstraction Principle
says to avoid requiring something to be stated more than once; instead, *factor
out* the recurring pattern. Higher-order functions enable such refactoring,
because they allow us to factor out functions and parameterize functions on
other functions.

Besides `twice`

, here are some more relatively simple examples, indebted also to
MacLennan:

**Apply.** We can write a function that applies its first input to its second
input:

```
let apply f x = f x
```

```
val apply : ('a -> 'b) -> 'a -> 'b = <fun>
```

Of course, writing `apply f`

is a lot more work than just writing `f`

.

**Pipeline.** The pipeline operator, which we’ve previously seen, is a
higher-order function:

```
let pipeline x f = f x
let (|>) = pipeline
let x = 5 |> double
```

```
val pipeline : 'a -> ('a -> 'b) -> 'b = <fun>
```

```
val ( |> ) : 'a -> ('a -> 'b) -> 'b = <fun>
```

```
val x : int = 10
```

**Compose.** We can write a function that composes two other functions:

```
let compose f g x = f (g x)
```

```
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
```

This function would let us create a new function that can be applied many times, such as the following:

```
let square_then_double = compose double square
let x = square_then_double 1
let y = square_then_double 2
```

```
val square_then_double : int -> int = <fun>
```

```
val x : int = 2
```

```
val y : int = 8
```

**Both.** We can write a function that applies two functions to the same
argument and returns a pair of the result:

```
let both f g x = (f x, g x)
let ds = both double square
let p = ds 3
```

```
val both : ('a -> 'b) -> ('a -> 'c) -> 'a -> 'b * 'c = <fun>
```

```
val ds : int -> int * int = <fun>
```

```
val p : int * int = (6, 9)
```

**Cond.** We can write a function that conditionally chooses which of two
functions to apply based on a predicate:

```
let cond p f g x =
if p x then f x else g x
```

```
val cond : ('a -> bool) -> ('a -> 'b) -> ('a -> 'b) -> 'a -> 'b = <fun>
```

## 4.1.2. The Meaning of “Higher Order”¶

The phrase “higher order” is used throughout logic and computer science, though not necessarily with a precise or consistent meaning in all cases.

In logic, *first-order quantification* refers primarily to the universal and
existential (\(\forall\) and \(\exists\)) quantifiers. These let you quantify over
some *domain* of interest, such as the natural numbers. But for any given
quantification, say \(\forall x\), the variable being quantified represents an
individual element of that domain, say the natural number 42.

*Second-order quantification* lets you do something strictly more powerful,
which is to quantify over *properties* of the domain. Properties are assertions
about individual elements, for example, that a natural number is even, or that
it is prime. In some logics we can equate properties with sets of individual,
for example the set of all even naturals. So second-order quantification is
often thought of as quantification over *sets*. You can also think of properties
as being functions that take in an element and return a Boolean indicating
whether the element satisfies the property; this is called the *characteristic
function* of the property.

*Third-order* logic would allow quantification over properties of properties,
and *fourth-order* over properties of properties of properties, and so forth.
*Higher-order logic* refers to all these logics that are more powerful than
first-order logic; though one interesting result in this area is that all
higher-order logics can be expressed in second-order logic.

In programming languages, *first-order functions* similarly refer to functions
that operate on individual data elements (e.g., strings, ints, records,
variants, etc.). Whereas *higher-order function* can operate on functions, much
like higher-order logics can quantify over over properties (which are like
functions).

## 4.1.3. Famous Higher-order Functions¶

In the next few sections we’ll dive into three of the most famous higher-order functions: map, filter, and fold. These are functions that can be defined for many data structures, including lists and trees. The basic idea of each is that:

*map*transforms elements,*filter*eliminates elements, and*fold*combines elements.