# Reading 16: Recursive Data Types

#### Software in 6.031

#### Objectives

- Understand recursive datatypes
- Read and write datatype definitions
- Understand and implement functions over recursive datatypes
- Understand immutable lists and know the standard operations on immutable lists
- Know and follow a recipe for writing programs with ADTs

## Introduction

In this reading we’ll look at recursively-defined types, how to specify operations on such types, and how to implement them.
Our main example will be *immutable lists*.

## Recursive functions

Before we introduce recursive datatypes — which have a recursive structure of both data and computation — take a minute to review recursive computations.

Just as a recursive function is defined in terms of itself, a *recursive datatype* is defined in terms of itself.
We’ll see the same need for *base* and *recursive* cases, which will now appear as different *variants* of the abstract type.

## Immutable lists

We’ll start with a classic recursive datatype, the *immutable list*.

Immutability is powerful not just because of its safety, but also because of the potential for sharing. Sharing actually produces performance benefits: less memory consumed, less time spent copying. Here we’re going to look at how to represent list data structures differently than in our familiar array lists or linked lists.

Let’s define a data type for an immutable list, `ImList<E>`

.
The data type has four fundamental operations:

These four operations have a long and distinguished pedigree.
They are fundamental to the list-processing languages Lisp and Scheme (where for historical reasons they are called `nil`

, `cons`

, `car`

, and `cdr`

, respectively).
They are widely used in functional programming, where `first`

and `rest`

are sometimes called *head* and *tail* instead.

Before we design Java classes to implement this datatype, let’s get used to the operations a bit, using lists of integers.
We’ll write lists with square brackets, like `[ 1, 2, 3 ]`

, and we’ll write the operations as if they are simple functions.
Once we get to Java, the syntax will look different but the operations will have the same meaning.

```
empty() → [ ]
cons(0, empty()) → [ 0 ]
cons(0, cons(1, cons(2, empty()))) → [ 0, 1, 2 ]
x = cons(0, cons(1, cons(2, empty()))) → [ 0, 1, 2 ]
first(x) → 0
rest(x) → [ 1, 2 ]
first(rest(x)) → 1
rest(rest(x)) → [ 2 ]
first(rest(rest(x)) → 2
rest(rest(rest(x))) → [ ]
```

The fundamental relationship between `first`

, `rest`

, and `cons`

is:

```
first(cons(elt, list)) = elt
rest(cons(elt, list)) = list
```

What `cons`

puts together, `first`

and `rest`

peel back apart.

### Immutable lists in Java

To implement this datatype in Java, we’ll use an interface:

```
public interface ImList<E> {
// todo: empty() returning ImList<E>
public ImList<E> cons(E elt);
public E first();
public ImList<E> rest();
}
```

This interface declares a *generic type* `ImList<E>`

that can be instantiated for any type `E`

: `ImList<Integer>`

, `ImList<String>`

, etc.
The `E`

in these declarations is a placeholder that the compiler will fill in when it checks our code for type safety.

And we’ll write two classes that implement this interface:

`Empty`

represents the result of the`empty`

operation (an empty list)`Cons`

represents the result of a`cons`

operation (an element glued together with another list)

```
public class Empty<E> implements ImList<E> {
public Empty() {
}
public ImList<E> cons(E elt) {
return new Cons<>(elt, this);
}
public E first() {
throw new UnsupportedOperationException();
}
public ImList<E> rest() {
throw new UnsupportedOperationException();
}
}
```

```
public class Cons<E> implements ImList<E> {
private final E elt;
private final ImList<E> rest;
public Cons(E elt, ImList<E> rest) {
this.elt = elt;
this.rest = rest;
}
public ImList<E> cons(E elt) {
return new Cons<>(elt, this);
}
public E first() {
return elt;
}
public ImList<E> rest() {
return rest;
}
}
```

So we have methods for `cons`

, `first`

, and `rest`

, but where is the fourth operation of our datatype, `empty`

?

One way to implement `empty`

is to have clients call the `Empty`

class constructor to obtain empty lists.
This sacrifices representation independence — clients have to know about the `Empty`

class!

As we saw in an earlier reading, a better way to do it is as a static factory method that takes no arguments and produces an instance of `Empty`

.
We can put this static method in the `ImList`

interface along with the other operations.
This choice was *not possible* in previous versions of Java, which is why we still write code like:

`List<String> z = new ArrayList<>();`

Perhaps someday Java will offer a `List.empty()`

method to obtain a new empty all-purpose `List`

, but not yet.
(`List.of()`

and `Collections.emptyList()`

provide *immutable* empty lists.)

We will go ahead and update our `ImList`

interface with the static `empty`

method:

```
public interface ImList<E> {
public static <E> ImList<E> empty() {
return new Empty<>();
}
public ImList<E> cons(E elt);
public E first();
public ImList<E> rest();
}
```

The signature for `empty`

uses an unfamiliar bit of generic type syntax.
The `E`

in `ImList<E>`

is a placeholder for the type of elements in an instance of `ImList`

, but `empty`

is a static method: it cannot see instance variables or methods, and it also cannot see the instance type parameter.
You can read the declaration of `empty`

as: “for any `E`

, `empty()`

returns an `ImList<E>`

.”

Now that we have all the operations, here’s some actual Java code that parallels the abstract examples we wrote earlier. Hover or tap on each row in the table to update the snapshot diagram:

The key thing to note here is the *sharing of structure* that immutable list provides.
In the last example above, `x`

and `y`

are sharing their representation of the sublist `[ 1, 2 ]`

.
Only one copy of this sublist exists in memory, and both `x`

and `y`

point to it, but this aliasing is perfectly safe because the list is immutable.

### Two classes implementing one interface

Note that this design is different from what we have seen with `List`

, `ArrayList`

, and `LinkedList`

.
`List`

is an abstract data type and `ArrayList`

and `LinkedList`

are two *alternative* concrete representations for that datatype.

For `ImList`

, the two implementations `Empty`

and `Cons`

*cooperate* in order to implement the datatype — you need them both.

#### reading exercises

We wrote our `ImList`

implementations without documenting the abstraction function and representation invariant, which makes us terrible people.

```
public class Empty<E> implements ImList<E> {
public Empty() {
}
public ImList<E> cons(E elt) { return new Cons<E>(elt, this); }
public E first() { throw new UnsupportedOperationException(); }
public ImList<E> rest() { throw new UnsupportedOperationException(); }
}
```

Select the best abstraction function for `Empty`

:

(missing explanation)

And select lines to include in the rep invariant (let’s include even the ones that are normally implicit):

(missing explanation)

```
public class Cons<E> implements ImList<E> {
private final E elt;
private final ImList<E> rest;
public Cons(E elt, ImList<E> rest) {
this.elt = elt;
this.rest = rest;
}
public ImList<E> cons(E elt) { return new Cons<E> (elt, this); }
public E first() { return elt; }
public ImList<E> rest() { return rest; }
}
```

Select all the good abstraction functions for `Cons`

:

(missing explanation)

And select lines to include in the rep invariant (let’s include even the ones that are normally implicit):

(missing explanation)

## Recursive datatype definitions

The abstract data type `ImList`

, and its two concrete classes `Empty`

and `Cons`

, form a *recursive* data type.
`Cons`

is an implementation of `ImList`

, but it also uses `ImList`

inside its own rep (for the `rest`

field), so it recursively requires an implementation of `ImList`

in order to successfully implement its contract.

To make this fact clearly visible, we’ll write a **datatype definition**:

This is a recursive definition of `ImList`

as a set of values.
Here’s the high-level meaning: the set `ImList`

consists of values represented in two ways: either by an `Empty`

object (which has no fields), or by a `Cons`

object whose fields are an element `elt`

and an `ImList`

`rest`

.

A more detailed reading: `ImList<E>`

is a generic type where for any `E`

, the set `ImList<E>`

consists of the values represented either by an `Empty`

object, or by a `Cons`

object whose fields are a value called `elt`

of type `E`

and a value called `rest`

of type `ImList<E>`

.

The recursive nature of the datatype becomes far more visible when written in a datatype definition.

We can write any `ImList`

value as a term or expression using this definition, e.g. the list `[ 0, 1, 2 ]`

is written as

`Cons(0, Cons(1, Cons(2, Empty)))`

And we can build up the infinite set of all `ImList`

values by starting from the base case that is `Empty`

and recursively applying `Cons`

.
For example, with `ImList<Boolean>`

:

Formally, a datatype definition has:

- an
**abstract datatype**on the left, defined by its**representation**(or**concrete datatype**) on the right - the representation consists of
**variants**of the datatype combined by a union operator, which we’ll write as`+`

- each variant is a class name with zero or more fields, written with name and type separated by a colon (
`:`

).

A *recursive* datatype definition is a datatype definition where the abstract type (on the left) appears in its own definition (as the type of a field on the right).
Another example is a binary tree:

The `Tree`

type is defined as the set of values formed either by `Empty`

or by `Node`

, which takes an element `e`

(of type `E`

) and `left`

and `right`

subtrees.

We’ll see more examples below.

When you write a recursive datatype, document the recursive datatype definition as a comment in the interface:

```
public interface ImList<E> {
// Datatype definition:
// ImList<E> = Empty + Cons(elt:E, rest:ImList<E>)
// ...
```

#### reading exercises

In an earlier reading we mentioned Optional<E> as a useful tool for representing a value that might be missing, as a more typesafe alternative to using `null`

.

Write a datatype definition for `Optional<E>`

, following the pattern of `ImList<E>`

.

(missing explanation)

## Functions over recursive datatypes

This way of thinking about datatypes — as a recursive definition of an abstract datatype with concrete variants — is appealing not only because it can handle recursive and unbounded structures like lists and trees, but also because it provides a convenient way to describe operations over the datatype, as functions with one case per variant.

First, notice how the datatype definition maps to the abstract interface and concrete variants that we’ve already seen:

Now: let’s add a new operation by thinking about it as a recursive function with one case per variant: the size of the list, which is certainly an operation we’ll want in `ImList`

.
We can define it like this:

**size : ImList → int** // returns the size of the list

and then fully specify its meaning by defining *size* for each variant of `ImList`

:

```
size(Empty) = 0
size(Cons(elt:E, rest:ImList)) = 1 + size(rest)
```

This function is recursive.
We can think about the execution of *size* on a particular list as a series of reduction steps:

```
size(Cons(0, Cons(1, Empty)))
= 1 + size(Cons(1, Empty))
= 1 + (1 + size(Empty))
= 1 + (1 + 0)
= 1 + 1
= 2
```

And the cases from the definition can be translated directly into Java as methods in `ImList`

, `Empty`

, and `Cons`

:

```
public interface ImList<E> {
// ...
public int size();
}
public class Empty<E> implements ImList<E> {
// ...
public int size() { return 0; }
}
public class Cons<E> implements ImList<E> {
// ...
public int size() { return 1 + rest.size(); }
}
```

This pattern of implementing an operation over a recursive datatype by

**declaring**the operation in the abstract datatype interface**implementing**the operation (recursively) in each concrete variant

is a very common and practical design pattern.
It sometimes goes by the unhelpful name *interpreter pattern*.

Let’s try a few more examples:

**isEmpty : ImList → boolean**

```
isEmpty(Empty) = true
isEmpty(Cons(elt:E, rest:ImList)) = false
```

You can see the `contains`

operation in action.
First look at how the cases were transformed into Java code, then trace the execution.
Watch the value of `this`

during the recursive calls.

**contains : ImList × E → boolean**

```
contains(Empty, e:E) = false
contains(Cons(elt:E, rest:ImList), e:E) = (elt = e) or contains(rest, e)
```

```
get(Empty, n: int) = undefined
get(Cons(elt:E, rest:ImList), n: int) = if n=0 then elt else get(rest, n-1)
```

**append: ImList × ImList → ImList**

```
append(Empty, list2: ImList) = list2
append(Cons(elt:E, rest:ImList), list2: ImList) = cons(elt, append(rest, list2))
```

```
reverse(Empty) = empty()
reverse(Cons(elt:E, rest:ImList)) = append(reverse(rest), cons(elt, empty())
```

For *reverse*, it turns out that the recursive definition produces a pretty bad implementation in Java, with performance that’s quadratic in the length of the list you’re reversing.
We could rewrite it using an iterative approach if needed.

#### reading exercises

**isEmpty : ImList → boolean**

isEmpty(Empty) = true

isEmpty(Cons(elt: E, rest: ImList)) = false

Let’s implement `ImList.isEmpty`

.

public interface ImList<E> {
// ...
/**
* @return true iff this list is empty
*/

}

(missing explanation)

…

class Empty<E> implements ImList<E> {
// ...
@Override

{
}
}

(missing explanation)

…

class Cons<E> implements ImList<E> {
private final E elt;
private final ImList<E> rest;
// ...
@Override

{
}
}

(missing explanation)

**append: ImList × ImList → ImList**

append(Empty, list2: ImList) = list2

append(Cons(elt: E, rest: ImList), list2: ImList) = cons(elt, append(rest, list2))

Let’s implement `ImList.append`

.

public interface ImList<E> {
// ...
/**
* @param other list to append to this list
* @return list with the elements of this followed by the elements of other
*/

}

…

class Empty<E> implements ImList<E> {
// ...
@Override

{
}
}

(missing explanation)

…

class Cons<E> implements ImList<E> {
private final E elt;
private final ImList<E> rest;
// ...
@Override

{

This time, pick all the correct implementations:

```
}
}
```

(missing explanation)

### Tuning the rep

Getting the size of a list is a common operation.
Right now our implementation of `size()`

takes *O(n)* time, where *n* is the length of the list — that’s linear in the number of list items.
We can make it better with a simple change to the rep of the list that caches the size the first time we compute it, so that subsequently it costs only *O(1)* time — constant time, independent of the number of list items — to get:

```
public class Cons<E> implements ImList<E> {
private final E elt;
private final ImList<E> rest;
private int size = 0;
// rep invariant:
// elt != null, rest != null, size >= 0
// size > 0 implies size == 1+rest.size()
// ...
public int size() {
if (size == 0) size = 1 + rest.size();
return size;
}
}
```

Note that we’re using the special value 0 (which can never be the size of a `Cons`

) to indicate that we haven’t computed the size yet.
Note also that this change introduces a new clause to the rep invariant, relating the `size`

field to the `rest`

field.

There’s something interesting happening here: this is an immutable datatype, and yet it has a mutable rep.
It’s modifying its own size field, in this case to cache the result of an expensive operation.
This is an example of a **beneficent mutation**, a state change that doesn’t change the abstract value represented by the object, so the type is still immutable.

## Rep independence and rep exposure revisited

Does our Java implementation of `ImList`

still have rep independence?
We’ve concealed the `Empty`

contructor behind the static method `ImList.empty()`

, and clients should never need to use the `Empty`

or `Cons`

constructors directly.
We can hide them further by making them package-private (declared with neither the `public`

nor `private`

keyword) so that classes outside of `ImList`

’s package cannot see or use them.

We have a great deal of freedom to change our implementation — indeed, we just added a `size`

field to the internal rep of `Cons`

.
We could even have an extra array in there to make `get()`

run fast!
This might get expensive in space, however, but we are free to make those tradeoffs.

What about an operation like `isEmpty`

above: does that operation break rep independence by revealing the concrete variant to clients?
Is it the same as checking `instanceof Empty`

?
No!
The spec of `isEmpty`

is not, e.g., “return true iff this is an instance of Empty.”
Instead, like any operation of an abstract type, we specify `isEmpty`

abstractly, e.g., “return true iff this list contains no elements.”
Any implementation of immutable lists, whether a recursive Empty-plus-Cons implementation, an array-backed list, a linked list, or something else, can support an `isEmpty`

operation with that spec.

Any time you write an ADT, its specs must not talk about the rep. The concrete variants of a recursive ADT are its rep, so the specs must not mention them.

Finally, is there rep exposure because `Cons.rest()`

returns a reference to its internal list?
Could a clumsy client add elements to the rest of the list?
If so, this would threaten two of `Cons`

’s invariants: that it’s immutable, and that the cached size is always correct.
But there’s no risk of rep exposure, because the internal list is immutable.
Nobody can threaten the rep invariant of `Cons`

.

## Null vs. empty

It might be tempting to get rid of the `Empty`

class and just use `null`

instead.
Resist that temptation.

Using an object, rather than a null reference, to signal the base case or endpoint of a data structure is an example of a design pattern called *sentinel objects*.
The enormous advantage that a sentinel object provides is that it acts like an object in the datatype, so you can call methods on it.
So we can call the `size()`

method even on an empty list.
If empty lists were represented by `null`

, then we wouldn’t be able to do that, and as a consequence our code would be full of tests like:

`if (list != null) n = list.size();`

which clutter the code, obscure its meaning, and are easy to forget. Better the much simpler

`n = list.size();`

which will always work, including when an empty `list`

refers to an `Empty`

object.

Keep `null`

values out of your data structures, and your life will be happier.

## Declared type vs. actual type

Now that we’re using interfaces and classes, it’s worth taking a moment to reinforce an important point about how Java’s type-checking works. In fact every statically-checked object-oriented language works this way.

There are two worlds in type checking: *compile time* before the program runs, and *run time* when the program is executing.
We saw this distinction when we discussed dynamic dispatch.

At compile time, every variable has a *declared type*, also called its *static type* or *compile-time type*, stated in its declaration.
The compiler uses the declared types of variables (and method return values) to deduce static types for every expression in the program.
For example, after a variable declaration `String s`

, the expression `s`

has static type `String`

, `s.charAt(0)`

has static type `char`

, and `s.length()`

has static type `int`

.

At run time, every object has an *actual type*, also called its *dynamic type* or *runtime type*, imbued in it by the constructor that created the object.
For example, `new String()`

makes an object whose actual type is `String`

.
`new Empty()`

makes an object whose actual type is `Empty`

.
`new ImList()`

is forbidden by Java, because `ImList`

is an interface — it has no object values of its own, and no constructors.

#### reading exercises

```
String hello = "Hello";
List<String> words1 = new ArrayList<>();
words1.add(hello);
ImList<String> words2 = ImList.empty();
words2.cons(hello);
```

(missing explanation)

```
String hello = "Hello";
List<String> words1 = new ArrayList<>();
words1.add(hello);
ImList<String> words2 = ImList.empty();
words2.cons(hello);
```

This time, when we say declared/actual type of a variable, we always mean the variable itself ** or** the object pointed to by that variable, whichever is appropriate.

(missing explanation)

## Another example: Boolean formulas

Another useful sort of recursive datatype in computer science is for Boolean formulas. For instance, here’s a formula of propositional logic:

which means “either P or Q is true, *and* either P is false or R is true.”

We can give a datatype definition suitable for representing all formulas of propositional logic.

```
Formula = Variable(name:String)
+ Not(formula:Formula)
+ And(left:Formula, right:Formula)
+ Or(left:Formula, right:Formula)
```

*(P ∨ Q) ∧ (¬P ∨ R)* would be

```
And( Or(Variable("P"), Variable("Q")),
Or(Not(Variable("P")), Variable("R")) )
```

#### reading exercises

Alyssa decides she would like an operation to retrieve all of the variable names in a formula as a set, using the immutable set type `ImSet`

:

**variables : Formula → ImSet<String>**

Suppose immutable `ImSet<E>`

provides three operations:

**emptySet : void → ImSet<E>**

// returns an empty set

**setAdd : E × ImSet<E> → ImSet<E>**

// takes a set and an element and returns the (duplicate-free) set with that element added

**setUnion : ImSet<E> × ImSet<E> → ImSet<E>**

// returns the (duplicate-free) union of two sets

Use those operations to define *variables*.
We’ve defined two of the cases for you:

(missing explanation)

How might we implement immutable `ImSet`

?
Let’s use `ImList`

!

Here’s the datatype definition, then, for `ImSet`

:

`ImSet<E> = ImList<E>`

Let’s define the operations using function notation.
Remember the four original operations of `ImList`

:

**empty: void → ImList**

**cons: E × ImList → ImList**

**first: ImList → E**

**rest: ImList → ImList**

Plus these additional ones we defined:

**size : ImList → int**

**contains : ImList × E → boolean**

We’ll define *emptySet* for you:

**emptySet : void → ImSet<E>**

emptySet() = | empty() |

(missing explanation)

And suppose we implement *setSize* using the *size*:

setSize() = | size() |

(missing explanation)

Complete these recursive definitions:

**setAdd : E × ImSet<E> → ImSet<E>**

if | ||

then | ||

else |

(missing explanation)

**setUnion : ImSet<E> × ImSet<E> → ImSet<E>**

if | ||||

then | ||||

else | ) |

Hint for *setUnion*: make the first argument closer to the `Empty`

base case.

(missing explanation)

A key operation for Boolean formulas is testing whether they are *satisfiable*, that is, whether some assignment of true/false values to the variables leads the formula to evaluate to true.
There is a simple but slow algorithm for checking satisfiability:

Extract the set of variables from the formula.

We’ve already implemented this with the**variables**operation.Try all possible assignments of true/false values to those variables.

We can represent an assignment with an`Environment`

: a list of variables and their values. We could use`ImList`

to implement the`Environment`

, or develop an immutable map type.Evaluate the formula for each environment.

For this, we’ll define**evaluate : Formula × Environment → boolean**.Return the first environment in which the formula evaluates to true.

Defining these pieces and putting them together into a **satisfiable : Formula → boolean** function is an exercise for another time.

## Backtracking search with immutability

We started out this reading with immutable lists, which are a representation that permits a lot of sharing between different list instances. Sharing of a particular kind, though: only the ends of lists can actually be shared. If two lists are identical at the beginning but then diverge from each other, they have to be stored separately. (Why?)

It turns out that backtracking search is a great application for these lists, and here’s why. A search through a space (like the space of assignments to a set of Boolean variables) generally proceeds by making one choice after another, and when a choice leads to a dead end, you backtrack.

Mutable data structures are typically not a good approach for backtracking.
If you use a mutable `Map`

, say, to keep track of the current variable bindings you’re trying, then you have to undo those bindings every time you backtrack.
That’s error-prone and painful compared to what you do with immutable maps — when you backtrack, you just throw the map away!

But immutable data structures with no sharing aren’t a great idea either, because the space you need to keep track of where you are (in the case of the satisfiability problem, the environment) will grow quadratically if you have to make a complete copy every time you take a new step. You need to hold on to all the previous environments on your path, in case you need to back up.

Immutable lists have the nice property that each step taken on the path can share all the information from the previous steps, just by adding to the front of the list. When you have to backtrack, you stop using the current step’s state — but you still have references to the previous step’s state.

Finally, a search that uses immutable data structures is immediately ready to be parallelized. You can delegate multiple processors to search multiple paths at once, without having to deal with the problem that they’ll step on each other in a shared mutable data structure. We’ll talk about this more when we get to concurrency.

## Summary

In addition to the big idea of **recursive datatypes**, we saw in this reading:

**datatype definitions**: a powerful way to think about abstract types, particularly recursive ones**functions over recursive datatypes**: declared in the specification for the type, and implemented with one case per concrete variant- immutable lists: a classic, canonical example of an immutable datatype

As always, we ask how these ideas make our code **safer from bugs**, **easier to understand**, and more **ready for change**.
Look again at the definition and implementation of `size()`

in `ImList`

.
The definition is little more than the mathematical definition of size.
The code is little more than the definition, with some semicolons to placate the compiler.

If we examine the definitions for further methods — `isEmpty`

, `contains`

, etc. — in each case we see a safe, easy-to-read implementation waiting to be coded.
Since we’ve taken the time to specify these operations, if we avoid rep exposure and maintain rep independence, we know our code is ready for change: different clients will be able to reuse our datatype, and we will be able to update the implementation without breaking them.