Conceptual Ways to Build New Types
To create a compound type, there are really only three essential building blocks. Any decent programming language provides these building blocks in some way:
 Eachof: A compound type t describes values that contain each of values of type t1, t2, …, and tn. Tuples are an example: int * bool describes values that contain an int and a bool. A Java class with fields is also an eachof sort of thing.
 Oneof: A compound type t describes values that contain a value of one of the types t1, t2, …, or tn. For a type that contains an int or a bool in ML, we need
datatype bindings
. In objectoriented languages with classes like Java, oneof types are achieved with subclassing, but that is a topic for much later in the course.  Selfreference: A compound type t may refer to itself in its definition in order to describe recursive data structures like lists and trees. This is useful in combination with eachof and oneof types. For example, int list describes values that either contain nothing or contain an int and another int list.
Records: Another Approach to Eachof Types
Record types are “eachof” types where each component is a named field
.
1  {foo : int, bar : int*bool, baz : bool*int} 
In ML, we do not have to declare that we want a record type with particular field names and field types — we just write down a record expression and the typechecker gives it the right type.
Now that we know how to build record values, we need a way to access their pieces. For now, we will use #foo e
where foo
is a field name.
The truth of tuple
In fact, this is how ML actually defines tuples: A tuple is a record. That is, all the syntax for tuples is just a convenient way to write down and use records. The REPL just always uses the tuple syntax where possible, so if you evaluate {2=1+2, 1=3+4} it will print the result as (7,3). Using the tuple syntax is better style, but we did not need to give tuples their own semantics: we can instead use the “another way of writing” rules above and then reuse the semantics for records.
This is the first of many examples we will see of syntactic sugar
. We say, Tuples are just syntactic sugar for records with fields named 1, 2, …, n.
1  val z = (3,7) : int * int 
Datatype Bindings: Our Own Oneof Types
We now introduce datatype bindings, our third kind of binding after variable bindings and function bindings.
1  datatype mytype = TwoInts of int * int 
Roughly, this defines a new type where values have an int int or a string or nothing. Any value will also be tagged
with information that lets us know which variant it is: These tags, which we will call *constructors, are TwoInts
, Str
, and Pizza
.
More precisely, the example above adds four things to the environment:
 A new type mytype that we can now use just like any other type
 Three constructors TwoInts, Str, and Pizza
A constructor is two different things. First, it is either a function for creating values of the new type (if the variant has of t for some type t) or it is actually a value of the new type (otherwise). In our example, TwoInts is a function of type int*int > mytype, Str is a function of type string>mytype, and Pizza is a value of type mytype. Second, we use constructors in caseexpressions as described further below.
1  datatype mytype = TwoInts of int * int 
How ML Provides Access to Datatype Values: Case Expressions
1  fun f x = (* f has type mytype > int*) 
In one sense, a caseexpression is like a more powerful ifthenelse expression: Like a conditional expression, it evaluates two of its subexpressions: first the expression between the case and of keywords and second the expression in the first branch that matches. But instead of having two branches (one for true and one for false), we can have one branch for each variant of our datatype (and we will generalize this further below). Like conditional expressions, each branch’s expression must have the same type (int in the example above) because the typechecker cannot know what branch will be used.
Each branch has the form p => e
where p is a pattern and e is an expression, and we separate the branches with the  character. Patterns look like expressions, but do not think of them as expressions. Instead they are used to match against the result of evaluating the case’s first expression (the part after case). This is why evaluating a caseexpression is called patternmatching.
Datatype Bindings and Case Expressions So Far, Precisely
We can summarize what we know about datatypes and pattern matching so far as follows: The binding
datatype t = C1 of t1  C2 of t2  …  Cn of tn
introduces a new type t and each constructor Ci is a function of type ti>t. One omits the “of ti” for a variant that “carries nothing” and such a constructor just has type t. To “get at the pieces” of a t we use a case expression:
case e of p1 => e1  p2 => e2  …  pn => en
A case expression evaluates e to a value v, finds the first pattern pi that matches v, and evaluates ei to produce the result for the whole case expression. So far, patterns have looked like Ci(x1,…,xn) where Ci is a constructor of type t1 … tn > t (or just Ci if Ci carries nothing). Such a pattern matches a value of the form Ci(v1,…,vn) and binds each xi to vi for evaluating the corresponding ei.
Type Synonyms
A type synonym simply creates another name for an existing type that is entirely interchangeable with the existing type.
For example, if we write:
1  type foo = int 
then we can write foo wherever we write int and viceversa.
for more complicated types, it can be convenient to create type synonyms. Here are some examples for types we created above:
1  type card = suit * rank 
Lists and Options are Datatypes
Because datatype definitions can be recursive, we can use them to create our own types for lists. For example, this binding works well for a linked list of integers:
1  datatype my_int_list = Empty 
We can use the constructors Empty and Cons to make values of my_int_list and we can use case expressions to use such values:
1  val one_two_three = Cons(1,Cons(2,Cons(3,Empty))) 
For options, all you need to know is SOME and NONE are constructors, which we use to create values (just like before) and in patterns to access the values. Here is a short example of the latter:
1  fun inc_or_zero intoption = case intoption of 
The story for lists is similar with a few convenient syntactic peculiarities: [] really is a constructor that carries nothing and :: really is a constructor that carries two things, but :: is unusual because it is an infix operator (it is placed between its two operands), both when creating things and in patterns:
1  fun sum_list xs = 
Notice here x and xs’ are nothing but local variables introduced via patternmatching. We can use any names for the variables we want.
PatternMatching for EachOf Types: The Truth About ValBindings
1  fun full_name (r : {first:string,middle:string,last:string}) = case r of 
However, a caseexpression with one branch is poor style — it looks strange because the purpose of such expressions is to distinguish cases, plural. So how should we use patternmatching for eachof types, when we know that a single pattern will definitely match so we are using patternmatching just for the convenient extraction of values? It turns out you can use patterns in valbindings too! So this approach is better style:
1 

1  fun sum_triple (x,y,z) = x+y+z 
This version of sum_triple should intrigue you: It takes a triple as an argument and uses patternmatching to bind three variables to the three pieces for use in the function body. But it looks exactly like a function that takes three arguments of type int. Indeed, is the type intintint>int for threeargument functions or for one argument functions that take triples?
It turns out we have been basically lying: There is no such thing as a multiargument function in ML: Every function in ML takes exactly one argument! Every time we write a multiargument function, we are really writing a oneargument function that takes a tuple as an argument and uses patternmatching to extract the pieces. This is such a common idiom that it is easy to forget about and it is totally fine to talk about “multiargument functions” when discussing your ML code with friends. But in terms of the actual language definition, it really is a oneargument function: syntactic sugar for expanding out to the first version of sum_triple with a onearm case expression.
Digression: Type inference
In ML, every variable and function has a type (or your program fails to typecheck) — type inference only means you do not need to write down the type.
1  fun sum_triple triple = case triple of 
In fact, type inference sometimes reveals that functions are more general than you might have thought. Consider this code, which does use part of a tuple/record:
1  fun partial_sum (x,y,z) = x + z 
In both cases, the inferred function types reveal that the type of y can be any type, so we can call partial_sum (3,4,5) or partial_sum (3,false,5). This is okay because the polymorphism indicates that partial_sum has a more gen eral type. If you can take a type containing ’a, ’b, ’c, etc. and replace each of these type variables consistently to get the type you “want,” then you have a more general type than the one you want.
Nested Patterns
It turns out the definition of patterns is recursive: anywhere we have been putting a variable in our patterns, we can instead put another pattern. Roughly speaking, the semantics of patternmatching is that the value being matched must have the same “shape” as the pattern and variables are bound to the “right pieces.” (This is very handwavy explanation which is why a precise definition is described below.) For example, the pattern a::(b::(c::d)) would match any list with at least 3 elements and it would bind a to the first element, b to the second, c to the third, and d to the list holding all the other elements (if any). The pattern a::(b::(c::[])) on the other hand, would match only lists with exactly three elements. Another nested patterns is (a,b,c)::d, which matches any nonempty list of triples, binding a to the first component of the head, b to the second component of the head, c to the third component of the head, and d to the tail of the list.
In general, patternmatching is about taking a value and a pattern and (1) deciding if the pattern matches the value and (2) if so, binding variables to the right parts of the value. Here are some key parts to the elegant recursive definition of pattern matching:
1  exception BadTriple 
Exceptions
ML has a builtin notion of exception. You can raise (also known as throw) an exception with the raise primitive. For example, the hd function in the standard library raises the List.Empty exception when called with []:
1  fun hd xs = 
You can create your own kinds of exceptions with an exception binding. Exceptions can optionally carry values with them, which let the code raising the exception provide more information:
1  exception MyUndesirableCondition 
Kinds of exceptions are a lot like constructors of a datatype binding. Indeed, they are functions (if they carry values) or values (if they don’t) that create values of type exn rather than the type of a datatype. So Empty, MyUndesirableCondition, and MyOtherException(3,9) are all values of type exn, whereas MyOtherException has type int*int>exn.
Tail Recursion and Accumulators
This topic involves new programming idioms, but no new language constructs. It defines tail recursion, describes how it relates to writing efficient recursive functions in functional languages like ML, and presents how to use accumulators as a technique to make some functions tail recursive.
1 

Why might sum2 be preferred when it is clearly more complicated? To answer, we need to understand a little bit about how function calls are implemented. Conceptually, there is a call stack, which is a stack (the data structure with push and pop operations) with one element for each function call that has been started but has not yet completed. Each element stores things like the value of local variables and what part of the function has not been evaluated yet. When the evaluation of one function body calls another function, a new element is pushed on the call stack and it is popped off when the called function completes.
there is nothing more for the caller to do after the callee returns except return the callee’s result.
This situation is called a tail call (let’s not try to figure out why it’s called this) and functional languages like ML typically promise an essential optimization: When a call is a tail call, the caller’s stackframe is popped before the call — the callee’s stackframe just replaces the caller’s. This makes sense: the caller was just going to return the callee’s result anyway. Therefore, calls to sum2 never use more than 1 stack frame.