Introduction to Programming in ATS:
<<< PreviousFunctionsNext >>>

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
// end of [ifold]

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, we can readily define a function based on ifold to do it: 

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

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

<<< PreviousHomeNext >>>
Envless Functions and Closure FunctionsUpExample: Binary Search