ML (Meta Language)

SELECTED TOPICS FROM TEXT CHAPS 8 and 9

Standard ML handout.

8.2 TYPES

ML strongly typed with compile-time testing (rare for functional language)

Built-in basic types: int, real, bool, string

Create enumerated types with datatype keyword, e.g.

datatype direction = ne | se | sw | nw ;
datatype texture = arc | band;

Structured types:
a. list e.g. int list or direction list
b. product (tuple, compound type) e.g. type square = texture * direction;
c. function e.g. int -> bool

(function type describes mapping from input parms to return value)

e.g. square list -> int

ML will try to infer types from context

 

8.2 BASIC LIST OPERATIONS

'[' and ']' are list boundary characters

',' is list element separator

[] is the empty list

null(<list>) test for empty list

hd(<list>) returns head element

tl (<list>) returns tail list (list w/o head element)

:: infix operator to construct list (left operand is element, right is list)

examples:

1::[2,3] is [1,2,3]

1:: [ ] is [1]

hd ([1,2,3]) is 1

tl ([1,2,3]) is [2,3]

Exercise: given [1,2,3] what expression yields list containing second value?

 

8.3 and 8.4 FUNCTIONS AND CONTROL FLOW

function definition syntax already seen

conditional: if then else e.g. fun abs(n) = if n >=0 then n else 0-n

iteration by recursion e.g. fun len(x) = if null(x) then 0 else 1+len(tl(x))

Exercise: define recursive factorial?

defining functions by case e.g. fun len([ ]) = 0 | len(a::y) = 1 + len(y)
(equivalent to above)

 

9.3 FUNCTIONS AS FIRST CLASS VALUES

- assign to data structs, pass as args, return from functions

ML "map" function as example:

fun map f [ ] = [ ] 

| map f (a::y) = (f a):: (map f y)

(note some parentheses not specified -- this is OK.)

mechanism to apply arbitrary function f to each item in arbitrary list.

 

9.7 Little Quilt in ML. Annotated version of Figure 9.7:

 
(* enumerated types *)
datatype texture = arcs | bands;
datatype direction = ne | se | sw | nw;
(* type definitions *)
type square = texture * direction;
type row = square list;
type quilt = row list;

We've already seen some of these examples. A square has a texture and a direction. A row is a list of squares. A quilt is a list of rows. Thus is quilt is a list of lists. [ [...] [...] [...] ]

 

(* utility functions *)
fun clockwise ne = se
| clockwise se = sw
| clockwise sw = nw
| clockwise nw = ne;

Note that parentheses are omitted, and "parameters" are constants. The interpretation of these is obvious (pattern matching used to match argument to parameter).

 

fun turnsq(tex,dir) =(tex,clockwise dir):square;

Building block for "turn". Returns a new object of type "square" with the direction rotated.

 

fun emptyquilt ([]) = true
| emptyquilt([]::x) = emptyquilt(x:quilt)
| emptyquilt(_) = false;

First case is empty list.

Second case is list whose first element is an empty list (e.g. first row is emtpy list).

Third case is "otherwise"

 

exception fail;

Declares an exception. Use with "raise" (equiv. to "throw") and with "handle" (equiv. to "catch")

 

(* the 4 basic elements of Little Quilt: a,b,turn,sew *)
val a = [[ (arcs, ne) ]];
val b = [[ (bands, ne) ]];

Both a and b are single-square quilts, with the given texture and direction. Each quilt consists of a single row (list) and each row consists of a single square.

 

fun sew([],[]) = []:quilt
| sew(r::x, s::y) = (r@s) :: sew(x,y)
| sew(_) = raise fail;

(note Fig 9.7 has error in first line. ":quilt" should be at the end, not before the "=")

First case: sewing together two empty quilts yields empty quilt

Second case:

Third case: otherwise, raise exception (unequal heights).

If both quilts have same height, recursion leads eventually to first case. Otherwise, recursion leads eventually to third case (one of x or y is empty).

 

fun turn x = 
if emptyquilt x then nil
else rev(map(turnsq o hd) x) :: turn(map tl x);

 

"nil" is equivalent to empty list.

Strategy for nonempty quilt is this:
- extract a "column" (first square in every row) into a list
- turn each individual square in that list
- reverse the order of list elements (result is a row in solution)
- repeat first three steps for each "column" (the recursive part)

 

Break last line of code down into two majors parts:

1. rev(map(turnsq o hd) x)

'rev' is builtin function to reverse a list; 'o' is function composition operator.

map(turnsq o hd) x is equivalent to map turnsq (map hd x)

Translation: Apply 'hd' to every row in x to extract square and apply 'turnsq' on that square. This processes one "column" into a new list. Finally rev reverses it.

 

2. turn(map tl x)

Recursively apply turn to next "column".

With each recursive step, a "column" is turned into a row, which becomes the next row of the resulting quilt.

The two steps combine to process the 2D grid like a nested loop where step 1 is the inner loop based on column number and step 2 is the outer loop based on row number.

  

Related Home Pages: notes | CSC 326 | Peter Sanderson | Computer Science | SMSU

Last reviewed: 18 November 1999

Peter Sanderson ( PeteSanderson@mail.smsu.edu )