Introduction to Programming in ATS:
PrevChapter 3. FunctionsNext

Higher-Order Functions

A higher-order function is a function that take another function as its argument. For instance, the following defined function rtfind is a higher-order one: 

fun rtfind
  (f: int -> int): int = let
  fun loop (
    f: int -> int, n: int
  ) : int =
    if f(n) = 0 then n else loop (f, n+1)
  // end of [loop]
in
  loop (f, 0)
end // end of [rtfind]

Given a function from integers to integers, rtfind searches for the first natural number that is a root of the function. For instance, calling rtfind on the polynomial function lam x => x * x - x - 110 returns 11. Note that rtfind loops forever if it is applied to a function that does not have a root.

Higher-order functions can greatly facilitate code reuse, and I now present a simple example to illustrate this point. The following defined functions sum and prod compute the sum and product of the integers ranging from 1 to a given natural number, respectively: 

fun sum (n: int): int = if n > 0 then sum (n-1) + n else 0
fun prod (n: int): int = if n > 0 then prod (n-1) * n else 1

The similarity between the functions sum and prod is evident. We can define a higher-function ifold and then implement sum and prod based on ifold: 

//
fun ifold
  (n: int, f: (int, int) -> int, ini: int): int =
  if n > 0 then f (ifold (n-1, f, ini), n) else ini
//
fun sum (n: int): int = ifold (n, lam (res, x) => res + x, 0)
fun prod (n: int): int = ifold (n, lam (res, x) => res * x, 1)
//

If we ever want to compute the sum of the squares of the integers ranging from 1 to a given natural number n, we can readily do it by defining a function based on ifold as follows: 

fun sqrsum (n: int): int = ifold (n, lam (res, x) => res + x * x, 0)

Suppose we generalize sqrsum to the following function sqrmodsum in order to compute the sum of the squares of the integers ranging from 1 to n that are multiples of a given number d: 

fun sqrmodsum
  (n: int, d: int): int =
  ifold (n, lam (res, x) => if x mod d = 0 then res + x * x else res, 0)
// end of [sqrmodsum]

For someone unfamilar with the distinction between an envless function and a closure-function, it may be a bit suprising to learn that this generalization does not actually work. The simple reason is that ifold expects its second argument to be an envless function but the function passed to ifold in the body of sqrmodsum is clearly not envless (due to its use of d). To address the issue, we can implement a variant of ifold as follows and then implement sqrmodsum based on this variant: 

//
fun
ifold2
(
  n: int, f: (int, int) -<cloref1> int, ini: int
) : int =
  if n > 0 then f (ifold2 (n-1, f, ini), n) else ini
// end of [ifold2]
//
fun
sqrmodsum
(n: int, d: int): int =
  ifold2(n, lam (res, x) => if x mod d = 0 then res + x * x else res, 0)
// end of [sqrmodsum]
//

While ifold2 is indeed more general than ifold, this generality does come with a price. Whenever sqrmodsum is called, a closure-function must be created on heap and then passed to ifold2; this closure-function is of no further use after the call returns and the memory it occupies can only be properly relcaimed through garbage collection (GC). Therefore, calling functions like sqrmodsum can readily result in memory leaks in a setting where GC is not available. Fortunately, there are also linear closure-functions in ATS, which do not cause any memory leaks even in the absence of GC as they are required to be explicitly freed by the programmer. I will cover this interesting programming feature elsewhere.

As more features of ATS are introduced, higher-order functions will become even more effective in facilitating code reuse.

PrevHomeNext
Envless Functions and Closure-FunctionsUpExample: Binary Search for Fun