Higher-order programming

As we have seen, functions defined by pattern matching associate patterns and expressions. Functions defined in this way are checked by Standard ML. One form of checking is to ensure that all of the patterns describe values from the same data type and all of the expressions produce values of the same type. Both of the functions below will be rejected because they do not pass these checks.

(* error *)
val wrong_pat = fn 1 => 1
                 | true => 1;

(* error *)
val wrong_exp = fn 1 => true
                 | n => "false";

Pattern matching provides subsequent checking which, if failed, will not cause the function to be rejected but will generate warning messages to call attention to the possibility of error. This subsequent checking investigates both the extent of the patterns and the overlap between them. The first version of the boolean negation function below is incomplete because the matches in the patterns are not exhaustive; there is no match for true. The second version has a redundant pattern; the last one. Both produce compiler warning messages.

(* warning *)
val not1 = fn false => true;

(* warning *)
val not2 = fn false => true
            | true  => false
            | false => false;

Both functions can be used. The first will only produce a result for false but because of the first-fit pattern matching discipline the second will behave exactly like the Bool.not function in the Standard ML library. The warning message given for the second version signals the presence of so-called dead code which will never be executed.

The checking of pattern matching by Standard ML detects flawed and potentially flawed definitions. However, this checking is only possible because the allowable patterns are much simpler than the expressions of the language. Patterns may contain constants and variables and the wild card which is denoted by the underscore symbol. They may also use constructors from a data type--so far we have only met a few of these including false and true from the bool data type and SOME and NONE from the option data type. Constructors are distinct from variables in patterns because constructors can denote only themselves, not other values. Patterns place a restriction on the use of variables; they may only appear once in each pattern. Thus the following function definition is illegal.

(* error *)
val same = fn (x, x) => true
            | (x, y) => false;

Similarly, patterns cannot contain uses of functions from the language. This restriction means that neither of the attempts to declare functions which are shown below are permissible.

(* error *)
val abs = fn (~x) => x
           | 0    => 0
           | x    => x;

(* error *)
val even = fn (x + x)     => true
            | (x + x + 1) => false;

Neither can we decompose functions by structured patterns, say in order to define a test on functions. Attempts such as the following are disallowed.

(* error *)
val is_identity = fn (fn x => x) => true
                   | _           => false;

However, we can use pattern matching to bind functions to a local name because one of the defining characteristics of functional programming languages is that they give the programmer the ability to manipulate functions as easily as manipulating any other data item such as an integer or a real or a word. Functions may be passed as arguments or returned as results. Functions may be composed in order to define new functions or modified by the application of higher-order functions.