# Chapter 22. Higher-Order Functions

A higher-order function is one that takes another function as its argument. Let us use BT to range over base types such as int, bool, char, double and string. A simple type T is formed according to the following inductive definition:

• BT is a simple type.

• (T1, ..., Tn) -> T0 is a simple type if T0, T1, ... Tn are simple types.

Let order be a function from simple types to natural numbers defined as follows:

• order(BT) = 0

• order((T1, ..., Tn) -> T0) = max(order(T0), 1 + order(T1), ..., 1 + order(Tn))

Given a function f of some simple type T, let us say that f is a nth-order function if order(T) = n. For instance, a function of the type (int, int) -> int is 1st-order, and a function of the type int -> (int -> int) is also 1st-order, and a function of the type ((int -> int), int) -> int is 2nd-order. In practice, most functions are 1st-order and most higher-order functions are 2nd-order.

As an example, let us implement as follows a 2nd-order function find_root that takes as its only argument a function f from integers to integers and searches for a root of f by enumeration:

```fn find_root
(
f: int -<cloref1> int
) : int = let
//
fun loop
(
f: int -<cloref1> int, n: int
) : int =
if f (n) = 0 then n else (
if n <= 0 then loop (f, ~n + 1) else loop (f, ~n)
) // end of [else] // end of [if]
in
loop (f, 0)
end // end of [find_root]
```

The function find_root computes the values of f at 0, 1, -1, 2, -2, etc. until it finds the first integer n in this sequence that satisfies f(n) = 0.

As another example, let us implement as follows the famous Newton-Raphson's method for finding roots of functions on reals:

```typedef
fdouble = double -<cloref1> double
//
macdef epsilon = 1E-6 (* precision *)
//
// [f1] is the derivative of [f]
//
fun
newton_raphson
(
f: fdouble, f1: fdouble, x0: double
) : double = let
fun loop (
f: fdouble, f1: fdouble, x0: double
) : double = let
val y0 = f x0
in
if abs (y0 / x0) < epsilon then x0 else
let val y1 = f1 x0 in loop (f, f1, x0 - y0 / y1) end
// end of [if]
end // end of [loop]
in
loop (f, f1, x0)
end // end of [newton_raphson]
```

With newton_raphson, both the square root function and the cubic root function can be readily implemented as follows:

```// square root function
fn sqrt (c: double): double =
newton_raphson (lam x => x * x - c, lam x => 2.0 * x, 1.0)
// cubic root function
fn cbrt (c: double): double =
newton_raphson (lam x => x * x * x - c, lam x => 3.0 * x * x, 1.0)
```

Higher-order functions can be of great use in supporting a form of code sharing that is both common and flexible. As function arguments are often represented as heap-allocated closures that can only be reclaimed through garbage collection (GC), higher-order functions are used infrequently, if at all, in a setting where GC is not present. In ATS, linear closures, which can be freed explictly in a safe manner, are available to support higher-order functions in the absence of GC, making it possible to employ higher-order functions extensively in systems programming (where GC is unavailable or simply disallowed). The details on linear closures are to be given elsewhere.

Please find on-line the entirety of the code used in this chapter.