Higher-Order Functions

The core of ATS is a functional language in which functions are first-class values. A higher-order function is a function whose arguments also include functions.

Let us use BT to range over base types such as char, double, int, string, etc. A simple type T is formed according to the following inductive definition:

BT is a simple type.
(T_1, ..., T_n) -> T_0 is a simple type if T_0, T_1, ..., T_n are simple types.

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

order(BT) = 0
order((T_1, ..., T_n) -> T_0) = max (order(T_0), 1 + order (T_1), ..., 1 + order(T_n))

Given a function f of simple type T, we 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 higher-order functions are 2nd-order.

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


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

The function find_root computes f(0), f(1), f(-1), f(2), f(-2), ... until it finds the first integer i satisfying f(i) = 0.

As another example, we implement the Newton-Raphson's method for finding roots of functions on reals:


val epsilon = 1E-6 (* precision *)

// Newton-Raphson's method for finding roots
// [f1] is a derivative of [f]
fn newton_raphson (
    f: double -<cloref1> double
  , f1: double -<cloref1> double
  , x0: double
  ) : double = let
  fun loop (
      f: double -<cloref1> double
    , f1: double -<cloref1> double
    , x0: double
    ): double = let
    val y0 = f x0
  in
    if abs (y0 / x0) < epsilon then x0 else begin
      let val y1 = f1 x0 in loop (f, f1, x0 - y0 / y1) end
    end
  end // end of [loop]
in
  loop (f, f1, x0)
end // end of [newton_raphson]

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

The code used for illustration is available here.