SML

Begin learning Standard ML.

Elements of ML

Build lists using [] or the cons operator, which is ::.

[];
4::[];

Produces a list int containing 4.

ML is a functional programming language: programs are functions (functions have types), running a program is evaluating an expression, no side effects in expressions (referential transparency).

val is a keyword for declaring a new variable and binding it to a value.

val z = 3;
val y = z + 1;
val z = 1;
y; 

The last line produces 4. This isn’t an assignment; y retains the value it was initially given. ML doesn’t re-evaluate it when z changes.

Types of functions

• -> is used for types of functions.
• it associates right; int -> int -> int means int -> (int -> int).

Know how to specify right and left associativity in a grammar for the midterm!

Functions

val fname = (fn x => x+1);

• val introduces a new name
• fn introduces a new function definition-this is the function of x that returns x+1

Recursion

val rec defines a recursive function. fun fname(...); is syntactic sugar for val rec fname = fn(...);.

Pattern Matching

fun toString 0 = "zero"
    | toString 1 = "one"
    | toString 2 = "two";

The language starts at the top and evaluates each case. An underscore _ matches anything.

Pattern matching on lists

fun sumList [] = 0
    | sumList (x::xs) = x + sumList xs;

This is an fn : int list -> int.

fun size [] = 0
    | size (x::xs) = 1 + size xs;

This is a fn : 'a list -> int. 'a is a type variable. 'a list is a list of any type, and so size is a polymorphic function.

Higher order functions

Takes other functions as arguments or returns functions.

fun incby x y = x + y

This is a fn : int -> int -> int. You can partially evaluate it with e.g., incby 2! This returns a function fn : int -> int.

ML assumes the type of int. To use reals, need to specify fun incby (x::real) y = x + y.

fun map f [] = []
    | map f (x::xs) = (f x) :: map f xs

This is a val map = fn: ('a -> 'b) -> 'a list -> 'b list.

f takes an x of type 'a and produces something of type 'b. Then this “cons’d” with a list of 'b things. The intermediate 'a list represents the second argument of map, which contains the remaining 'a things that need to get “mapped”.