Functions as values

Functions can be used as values. By treating them as data, they can be stored in variables, and passed to other functions. This lesson shows one example of how that can be useful.

Consider the following list of numbers:

alg list real nrs = [0.5, 1.3, 0.1, 2.7, 1.4];

Now assume we wanted to sort these numbers both in increasing and in decreasing order, using a single sorting function:

alg list real inc = sort(nrs, cmp_inc); // [0.1, 0.5, 1.3, 1.4, 2.7]
alg list real dec = sort(nrs, cmp_dec); // [2.7, 1.4, 1.3, 0.5, 0.1]

Variable inc contains the same numbers as nrs, but sorted in increasing order, while dec contains them in decreasing order. We use the same sort function in both cases, but with different comparison functions:

func bool cmp_inc(real a, b):
  return a <= b;
end

func bool cmp_dec(real a, b):
  return a >= b;
end

Function cmp_inc takes two real numbers and returns true only if the first number is smaller than the second one (a and b are in increasing order). Function cmp_dec has the same parameters, but returns true only if the first number is larger than the second one (a and b are in decreasing order). The sort function is defined as follows:

func list real sort(list real xs; func bool (real, real) cmp):
  int i = 1, j;
  real x;

  while i < size(xs):
    j := i;
    while j > 0 and not cmp(xs[j-1], xs[j]):
      // swap x[j-1] and x[j]
      x := xs[j-1];
      xs[j-1] := xs[j];
      xs[j] := x;
      j := j - 1;
    end
    i := i + 1;
  end
  return xs;
end

The sort function has two parameters. The first parameter is xs, which contains the values to sort. The second parameter is cmp, the compare function to use to determine whether two numbers are correctly ordered. The cmp parameter has type func bool (real, real), which means that a function that has two real parameters and a boolean return value is required. The cmp_inc and cmp_dec functions satisfy these requirements, and can be used as second argument when the function is called to determine the values of algebraic variables inc and dec.

The sort function implements a standard insertion sort algorithm. The cmp parameter is used in the sort function to compare two consecutive values in xs, and swap them if they are not correctly ordered.

The cmp parameter of the sort function has a function type, allowing compare functions to be passed to the sort function, as data. This allows the sort function to sort lists of numbers in different orders, depending on the compare function that is provided.