Table of Contents
Chapter 6 – Case Analysis
Tuple types are homogeneous e.g. all values of type int*real are pairs containing an int and a real. Match failures occur at compile time. Types that have more than one form, such as int, are heterogeneous. Pattern matches fail at run time as a bind failure.
ML defines functions over heterogeneous types using clausal function expressions. For example:
fn pat1 => exp1
| pat2 => exp2
| ...
| patn => expn
Each component pat => exp is called a clause, or a rule. The entire assembly of rules is a called a match. For example:
val recip : int -> int =
fn 0 => 0 | n:int => 1 div n
The fun notation is generalized so we can be more concise:
fun recip 0 = 0
| recip (n:int) = 1 div n
Case analysis on the values of a heterogeneous type is performed by application of a clausally-defined function. The notation:
case exp
of pat1 => exp1
| ...
| patn => expn
is short for the application:
(fn pat1 => exp1
| ...
| patn => expn)
exp
Matches are subject to two forms of “sanity check” – exhaustiveness checking and redundancy checking.
Chapter 7 – Recursive Functions
For a function to be able to call itself, it needs a name. For example:
val rec factorial : int->int =
fn 0 => 1 | n:int => n * factorial (n-1)
or using fun notation:
fun factorial 0 = 1
| factorial (n:int) = n * factorial (n-1)
Iteration
If we define a helper function that accepts an accumulator we can reduce the storage needed:
fun helper (0,r:int) = r
| helper (n:int,r:int) = helper (n-1,n*r)
fun factorial (n:int) = helper (n,1)
It’s better programming style to hide the helper function w/in a local declaration:
local
fun helper (0,r:int) = r
| helper (n:int,r:int) = helper (n-1,n*r)
in
fun factorial (n:int) = helper (n,1)
end
Tail recursive functions are analogous to loops in imperative languages – they iterate the computation w/o needing auxiliary storage.
Mutual Recursion
Definitions which are mutually recursive can be joined together with the and keyword to indicate they are defined simultaneously by mutual recursion:
fun even 0 = true
| even n = odd (n-1)
and odd 0 = false
| odd n = even (n-1)
Chapter 8 – Type Inference and Polymorphism
Standard ML allows you to omit type information whenever it can be determined from context. Consider the following:
fn s:string => s ^ "\n"
There is no need to declare the type of s since it can be inferred from the context, so we may write:
fn s => s ^ "\n"
A type scheme is a type expression involving one or more type variables standing for an unknown, but arbitrary type expression. Type variables are written ‘a (pronounced alpha), ‘b (pronounced beta), etc. For example, the type scheme ‘a->’a has instances int->int, string->string, (int*int)->(int*int), and (’b->’b)->(’b->’b), etc. It does not have the type int->string.
We may bind an identity function to the variable I as follows:
val I : 'a->'a = fn x=>x
We may also write:
fun I(x:'a) : 'a = x
Standard ML eliminates the need to ascribe a type scheme to the variable:
val I = fn x=>x
or
fun I(x) = x
Chapter 9 – Programming with Lists
The values of type type list are the finite lists of values of type type:
1. nil is a value of type typ list.
2. if h is a value of type typ, and t is a value of type typ list,
then h::t is a value of type typ list.
3. Nothing else is a value of type typ list.
The type expression typ list is a postfix notation for the application of the type constructor list to the type typ.
A value val of type typ list has the form:
val1 :: (val2 :: (… :: (valn :: nil) … ))
The :: operator is right-associative, so we may omit parentheses:
val1 :: val2 :: … :: valn :: nil
Or, we may use list notation:
[ val1, val2, ..., valn ]
Computing With Lists
Some examples:
fun length nil = 0
| length (_::t) = 1 + length t
Note we do not give a name to the head of the list, instead we use a wildcard _
fun append (nil, l) = l
| append (h::t, l) = h :: append (t, l)
The latter is built into Standard ML and is written using infix as: exp1 @ exp2
fun rev nil = nil
| rev (h::t) = rev t @ [h]
The running time of the latter is O(n2). The following definition makes use of an accumulator and has a running time of O(n):
local
fun helper (nil, a) = a
| helper (h::t, a) = helper (t, h::a)
in
fun rev' l = helper (l, nil)
end
Chapter 10 – Concrete Data Types
Non-Recursive Datatypes
Example of nullary i.e. zero argument, constructors:
datatype suit = Spades | Hearts | Diamonds | Clubs
It is conventional to capitalize the names of value constructors, but this is not required by the language.
Datatypes may be parameterized by a type:
datatype 'a option = NONE | SOME of 'a
The values are NONE or Some val, where val is a value of type typ. The option type constructor is pre-defined in Standard ML.
Option types can also be used in aggregate data structures:
type entry = { name:string, spouse string option }
An entry for an unmarried person would have a spouse field with a value of NONE.
Recursive Datatypes
datatype 'a tree =
Empty |
Node of 'a tree * 'a * 'a tree
1. The empty tree Empty is a binary tree.
2. If tree_1 and tree_2 are binary trees, and val is a value of type type, then Node (tree_1, val, tree_2) is a binary tree.
3. Nothing else is a binary tree.
A function to compute the height of a binary tree, and one to compute the number of nodes:
fun height Empty = 0
| height (Node (lft, _, rht)) = 1 + max (height lft, height rht)
fun size Empty = 0
| size (Node (lft, _, rht)) = 1 + size lft + size rht
Heterogeneous Data Structures
The tree data type above requires that the type of the data items at the nodes must be the same for every node of the tree. To represent a heterogeneous tree, the data item must be labelled with enough info to determine the type at run-time.
datatype int_or_string =
Int of int |
String of string
type int_or_string =
int_or_string tree
Datatype declarations and pattern matching can be useful for manipulating the abstract syntax of a language. Consider an example representing arithmetic expressions:
datatype expr =
Numeral of int |
Plus of expr * expr |
Times of expr * expr
fun eval (Numeral n) = Numeral n
| eval (Plus (e1, e2)) =
let
val Numeral n1 = eval e1
val Numeral n2 = eval e2
in
Numeral (n1+n2)
end
| eval (Times (e1, e2)) =
let
val Numeral n1 = eval e1
val Numeral n2 = eval e2
in
Numeral (n1*n2)
end
If we extend the expr datatype as follows:
datatype expr =
Numeral of int |
Plus of expr * expr |
Times of expr * expr
Recip of expr
The compiler will complain about eval being incompatible with the new version of expr. Recompiling eval will produce an inexhaustive match warning since eval lacks a case for Recip. This is one of the benefits of static typing provided in Standard ML.
