Exercise #3

Pattern matching

Standard ML supports pattern matching on parameters, which is a syntactic simplification over if...then...else expressions (which can also be compiled slightly more efficiently in many cases). This allows a function to be "overloaded" based on the values of its arguments, as opposed to its types. For example, the function

   fun not (false) = true
     | not (true)  = false;

inverts a boolean. Patterns behave as if examined in the order defined; this means that

   fun divby (0) = 0
     | divby (1) = 1024
     | divby (x) = 1024 div x;

(which divides 1024 by its argument unless the argument is zero) will not evaluate the division if the first case matches.

Using pattern matching, implement a nor function which takes two boolean arguments and returns whether neither of them is true.
SML allows a so-called wildcard name, \it{underscore} (_) to be used, which matches anything. Using this, implement nand, which takes two boolean arguments and returns whether either of them is false.
Determine what SML does if you have redundant patterns, i.e. if a later option is completely covered by an earlier one.
Before moving on to the next question, familiarise yourself with the infix operator (::) on lists. Determine what the operator does.
Note that operators like this one are often referred to as constructors. Constructors, unlike "normal" functions and operators, can be used as parts of the patterns we use for pattern matching.
Using pattern matching and the (::) constructor as part of a pattern, re- implement the find0 function from exercise #2.

Standard ML is installed at /tools/cs/smlnj/bin/sml on the CSEL machines.