Compound Data Types

Product Types

The each-of type is more formally the product type. A product type describes the values containing each of the values of type ${t_1, t_2, \ldots, \textit{ and } \space t_n.}$ Tuples are the most obvious example of product type data. A tuple such as (1, true) is a value of type int*bool. The tuple describes the values containing an int and a bool.

val student = {name="Jo Ann", age=19, enrolled=true}

val student = {age=19,enrolled=true,name="Jo Ann"} :
{age:int, enrolled:bool, name:string}

val student = {name="Jo Ann", age=19, enrolled=true}
val JoAnnName = #name student

val student = {age=19,enrolled=true,name="Jo Ann"} :
{age:int, enrolled:bool, name:string}
val JoAnnName = "Jo Ann" : string

val foo = (1, 2, 3)
val bar = {1=1, 2=2, 3=3}

Sum Types

A sum type describes the values containing a value of one of the types ${t_1, t_2, \ldots, \textit{ or } \space t_n.}$ An example of sum type data is int option. Here, the data type either contains an int or it does not. Functional languages like ML tend to handle sum types succinctly, at least as compared to object-oriented languages like Java, where sub-classing is almost always required.

datatype fooType = TwoInts of int * int
        | Str of string
        | xyz
val a = Str "Hi"
val b = Str
val c = xyz
val d = TwoInts(1 + 1, 2 + 2)
val e = a

datatype fooType = Str of string | TwoInts of int * int | xyz
val a = Str "Hi" : fooType
val b = fn : string -> fooType
val c = xyz : fooType
val d = TwoInts (2,4) : fooType
val e = Str "Hi" : fooType

val a = Str "Hello" (* evaluates to Str("Hello") *)
val b = TwoInts(1, 3-2)
val c = Str (* evaluates to fn : string -> fooType *)

datatype suit = Club | Diamond | Heart | Spade

datatype rank = Jack | Queen | King | Ace | Num of int

datatype id = BookNum of int
     | Title of string*(string option)*string

{
 studentID : int,
 firstName : string,
 middleName : string option, (* not all students have middle names *)
 lastName : string
}

datatype student = studentID of int
        | firstName of string
        | middleName of string option
        | lastName of string

{
 studentID : int option
 firstName : string,
 middleName : string option
 lastName : string
}

Case Expressions

Now that we know about variant-accessing functions, we might notice that some data types do not have the variant-accessing functions we saw for things like lists and optionals. For example, the string type doesn't have variant-accessing functions like isString or getString. What happened there?

Recall what we want with datatype bindings: (1) We need a way to determine what variant the value is, and (2) a way to extract the data, if any, associated with that variant. Languages like ML combine these two needs as a single construct through case expressions and pattern matching.

datatype fooType = TwoInts of int * int
       | Str of string
       | xyz
fun f (x : fooType) =
 case x of
  xyz => 3
  | Str s => 8
  | TwoInts(i1, i2) => i1 + i2

In the code above, we have the same datatype we saw before—fooType. In ML, pattern matching is done in the order written.

The more interesting part is that we now have a function that takes a value of type fooType (note that the parameter list is optional, but we include it for clarity). This function takes a myType and returns an int. The keywords case ... of denote a case expression, and they are what we use to access the values of the given datatype. Each of the lines following case ... of are cases, separated by a pipe (|). The case expression works as such: (1) If x is an xyz, evaluate to 3. (2) If x is a Str, evaluate to 8. (3) If x is a TwoInts, evaluate to i1 + i2.

${p \nc \textit{exp}}$

Where ${p}$ is a pattern, and ${\textit{exp}}$ is an expression. A more general syntax:

fun f x =
case x of
 p0 => exp0
 | p1 => exp1
 | p2 => exp2
 | ...
 | pn => expn

Patterns are the construct used to match against the result of evaluating the case's first expression (in the syntax above, p0 => exp0.) This form of evaluation has a specific name—pattern matching.

Importantly, case expressions are first-match, meaning that the moment there is a pattern match, the entire expression evaluates to that pattern match's expression. ML will not continue to check the remaining branches.

Having introduced case expressions, we will stray from using hd, tl, and null. These are all constructors, but it is far better to use the constructors [] and ::. The constructor [] represents the empty list, and :: represents the non-empty list. We will use these constructors alongside case expressions.

enum TrafficLight {
 GREEN,
 YELLOW,
 RED
}

public class MainProgram{
 public static void main(String []args){
  TrafficLight streetA = TrafficLight.GREEN;
  String result = motion(streetA);
  System.out.println(result);
 }

 public static String motion(TrafficLight light) {
  if (light == TrafficLight.GREEN) {
    return "Go";
  }
  else if (light == TrafficLight.YELLOW) {
    return "Slow Down";
  }
  else {
    return "Stop";
  }
 }
}

Go

datatype TrafficLight = Green
       | Yellow
       | Red
fun motion x =
 case x of
  Green => "Go"
  | Yellow => "Slow down"
  | Red => "Stop"
val x = Green
val y = motion(x)

datatype TrafficLight = Green | Red | Yellow
val motion = fn : TrafficLight -> string
val x = Green : TrafficLight
val y = "Go" : string

Recursive Types

A recursive compound data type is a type that can refer to itself in its definition to describe a recusive structure. We've seen one such recursive type, lists. An int list describes values that contain either nothing, or contains an int and another int list. We can see this to be the case when we build a list recursively:

1 :: [ 2 :: [3 :: [4 :: [5 :: [6 :: []]]]]]
 ⇩
[1, 2, 3, 4, 5, 6]

In fact, we can implement our own definition of a list:

datatype list = Empty
       | Cons of int * list
val x = Cons(1, Cons(2, Cons (3, Empty)))

datatype list = Cons of int * list | Empty
val x = Cons (1,Cons (2,Cons (3,Empty))) : list

Those familiar with a languages of the Lisp family may recognize the example above. With our implementation, we can write various functions:

datatype list = Empty
     | Cons of int * list
val x = Cons(1, Cons(2, Cons (3, Empty)))

fun append (xs, ys) =
 case xs of
  Empty => ys
  | Cons(x, xs') => Cons(x, append(xs', ys))

datatype exp = Constant of int
       | Negate of exp
       | Add of exp * exp
       | Multiply of exp * exp
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)

val x = Add(Constant (10 + 9), Negate (Constant 4))
val y = eval(x)

datatype exp
 = Add of exp * exp | Constant of int | Multiply of exp * exp | Negate of exp
val eval = fn : exp -> int
val x = Add (Constant 19,Negate (Constant 4)) : exp
val y = 15 : int

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

val x = Add(Constant (10 + 9), Negate (Constant 4))

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)

Add(Constant (10 + 9), Negate (Constant 4))
 (Constant (10 + 9)) + (Negate(Constant 4))
 19 + (Negate(Constant 4))
 19 + (-(Constant 4))
 19 + (-4)
 15

Type Synonyms

Another extremely useful binding is the type synonym. Many languages, for example Swift, provide this feature in other terms like type alias. A type synonym creates another name for existing type. We can then use that name interchangeable with the existing type.

For example, if we write:

type age = int

We now have a type called age, which we can use wherever we must write int. Needless to say, type synonyms are extremely lead to much more readable and meaningful programs.

Note that type synonyms are a kind of name binding, rather than a datatype binding. In a datatype binding, we are introducing a new type—it is not the same as any existing type. The datatype binding will create constructors that produce a value of the new type. A type synonym, however, is a name binding—it is simply a name that points to an existing data type.

Type synonyms are particularly useful when used with composite data types (i.e., the types we've created ourselves). For example:

datatype suit = Club | Diamond | Heart | Spade
datatype rank = Jack | Queen | King | Ace | Number of int
type card = suit * rank

In the code above, we've created two sum types, suit and rank. Then, we represent a card as a tuple, (suit, rank). Instead of repeatedly writing suit * rank, we simply call it card.

The same idea extends to product types. Instead of repeatedly writing a record, we can encapsulate it in a type synonym:

type studentIdentification = { studentID : int option,
                firstName : string,
                middleName : string option,
                lastName : string }

Polymorphic Datatypes

Recall that we noted how the list and option types are really datatype bindings. We want to refine this notion just a bit further. Lists and options are a special type of datatype binding—they are datatype bindings that take option parameters. Thus, list itself is not a type. The data types are actually int list or string list. The same goes for optionals. option is not a type; it's int option, or string option.

So what do the identifiers list and option represent? They are type constructors—functions that take type parameters to produce types. More specifically, list and option are polymorphic type constructors.

The type constructors list and option are examples of a big decision language designers have to make. Do we want a single polymorphic data type (a data type that changes depending on what's passed into it) list, or do we want a single constructor called list that produces different types depending on its parameters? ML's designers went with the second option, and included the ability for users to define their own polymorphic datatypes.

For example, we can create a polymorphic binary tree type:

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

In the data type above, the type is not tree. Instead, the types are int * string tree or int * int tree. It all depends on what's passed as arguments for alpha a and alpha b (the parameters 'a and 'b).

Pattern Matching & Functions

It turns out that in ML, we've been using pattern matching all along. To see how, we explore pattern matching further.

In the previous sections, we used pattern matching with respect to sum types. We did so because that's really the only way we access the values stored in a sum type. But what about product types? We can actually use pattern matching for records and tuples. Let's consider the tuple. Suppose we had a function that takes a triple, and returns the sum of its individual parts:

fun sum_triple triple =
 case triple of
  (x, y, z) => x + y + z

val x = (1, 2, 3)
val y = sum_triple(x)

val sum_triple = fn : int * int * int -> int
val x = (1,2,3) : int * int * int
val y = 6 : int

Above, we used a case expression. In this case, the function takes the tuple, and performs a computation, addition, where each of x, y, and z match.

The example above, however, is poor style. We've written what's called a

one-armed case expression—a case expression that only has one case. A much better way:

fun sum_triple triple =
 let val (x, y, z) = triple
 in
  x + y + z
 end
val x = (1, 2, 3)
val y = sum_triple(x)

val sum_triple = fn : int * int * int -> int
val x = (1,2,3) : int * int * int
val y = 6 : int

Notice how we bound (x, y, z) to triple, the argument passed. This is just a pattern match. Another example:

fun full_name person =
 let val { firstName = x, lastName = z } = person
 in
  x ^ " " ^ z
 end
val jane = { firstName = "Jane", lastName = "Eyre" }
val janeEyre = full_name(jane)

val full_name = fn : {firstName:string, lastName:string} -> string
val jane = {firstName="Jane",lastName="Eyre"} :
 {firstName:string, lastName:string}
val janeEyre = "Jane Eyre" : string

We can write the code above even more concisely:

fun sum_triple (x, y, z) =
 x + y + z
fun full_name { firstName = x, lastName = z } =
 x ^ " " ^ z

val x = (1, 2, 3)
val y = sum_triple(x)
val jane = { firstName = "Jane", lastName = "Eyre" }
val janeEyre = full_name(jane)

val sum_triple = fn : int * int * int -> int
val full_name = fn : {firstName:string, lastName:string} -> string
val x = (1,2,3) : int * int * int
val y = 6 : int
val jane = {firstName="Jane",lastName="Eyre"} :
 {firstName:string, lastName:string}
val janeEyre = "Jane Eyre" : string

Take a close look at how we wrote the functions. The variable we pass into the function—the argument—is actually a pattern match! This in turn means that we do not have to use the # symbol to extract data from a tuple. We can simply pattern match. This also means that we do not always have to specify types for arguments.

Having seen enough ML, we might notice something jump out at us. That function sum_triple looks an awful lot like a function that takes three arguments. We've seen functions that take just one argument:

fun double(x) =
 x * 2
val x = 3
val y = double(3)

val double = fn : int -> int
val x = 3 : int
val y = 6 : int

How does ML know when we're doing a pattern match and when we're passing arguments to a function? With a simple rule: Every function in ML only takes one argument, and uses pattern matching to take the parts out. In the case of our regular function definitions, the argument passed is a tuple. The tuple is the one argument.

This feature in ML leads to the peculiar observation that ML is a language where there is no such thing as a multi-argument function. In other words, functions in ML can only take one parameter. Of course, this borders on pedantry and isn't a great marketing opener.

Whether the tuple has one, two, three, or a hundred parts, ML uses pattern matching to extract them. But what about functions that take no arguments?

fun greet() = print "Hello!\n"

The rule still applies. Every function takes only one argument. Here, there are no arguments, so a pattern match is done. In this case, the pattern to match is (), and it matches to a value of type unit.

Using pattern matching for functions allows us to write functions that would otherwise be extremely unwieldy to write in languages like Java.

fun turn_left (x, y, z) = (y, z, x)
fun turn_right coordinate =
 turn_left(turn_left coordinate)
fun complete_rotation coordinate =
 turn_right(turn_right(turn_right coordinate))

val original = (1, 2, 3)
val turnLeft = turn_left(original)
val turnRight = turn_right(original)
val turnRight_turnRight_turnRight = complete_rotation(original)

val turn_left = fn : 'a * 'b * 'c -> 'b * 'c * 'a
val turn_right = fn : 'a * 'b * 'c -> 'c * 'a * 'b
val complete_rotation = fn : 'a * 'b * 'c -> 'a * 'b * 'c
val original = (1,2,3) : int * int * int
val turnLeft = (2,3,1) : int * int * int
val turnRight = (3,1,2) : int * int * int
val turnRight_turnRight_turnRight = (1,2,3) : int * int * int

Using pattern matching allows us to write functions whose arguments immediately pass into another function without the need to explicitly write out parameters. This is something not very many languages can do. In ML, the three functions above are written succinctly because of pattern matching. In other languages like Java, it's fairly awkward to implement. Not only does pattern matching allow ML to handle functions like those above easily, it reduces the size of a language's implementation. Here, ML's size is reduced by the fact that there is no separate implementation for multi-argument functions.

import Foundation

let arrTuple = [(0, 1), (2, 3), (4, 5)]
for i in 0..<arrTuple.count {
  print(arrTuple[i].1)
}

1
3
5

import Foundation

let arr = [(0, 1), (2, 3), (4, 5)]
for (_, i) in arr {
  print(i)
}

1
3
5

Type Inference & Pattern Matching

Having discussed pattern matching, we should address its relationship to type inference. The topic of type inference will be discussed in later sections. Recall that we can use # to access the values in a record or tuple. With pattern matching, we no longer need to use #, nor do we need to explicitly state the types for our function arguments. Why are we allowed to do this? Because ML uses pattern-matching to infer types. However, for type inference to work, we have to give ML enough information to work with.

Notice ML's type inference for these functions:

fun sum_triple (x, y, z) =
 x + y + z
fun full_name {firstName = x, lastName = y} =
 x ^ " " ^ y

val sum_triple = fn : int * int * int -> int
val full_name = fn : {firstName:string, lastName:string} -> string

ML can infer the types for these functions because of the computations we intend to perform in the functions' bodies. For sum_triple, we are asking for addition, so ML infers int. In full_name, we are asking for concatenation, so ML infers string. The patterns told ML most of what is needed for type inference; the rest of the necessary information is provided by the operations. If we used the # syntax, type inference will still work:

fun sum_triple (triple : int*int*int) =
 #1 triple + #2 triple + #3 triple
fun full_name (n: {firstName:string, lastName:string}) =
 #firstName n ^ " " ^ #lastName n

val sum_triple = fn : int * int * int -> int
val full_name = fn : {firstName:string, lastName:string} -> string

Now, notice what happens when remove our explicit type indicator for the first function:

fun sum_triple (triple) =
 #1 triple + #2 triple + #3 triple
fun full_name (n: {firstName:string, lastName:string}) =
 #firstName n ^ " " ^ #lastName n

records.sml:1.3-2.36 Error: unresolved flex record (need to know the names of ALL the fields
in this context)
 type: {1:'Y[OL(+,+)], 2:'Y[OL(+,+)], 3:'Y[OL(+,+)]; 'Z}

ML cannot infer the type and returns a compilation error. This is because ML knows that there must be a tuple, but it has no idea whether the tuple has four, five, or even a hundred parts. Thus, we have to provide the indicator explicitly.

fun partial_sum (x, y, z) =
 x + z

fun full_name {firstName = x, middleName = y, lastName = z} =
 x ^ " " ^ z

val partial_sum = fn : int * 'a * int -> int
val full_name = fn :
 {firstName:string, lastName:string, middleName:'a} -> string

Polymorphic & Equality Types

We can gain some insight into how ML infers types for polymorphic functions by looking at a simple example:

fun append(xs, ys) =
 case xs of
  [] => ys
  | x::<span data-text="Note that this is just a variable binding. We could have used anything here." class="tooltip">xs'</span> => x :: append(xs', ys)
val list1 = append(["a", "b"], ["c", "d"])
val list2 = append([1, 2], [3, 4])

val append = fn : 'a list * 'a list -> 'a list
val list1 = ["a","b","c","d"] : string list
val list2 = [1,2,3,4] : int list

Notice that ML can infer the list's type even if we didn't explicitly state it. Our function append() is polymorphic. It has a type of 'a list * 'a list -> 'a list, which is more general than some like string list * string list -> string list. The xs and ys can be of any type. What we cannot do is use append() with lists of different types:

fun append(xs, ys) =
 case xs of
  [] => ys
  | x::xs' => x :: append(xs', ys)
val list3 = append([1, 2], ["a", "b"])

records.sml:7.5-7.39 Error: operator and operand do not agree [overload - bad instantiation]
operator domain: 'Z[INT] list * 'Z[INT] list
operand:         'Z[INT] list * string list
in expression:
 append (1 :: 2 :: nil,"a" :: "b" :: nil)

We cannot do so because all the 'a must be replaced with a single type. However, we can append two lists of different types, as long as we use a second type parameter, 'b.

In some situations, we might notice a ''a—two quotations instead of one. For example, a function type that looks like:

''a list * ''a -> int

The two prime ticks indicate an equality type. An equality type is a type whose value can be used with the = operator. This means that a function with the type above is polymorphic, but we the set of possible types that ''a can take is limited—only those that can be used with the = operator. The set includes types like string, int, as well as tuples and lists (as long as they are composed of equality type values), but does not include types like real (floating point values) and function types.

Nested Patterns

Return to pattern matching, we can nest case expressions as much as we'd like. However, a better approach is nesting the patterns rather than the case expressions themselves; nested patterns are usually much easier to read than nested case expressions.

Pattern matching is recursive. The process: ML takes a pattern (which itself can contain patterns) and a value (which can contain other values) and asks, does this value have the same "shape" described by the pattern? If the answer is yes, then ML binds the relevant variables to the corresponding parts. This is very abstract, so several examples are needed.

Suppose we have the following tuple of lists:

([1, 2, 3], [4, 5, 6], [7, 8, 9])

We want to write a function that returns the following:

[(1, 4, 7), (2, 5, 6), (3, 6, 9)]

Notice the pattern? The function takes a tuple of three lists, then returns a list of three tuples, where each the first tuple consists of all the first elements of the three lists, the second tuple consists of all the second elements of the three lists, and the third tuple consists of all the third elements of the three lists.

Without pattern matching, the function would look like:

exception ListLengthMisMatch

fun zip1(l1, l2, l3) =
 if null l1 andalso null l2 andalso null l3
 then []
 else if null l1 orelse null l2 orelse null l3
 then raise ListLengthMismatch
 else (h2 l1, hd l2, hd l3) :: zip(tl l1, tl l2, tl l3)

The function above is pretty messy to look at. Worse, we are taking the risk of missing a case, and we aren't relying on any help from the type checker. What if we used pattern matching?

fun zip2 (l1, l2, l3) =
 case l1 of
  [] =>
  (case l2 of
   [] => (case l3 of
     [] => []
     | _ => raise ListLengthMismatch)
    | _ => raise ListLengthMismatch)
   | hd1 :: tl1 =>
    (case l2 of
     [] => raise ListLengthMismatch
     | hd2::tl2 => (case l3 of
       [] => raise ListLengthMismatch
       | hd3::tl3 =>
        (hd1, hd2, hd3)::zip3(tl1, tl2, tl3)))

This looks even worse than the previous implementation. Rather than using andalso and orelse, we're manually checking for all the possible patterns. Luckily there's a better way. Instead of checking for every pattern, we want to use the fact that patterns can exist inside patterns.

Here is another implementation:

fun zip list_triple =
 case list_triple of
  ([], [], []) => []
  | (hd1::tl1, hd2::tl2, hd3::tl3) => (hd1, hd2, hd3)::zip3(tl1, tl2, tl3)
  | _ => raise ListLengthMismatch

In the example above, we're only considering three patterns. First:

([], [], [])

The pattern above is a tuple with three lists. When ML sees this pattern, it will match any value it finds that has the pattern of three empty lists within a tuple. If ML finds a match, it returns the empty list [].

Then there's a second pattern:

(hd1::tl1, hd2::tl2, hd3::tl3)

This pattern consists of a few parts: First, it is a tuple. Second, it is a 3-tuple with three non-empty lists. I.e., it has a head and a tail. This means that list_triple will only match if it is a tuple with three non-empty lists. If matches, then we bind each head of the three lists in the tuple to hd1, hd2, and hd3. The same goes for tl1, tl2, and tl3. Then, cons the result of (hd1, hd2, hd3) to zip3(tl1, tl2, tl3). Notice how this is recursive.

Exceptions

Having discussed patterns, we can now more thoroughly investigate exceptions: idioms for indicating a particular condition as a runtime error. Exceptions are not unique to ML; they are found in numerous languages, both old and new. They are even found in reality—they are quite literally exceptions to a general rule or condition. For example, a professor might have a general rule of not accepting late assignments. However, there may be exceptions to that general rule: A personal emergency, being ill, or obtaining special permission for a late submission. Examining this from a programming perspective, we might model the professor's grading scheme as including a function called is_generally_compliant(), which checks whether a given submission is late. If the submission is late, it returns false. But, if some condition is true (i.e., excused earlier), we throw, or raise an exception. When that exception is raised, we need some way to handle, or catch, that exception: Return some message, execute that function, or store this data, etc.

The syntax for defining exceptions in ML:

exception 𝑒

where 𝑒 is some identifier. The expression ${e}$ is actually a constructor, with the identifier ${e.}$ Because constructors are functions, exceptions in ML are first class, so they are themselves values. And because they are values, they have type, namely exn. Thus, if we wrote:

exception Error

we introduce into the environment the value Error : exn. The keyword exn is a clipping of "exception name." To repeat, in the example above, the value Error is not itself the exception; it's the constructor for an exception. Thus, to derive any use of exceptions, they must be raised. In other languages, raising an exception is called throwing an exception. Here is an example:

(* This function computes the factorial of a number. *)
 fun factorial n =
  let exception Negative
  in
   if n = 0
    then 1
   else
    if n < 0 then raise Negative
    else n * factorial(n - 1)
  end

 val x = factorial 4
 val y = factorial ~2

uncaught exception Negative
  raised at: exceptions.sml:8.24-8.32

In the example above, we created a new value, Negative : exn, and we raise it whenever a negative number is passed as a value to the function factorial(). Fixing the error:

(* This function computes the factorial of a number. *)
fun factorial n =
 let exception Negative
 in
  if n = 0
   then 1
  else
   if n < 0 then raise Negative
   else n * factorial(n - 1)
 end

val x = factorial 4
val y = factorial 2

val factorial = fn : int -> int
val x = 24 : int
val y = 2 : int

In many situations, we want to handle the exception. In other languages, this is also called catching the exception. For example, perhaps we might want, for whatever reason, to immediately return 0 whenever we pass a negative number to the factorial() function. To do so, we can use a handle expression:

(* This function computes the factorial of a number. *)
fun factorial n =
 let
  exception Negative
 in
  if n = 0
   then 1
  else
   if n < 0 then raise Negative
   else n * factorial(n - 1)
 end

val a = 5
val b = ~5
val x = factorial a
val y = factorial b handle Negative => 0

val factorial = fn : int -> int
val a = 5 : int
val b = ~5 : int
val x = 120 : int
val y = 0 : int

In the last line of the source code above, when the factorial() function raises the exception Negative, the value of y is immediately bound to 0.

Tail Recursion

Most of the functions we've seen are recursive. This raises a fair question: How efficient is recursion? To answer this question, we investigate the idea of tail recursion. To understand tail recursion, let's talk about the call stack.

The call stack is an abstract idea; think of it as this stack of papers, each with a single task. Those tasks are functions, and each piece of paper is called a stack frame. The piece of paper, or call stack, contains the value of local variables, and all the operations the function must perform. Whenever we call a function ${f,}$ we push a stack frame of ${f,}$ a new piece of paper, onto the stack. Once that call to ${f}$ finishes (i.e., the task is complete), ${f}$ is removed from the stack (in programming parlance, the stack frame is popped off the stack).

Now, with recursion, we are calling functions that call themselves. Thus, there is a situation where we have multiple stack-frames resulting from calls to the same function. For example, with the factorial() function we wrote previously, calling factorial(3) results in four separate stack frames: factorial(3), factorial(2), factorial(1), and factorial(0).

Here is a more efficient version of factorial() (for simplicity, we've removed the exception from the earlier section):

(* This function computes the factorial of a number. *)
fun factorial n =
let fun factorial_helper(n, accumulator) =
 if n = 0
  then accumulator
  else factorial_helper(n - 1, accumulator * n)
in
 factorial_helper(n, 1)
end

val a = factorial(3)

val factorial = fn : int -> int
val a = 6 : int

This looks more complicated, so let's walk through it. Inside factorial(), we have a locally-defined helper function, factorial_helper(). That function takes two arguments: n, the argument passed to factorial(), and accumulator. factorial_helper() works as such: If n=0, then return the accumulator; otherwise, return factorial_helper(n-1, accumulator * n).

Thus, when we call factorial(3), we end up creating the following stacks: factorial_helper(3, 1), factorial_helper(2, 3), factorial_helper(1, 6), and factorial(0, 6). This may not seem like an improvement; we have a bigger stack than the previous implementation!

This is where tail recursion comes into play. In languages that implement tail recursion—such as ML—calls like factorial_helper() are identified by the language as tail calls. And when a call is identified as a tail call, the language follows a specific rule: Do not keep a function's stack frame if all the function performs is getting back a callee's result and return it without any further evaluation. Following this rule, languages like ML perform the following whenever it encounters a tail call like factorial_helper():

1. Remove the caller before the call.
2. Let the callee use the resulting empty stack.

Thus, when we call factorial(3), a tail call, we create a stack frame for factorial(3). However, because it's a tail call, the stack frame is "cleared" of factorial(3)'s machine code, and replaced with factorial_helper(3, 1). This in turn calls factorial_helper(n-1, accumulator * n), and as such, factorial_helper(3, 1) is itself a tail call. Thus, factorial_helper(3, 1) has its stack frame cleared, and replaced with factorial_helper(2, 3). This goes on until we reach factorial_helper(0, 6). The end result: We only used 1 stack frame.

To refactor recursive functions as tail-recursive, we can use the following approach:

1. Create a helper function with an accumulator parameter.
2. Think of the accumulator as a variable that "holds" the answer so far.
3. Think of the old base case as the initial accumulator.
4. Think of the new base case as the final accumulator.

For example, consider a function that sums all the elements in a list:

(* linear recursion *)
fun summate1 xs =
case xs of
 [] => 0
 | x::xs' => x + summate1 xs'

(* tail recursion *)
fun summate xs =
let
 fun helper(xs, accumulator) =
  case xs of
   [] => accumulator
   | x::xs' => helper(xs', x + accumulator)
in
 helper(xs, 0)
end