Let expressions

let val x = expr_1 in expr_2 end;

The value of the entire let expression is the value of expr_2. x is a new variable that is binded to the result of expr_1. The binding is local to the let expr.

Example:

fun rev x = let val(a,b) = rev2(x, []) in b end;

which is a val rev = fn : 'a list -> 'a list. The result is accumulated in b and returned in x.

Logical conditionals in ML

  • orelse is or
  • andalso is and

Strange!

Infix operators

Can have any precedence in 0 to 9. Can be left associative, or right-associative if infixr is used.

Example:

Function to indicate if item is in a list,

infix mem;
fun(x mem []) = false
  | (x mem (y::ys)) = x=y orelse (x mem ys);

Note that mem only works with types that have an equality test defined. Denoted as ''a. This is called constrained polymorphism, since not any old type can be used! Built into the language.

Custom data types

keyword datatype. Use pattern-matching to indicate valid constructors.

Example:

datatype Person = Queen 
  | Peer of string * string * int
  | Peasent of string
  | Knight of string
  | ...

Functions over a user defined type can be defined using patterns over constructors. Note that concatenating strings is done with the ^ character, e.g., "Sir" ^ name.

fun title Queen = "Her majesty the Queen"
    | title (Peer (deg, terr,_)) = "The " ^ deg ^ " of " ^ terr
    ...

This is var title = fn: person -> string.

Datatypes are the disjoint union of their constructors- labeled disjoint types. They are polymorphic as well.

Example:

datatype ('a, 'b) union = ln1 of 'a | ln2 of 'b;
val v1 = [ln1 "hello", ln1 "bye", ln2 3, ln1 "adios"];

This is val v1 = [...] : (string, int) union list. Type inference~

Example:

datatype bin_tree = leaf of int
  | node of bin_tree * bin_tree;

Simple tree: node(leaf 1, node(leaf 2, leaf 3));

Binding functions with Let

Let expressions can also locally bind functions to names. Useful for helper functions.

fun ordered (leaf n) = true
    | ordered (node(t1, t2)) = (max t1 <= min t2)
                               andalso (ordered t1)
                               andalso (ordered t2);

This is a val ordered = fn: bin_tree -> bool. Note that max and min are also helper functions. Can define max and min within ordered using let.

What if we wanted to express binary trees as (5, (3, 2))? Need to write a scanner and a parser for this grammar! Can do this in ML.

Case expressions

case E of P1 => E1 | ... | Pn => En

The value of E is matched against patterns P1, …, Pn. The value of the expression corresponding to the first pattern to match the value of E is the value of the expression.

Assume you have a list of scanned tokens from some inputs, ts. Recall, a binary tree should be (binTree, binTree).

fun binTree ts = 
    case ts of 
        (numlit x)::tr => tr
        | lparen::tr => 
            let val ts1 = binTree tr
            let val ts2 = case ts1 of 
                          comma::tr2 => tr2
                          | _ => raise parseError
            let val ts3 = binTree ts2
            val ts4 = case ts3 of 
                      rparen::tr4 => tr4
                      | _ => raise parseError
            in ts4 (* return remainder of the list of tokens *)
            end
        | _ => raise parseError

Putting function binTree together with our scanner scan,

fun parse s = 
    let val result = binTree (scan s)
    in result = []
    end;

which, if result is non-empty, means the parsing failed so the value returned is false.