## Programming in Standard ML – Part 3

## 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(*n*^{2}). 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.

## Leave a Reply