Pattern matching, type inference, data types, pattern matching, continuations.
Readings: Ullman, ch 1-4, 5 (optional)
: SML syntax fast loop-up book
: SML tutorial written by TAs at CMU.
Overview
Functional: functions as first-class values
Garbage collected
Strict evaluation (applicative order)
No coercion
Strong and static typing
parametric polymorphism
structural equivalence
all with type inference
Advanced module system
Exceptions
Miscellaneous features
datatypes (merge of enumerated literals and variant records)
pattern matching
ref type constructor (like const pointers)
(* Comments *)val k = 5;
List operations
1::[2,3];
=> val it = [1, 2, 3] : int list
(* whether empty or not *)
null [1, 2];
=> val it = false : bool
hd [1, 2, 3];
=> val it = 1 : int
tl [1, 2, 3];
=> val it = [2,3] : int list
(* concatenation of lists *)
[1, 2, 3] @ [2, 3, 4];
=> val it = [1,2,3,2,3,4] : int list
Functions
(* named *)
fun abs x = if x >= 0.0 then x else ~x;
(* anonymous *)
fn x => if x >= 0.0 then x else ~x;
(* pattern-matching style *)
fun length [] = 0
| length (x::xs) = 1 + length xs;
(* multiple arguments *)
fun add (a, b) = a + b; (* pass a tuple *)
fun add a b = a + b; (* currying *)
Type notation α → β → δ means α → (β → δ)
let local scope
fun findroot (a, x, acc) =
let val nextx = (a / x + x) / 2.0
in
if abs (x - nextx) < acc * x
then nextx
else findroot (a, nextx, acc)
end
datatype tree = Leaf of int
| Node of tree * tree;
tree is a type constructor.
Leaf and Node are data constructors:
Leaf : int → tree
Node : tree * tree → tree
Pattern matching for datatypes
We can define functions by pattern matching:
fun sum (Leaf t) = t
| sum (Node (t1, t2)) = sum t1 + sum t2;
or
fun sum x = case x of Leaf t => t
| Node (t1, t2) => sum t1 + sum t2;
Functions accepting data constructors as arguments must provide an exhaustive definition(cover every data constructor for the datatype).
Parameterized datatypes (with type variables)
datatype 'a gentree =
Leaf of 'a
| Node of 'a gentree * 'a gentree;
val names = Node (Leaf "this", Leaf "that");
Common idiom: option
option is a built-in datatype:
datatype 'a option = NONE | SOME of 'a;
A lookup function using option:
fun lookup eq key [] = NONE
| lookup eq key ((k,v)::kvs) =
if eq (key, k)
then SOME v
else lookup eq key kvs;
Type of lookup is (α1*α2→bool) → α1 → (α2*β)list → βoption.
Signature and structures
An ML signature specifies an interface for a module.
signature STACKS =
sig
type stack
exception Underflow
val empty : stack
val push : char*stack->stack
val pop : stack->char*stack
val isEmpty : stack->bool
end
A structure implementing it would be:
structure Stacks : STACKS =
struct
type stack = char list
exception Underflow
val empty=[]
val push=op::
fun pop (c::cs) = (c, cs)
| pop [] = raise Underflow
fun isEmpty [] = true
| isEmpty _ = false
end
Signature ascription
Opaque ascription (:>) hides the identity of types beyond that which is conveyed in the signature. That is, additional type information provided by the structure will be considered abstract.
Transparent ascription (:) exposes the identity of types beyond that conveyed in the signature. That is, additional type information provided by the structure will augment the signature.
both prohibit the introduction of identifiers not already present in the signature. This is component hiding.
both permit types (in structures) which are broader than the signature.
Examples:
signature SetSignature =
sig
type ’a set
val empty : ’’a set
val singleton : ’’a -> ’’a set
end;
structure Set =
struct
type ’a set = ’a list;
val empty = [];
fun singleton a = [a]
val aux = [];
end;
(* Opaque ascription *)
structure Set2 :> SetSignature = Set;
Set2.aux ; (* error - component hiding *)
Set2.singleton (2) = [2]; (* error - list representation hidden *)
(* Transparent ascription *)
structure Set2 : SetSignature = Set;
Set2.aux ; (* error - component hiding *)
Set2.singleton (2) = [2]; (* okay *)
Functor
A functor creates a structure from a structure.
signature TOTALORDER =
sig
type element;
val lt : element * element -> bool;
end ;
functor MakeBST (Lt : TOTALORDER):
sig
type ’label btree;
exception EmptyTree;
val create : Lt.element btree;
val lookup : Lt.element * Lt.element btree -> bool ;
val insert : Lt.element * Lt.element btree -> Lt.element btree;
val deletemin : Lt.element btree -> Lt.element * Lt.element btree;
val delete : Lt.element * Lt.element btree -> Lt.element btree;
end =
struct
open Lt ;
datatype ’label btree = Empty |
Node of ’label * ’label btree * ’label btr...
val create = Empty;
fun lookup (x, Empty) = ...;
fun insert (x, Empty) = ...;
exception EmptyTree;
fun deletemin (Empty) = ...;
fun delete (x , Empty) = ...;
end;
Invoke the functor:
structure String : TOTALORDER =
struct
type element = string ;
fun lt (x, y) =
let
fun lower (nil) = nil |
lower (c::cs ) =
(Char.toLower c)::lower(cs);
in
implode(lower(explode(x))) <
implode(lower(explode(y)))
end ;
end ;
structure StringBST = MakeBST (String);