## 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.