PATTERNS

ML allows you to match arguments with *patterns* - structured descriptions of
  objects containing variables that are bound to remaining pieces of structure.
  Example:

fun fib(n) = if (n=0) then 0 
	     else if (n=1) then 1
   	     else fib(n-1) + fib(n-2);

This is a pain.  We have already seen case statements, but they have no
  "else" clause for the last case.  They can, however, employ patterns:

fun fib(n) = case n of
		 0 => 0	
	       | 1 => 1
	       | m => fib(m-1)+fib(m-2);

Here, m matches whatever n might be.  Since cases are tried in order,
  and m mathces anything, this is effectively an "else" clause.
ML has a more convenient syntax, however:

fun fib 0 = 0
  | fib 1 = 1
  | fib n = fib(n-1) + fib(n-2);

In this way, the function itself is defined in cases.
Another example:

fun listsum L = if (null L) then 0 else (hd L) + listsum (tl L);
listsum [1,2,3];

OR

fun listsum [] = 0
  | listsum L = (hd L) + listsum (tl L);

OR

fun listsum [] = 0
  | listsum (h::t) = h + listsum t;

And look what else ML does!
fun reverse (h::t) = reverse(t) @ [h];

Very useful for debugging...
Here's a clever idea that really benefits from patterns:

fun median x =
    let fun medhelp ((x1::x2::xt),(y1::yt)) = medhelp(xt,yt)
	  | medhelp (_,(median::_)) = median
	  (* traverse twice as fast through one list *)
    in
	medhelp(x,x)
    end;
median [1,2,3];
median [1,2,3,4];
median [];

IT
Use val to declare constants:
val seconds = 60;
val f = fn n => 2*n;  (* lambda expressions *)
it;   (* last value produced *)

WHY BOTHER WITH TYPING:
 - easier to debug programs: compiler can catch many errors: clashes, 
                             misspellings ...
 - efficiency: typing can be used for "static analysis" in compiler
               to generate quicker code
 - documentation: types declare your intent with well-chosen names
 - overloading/redundancy: also indicates a relevant abstraction

Some languages' type systems operate at compile-time, e.g., ML, Ada
Others operate at run-time, e.g., dynamic dispatch for virtual methods in C++

Typing at compile-time is called *static typing*
Explicit static typing: code contains declarations, e.g. C: int x,y,z;
But it's also possible to infer types:
  a3 := b4 + 1;
     what could a3 and b4 be?  We can tell because of + and 1!
  if (test) then ...
     what is test?  Must be bool!
This is called *type inferencing*

Sound type system: a type system in which all types can always be inferred in
  any valid program.
ML has a sound type system

RECORD TYPES
We have already seen tuples:
(1,2,"abc");
These are useful because they are flat and heterogeneous.

But you can also name the different dimensions:
{name="gerald penn",age=36,salary=1000000};
This is a RECORD (INSTANCE), a generalization of tuples, and 
  it has a RECORD TYPE.
# salary {name="gerald penn",age=36,salary=1000000};
# salary {name="gerald penn",age=36};

Tuples are shorthand for records with numerical fields:
# 3 (1,2,"abc");
# 3 {1=1,2=2,3="abc"};

TYPE SYNONYMS
type waitress = {name:string, age:int, salary:int, tips:int};
type waitresses = waitress list;

User-declared types can be used wherever built-in types can:
fun income (W:waitress) = # salary W + # tips W;
fun income (W) = # salary W + # tips W;
fun total ([]:waitresses) = 0
  | total (w::WL) = income w + total WL;
val f:waitress = {name="flo",age=45,salary=20000,tips=5000};
  (note type declaration)

On the other hand, patterns can also be used with records:
fun income {name=_,age=_,salary=S,tips=T} = S + T;
income f;
vs.
fun income {salary=S,tips=T} = S + T;
vs.
fun income ({salary=S,tips=T,...}:waitress) = S + T;  
(* This is a *flex record* *)

FUNCTION POLYMORPHISM: values (including variables or functions) that can
                       have more than one type

fun length L = if (null L) then 0 else 1 + length (tl L);

fun reverse [] = []
  | reverse (h::t) = reverse(t) @ [h];

fun listify x = [x];

fun apply (f,x) = (f x);
apply(real,5);

Without polymorphism, we would need many functions:
  int-length, int-reverse, real-length, real-reverse, etc.

There are three kinds of polymorphism:
  AD-HOC POLYMORPHISM: aka. overloading, different operations known by
    same name, which compiler/interpreter must resolve.
  INHERITANCE-BASED POLYMORPHISM: subclasses define new versions of methods
    possessed by superclass.  OO languages use this a lot.
    public class Employee{
        public int salary;
        public void income() = {return salary;}
    }
    public class Waitress extends Employee{
        public int tips;
        public void income() = {return (salary + tips);}
    public class Professor extends Employee;

  PARAMETRIC POLYMORPHISM: types/type variables explicitly used as parameters
     heterogeneous (C++): one copy of function code per instantiation of parms
     homogeneous (ML): one copy of code only - parameters used internally

Parameters can also be used in type declarations:
type 'a pair = 'a * 'a;
(1,2): int pair;

type 'a func = 'a -> 'a;
square: real func;

Certain operators restrict polymorphism:
  arithmetic: +,-,*,etc.
  division-related: / vs. div, mod
  inequality: <, >, etc.
  Boolean connectives: and, or, etc.
  string operators: ^, @
  type conversion: real, round, str
  equality: = ("equality types")

Others do not, e.g., tuples, list operators.

TYPE DEFINITIONS
type pound = real;
type kg = real;
fun kg_to_lbs (N:kg) = (N * 2.2): pound;
kg_to_lbs (1.0);
kg_to_lbs (1.0:pound);
kg_to_lbs (kg_to_lbs (1.0));

What's wrong here?

kg and pound are SYNONYMS for real - so ML doesn't really care which we use.

New types can be DEFINED using explicit TYPE CONSTRUCTORS;
datatype pound = lbs of real;
datatype kilogram = kg of real;
lbs 3.0;
kg 3.0;

fun kg_to_lbs (kg x) = lbs (x*2.2);
kg_to_lbs(1.0);
kg_to_lbs(kg 1.0);
kg_to_lbs(lbs 1.0);
kg_to_lbs(kg_to_lbs(kg 1.0));

There can be more than 1 constructor too:
datatype money = coins of int
	       | notes of int
	       | cheque of string * real;
cheque("cibc",100.70);
money is called a *variant type*.

In function definitions, pattern-matching then distinguishes among them:
fun amount (coins N) = real(N)/100.0
  | amount (notes N) = real(N)
  | amount (cheque (_,N)) = N;

Note the syntactic parallelism between variant type definitions and matching
  patterns in function definitions.  One exists in the world of types, the 
  other, in the world of objects.

We can use variant types to better cope with the homogeneity of ML's
polymorphic type system:
[1,2.0,3.5,4];

datatype number = r of real
		| i of int;
[i 1,r 2.0,r 3.5,i 4];

fun sumlist [] = 0.0
  | sumlist ((r x)::t) = x + sumlist(t)
  | sumlist ((i x)::t) = real(x) + sumlist(t);
sumlist [i 1,r 2.0,r 3.5,i 4];

User-defined datatypes can be recursive:
datatype tree = leaf of int
	      | node of tree * tree;

fun sumtree (leaf n) = n
  | sumtree (node(t1,t2)) = sumtree(t1) + sumtree(t2);
val t = node(leaf(3),node(leaf(2),leaf(5)));
sumtree t;

User-defined types can also be parametrically polymorphic:

datatype 'a tree = leaf of 'a
		 | node of ('a tree) * ('a tree);
leaf(2);
node(leaf("ab"),leaf("cd"));
node(leaf(2),leaf("cd"));

fun count (leaf _) = 1
  | count (node (t1,t2)) = count t1 + count t2;