Cons list in Java
The fundamental data structure in many functional languages is the immutable linked list.
It is constructed from two building blocks:
Nil: The empty list
Cons: A cell containing an element also known as head; and a pointer to the rest of the list also known as tail.
The term cons comes form functional programming language ‘lisp’. In Scala, there is a double colon operator :: called cons operator.
Let’s take an example in Scala. Consider following list.
List(1, 2, 3) or 1 :: 2 :: 3 :: Nil
In memory, the list is represented as follow:
*--*--*--Nil
| | |
1 2 3In the diagram above * represents a cons cell, which contains an element and a reference to next cons cell.
e.g. first cons cell stores the value of integer 1 and points to the next cons cell which hold a value of integer 2.
Technically, the cons list is also a (unbalanced) binary tree.
The representation above can be re-arranged as follow:
*
/ \
1 *
/ \
2 *
/ \
3 NilLet’s see how this could be modelled in Java. The basic structure of cons list can be implemented using following abstract class.
public abstract class ConsList<T> {
protected T head;
protected ConsList<T> tail;
public abstract boolean isEmpty();
public T head() {
return head;
}
public ConsList<T> tail() {
return tail;
}
}The ConsList can have a head element and a tail which itself is a ConsList.
Now there are two special implementation cases possible for ConsList.
- Nil: An empty list
- Cons: A list with a head and tail
Let’s create concrete classes for these cases.
public class Nil<T> extends ConsList<T> {
private static Nil Nil;
public static <T> Nil<T> getNil() {
if(Nil == null) {
Nil = new Nil<T>();
}
return Nil;
}
private Nil() { }
@Override
public boolean isEmpty() {
return true;
}
@Override
public T head() {
throw new NoSuchElementException("head of empty list");
}
@Override
public ConsList<T> tail() {
throw new UnsupportedOperationException("tail of empty list");
}
}The Nil will be used to denote an empty list. Hence isEmpty method always returns true. The head and tail methods throw exceptions, since these operations cannot be performed on an empty list. Nil is typically used to denote an end of the list.
There will always be a single instance of Nil class used to denote an empty list, so we can mark this class as an inner class of ConsList and create a singleton Nil object.
The ConsList class can be modified to include this singleton Nil as a static member.
public abstract class ConsList<T> {
T head;
ConsList<T> tail;
public abstract boolean isEmpty();
public static <T> ConsList<T> Nil() {
return getNil();
}
public T head() {
return head;
}
public ConsList<T> tail() {
return tail;
}
}And finally the implementation of cons operations.
public class Cons<T> extends ConsList<T> {
private Cons(T head, ConsList<T> tail) {
this.head = head;
this.tail = tail;
}
public static <T> Cons<T> cons(T head, ConsList<T> tail) {
return new Cons<>(head, tail);
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public String toString() {
return "List(" + toString(this) + ")";
}
private String toString(ConsList<T> list) {
return list.isEmpty() ? "" :
list.head() +
(list.tail().isEmpty() ? "" :
", " + toString(list.tail()));
}
}Note that the constructor is private and the list can be formed using cons method which take head and tail and creates a cons cell by connecting head with tail. The isEmpty method would always return false.
Now the list can be constructed using following syntax:
ConsList<Integer> list2 = cons(1, cons(2, cons(3, Nil())));
ConsList<String> colors = cons("Red", cons("Green", cons("Blue", Nil())));Now we know how to compose a cons list recursively. Lets try to do some operations on the cons lists using recursion.
Sum of all numbers in a list
int sum(ConsList<Integer> list) {
return list.isEmpty() ? 0 : list.head() + sum(list.tail());
}Square all the numbers in a list
ConsList<Integer> square(ConsList<Integer> list) {
return list.isEmpty() ? list :
cons(list.head() * list.head(), square(list.tail()));
}Increment all the numbers in a list by 1
ConsList<Integer> increment(ConsList<Integer> list) {
return list.isEmpty() ? list :
cons(list.head() + 1, increment(list.tail()));
}There is a repetitive pattern in above two examples. All we are trying to do is, transform each element in a list by applying some kind of operations like square / increment. This can be made generic using Function. This kind of transform operation is typically known as map operation.
ConsList<Integer> map(ConsList<Integer> list, Function<Integer, Integer> function) {
return list.isEmpty() ? list :
cons(function.apply(list.head()), map(list.tail(), function));
}Then this method can be called as follow
ConsList<Integer> integers = cons(1, cons(2, cons(3, Nil())));System.out.println(map(integers, n -> n * n));
// List(1, 4, 9)System.out.println(map(integers, n -> n + 1));
// List(2, 3, 4)
This map method can be performed on a list which contains elements of any type. Since the operation is performed on list itself, we can avoid passing the list every time by moving this method to ConsList class itself. Let’s make it generic to run on a list of any type.
@Override
public <R> ConsList<R> map(Function<T, ? extends R> function) {
return cons(
function.apply(this.head()),
this.tail.map(function)
);
}Then it can be used as follow
ConsList<Integer> list = integers.map(n -> n * n);
// List(2, 3, 4)ConsList<String> colors = cons("Red", cons("Green", cons("Blue", Nil())));
System.out.println(colors.map(String::toUpperCase));
// List(RED, GREEN, BLUE)
Tail recursion
If you try to compute a sum using recursion for a huge numbers, it’s likely to throw a stackoverflow exception. Many functional languages like Scala address this using tail recursion. However Java compiler does not optimise the recursive call even if it is written in tail recursive way. We will explore more about tail recursion in another blog post.
Structural sharing
The cons list we created is a immutable data structure. It cannot be modified. If we want to modify it, a new immutable list would be created.
e.g. the map operation mentioned above creates a new list by modifying the elements keeping the original list intact. These kind of data structures are called persistent data structures.
Since the data structure is immutable, one might think that a lot of memory would be consumed since a new list would be created when we try to perform various operations on list. On the contrary, these kind of data structures allow structural sharing by sharing nodes.
e.g. consider following operations on list
list1 ++ list2 or list1.append(list2)Here a new list will be created, which will contain elements from both the lists. But in memory all the nodes in newly created appended list would point to the nodes used by list1 and list2. Hence consuming almost no more memory.
The implementation of append lists can be written as follow by introducing append method in Cons and Nil class.
In Cons class
@Override
public ConsList<T> append(ConsList<T> other) {
return cons(this.head(), this.tail.append(other));
}and in Nil class
@Override
public ConsList<T> append(ConsList<T> other) {
return other;
}When to use cons list
- Cons list is suitable in multithreaded environment as its a immutable data structure. Any operations performed on the cons list creates a new lists and existing elements cannot be modified.
- Head/Tail decomposition: The ability to decompose the list into head and it’s tail allows programmers to write algorithms in recursive form very easily. These kind of algorithms are easy to understand and debug. And may cause less number of bugs.
3. Building a list is a constant time operation. You just create a new node that points to the already existing list.
When not to use cons list
- When you need to access random element in a list using index
- When you want to create a list by dynamically appending items to an empty list.
- When performance / Memory is a concern. Mutable data structures would be little bit faster and would consume a little less space.
Cons lists are very useful when you are looking for writing a concise functional or declarative style code compared to bug prone imperative style code.
That being said, As an exercise, try to write a filter function in ConsList which filters elements based on a predicate. Make sure that structural sharing is done while creating a filtered list.
