Datatype Bindings

Example:

datatype newtype =
       TwoInts of int*int
       | Str of string
       | Pizza

newtype is a new type that is added to the environment.

TwoInts, Str, Pizza are constructors.

TwoInts and Str are also functions:

TwoInts : int*int -> newtype

Str : string -> newtype

Pizza has type newtype.

Usage:

val a = Str "hi"
val b = Str

a has type Str "hi" : newtype.

So the value has two components:

Tag (which constructor)
Data (value)

Examples of Datatypes

Enumerations

datatype suit = Club | Diamond | Heart | Spade

Student Records

datatype id = StudentNum of int
            | Name of string * (string option) * string

We can now identify a student either through an ID or a first and last name (middle is optional). But we cannot do both.

This is better than having a record with all these fields, but setting StudentNum to -1 if (s)he does not have one!

Obviously, this datatype does not work if every student has both a name and ID.

Recursive Definitions

datatype exp = Constant of int
             | Negate of exp
             | Add of exp*exp
             | Multiply of exp*exp

Add (Constant(10+9), Negate(Constant 4))

Here is how to evaluate an expression:

fun eval e =
  case e of
      Constant i => i
    | Negate e2 => ~ (eval e2)
    | Add (e1, e2) => (eval e1) + (eval e2)
    | Multiply (e1, e2) => (eval e1) * (eval e2)

eval(Add(Constant(3), Constant(4)))

Note: A fully recursive function with no if conditions!

Lists

datatype my_int_list = Empty
                     | Cons of int * my_int_list

val x = Cons(4, Cons(23, Cons(2008, Empty)))

In real lists, [] and :: are merely constructors. So you can do:

fun sum_list xs =
  case xs of
      [] => 0
    | x:xs' => x + sum_list xs'

This is preferred to hd, tl and null, as pattern matching will catch the lack of all cases, or redundant cases, etc. It also ensures not having to worry about exceptions if you call hd on an empty list, etc.

Note that :: is infix.

Polymorphic Datatypes

[] and :: are polymorphic type constructors. They can be used for any type.

This is how options are defined:

datatype 'a option = NONE | SOME of 'a

Here is how you would define a tree of any type:

datatype ('a, 'b) tree = Node of 'a*('a,'b) tree * ('a,'b) tree
                       | Leaf of 'b

If it is a Node, it has a value and a left and a right subtree. This definition allows the leafs to have a different type from the nodes.

Below is how you would define a list.

datatype 'a mylist = Empty | Cons of 'a * 'a mylist