4.12.3.1 - Functional lists, heads, tails and construction (Java)

Head, tail and empty lists

A non-empty list can be separated into its first element and the list that remains.

For $[4,3,5]$, the head is $4$ and the tail is $[3,5]$. Using the Haskell-style head:tail representation,

Here the colon constructs a list by placing an element in front of a list. It is functional list notation, not Java syntax. The final $[]$ is an empty list, which finishes the structure. This explains why a list can be built from repeated head-plus-tail construction.

For $[9]$, the head is $9$ and the tail is $[]$. The empty list itself has no first element: head and tail operations on $[]$ are undefined in this model. Do not invent a head of 0 or treat an empty tail as the number 0. The program must check emptiness before requesting a head or tail when emptiness is possible.

Java's List<Integer> contains integer objects. xs.get(0) obtains its head when the list is non-empty. xs.subList(1, xs.size()) describes the tail portion, but it is a view backed by the original list. Our functional implementation copies it so the returned list does not share that mutable view:

static Integer head(List<Integer> xs) {
    if (xs.isEmpty()) {
        throw new IllegalArgumentException("Empty list has no head");
    }
    return xs.get(0);
}

static List<Integer> tail(List<Integer> xs) {
    if (xs.isEmpty()) {
        throw new IllegalArgumentException("Empty list has no tail");
    }
    return Collections.unmodifiableList(
        new ArrayList<>(xs.subList(1, xs.size())));
}

These methods belong inside Main, with List, Collections and ArrayList imported. unmodifiableList prevents changing the returned list through that reference. Because the elements here are integer values, we need not consider changes inside mutable element objects. The methods do not modify xs.

Length and empty checks

Testing for emptiness and obtaining a length are valid for every list, including an empty list.

An empty check returns a Boolean. A length operation returns the number of elements, not the final index and not the sum of their values. Thus $\operatorname{empty}([])=\mathrm{true}$, $\operatorname{length}([])=0$, and $\operatorname{length}([4,3,5])=3$. Repeated elements each count: $[7,7]$ has length 2.

Java expresses these operations as xs.isEmpty() and xs.size(). Collections.emptyList() constructs an empty list value of the inferred element type; it does not construct a list whose only element is null or zero.

List<Integer> empty = Collections.emptyList();
List<Integer> one = Collections.singletonList(0);
System.out.println(empty.isEmpty());
System.out.println(empty.size());
System.out.println(one.isEmpty());
System.out.println(one.size());

These statements belong inside main with the required imports. The outputs are true, 0, false, 1. A list containing 0 is not empty. Neither is a list containing an empty list: its outer list has one element, though that element's own length is 0.

Emptiness gives a base case for recursive processing. In a head–tail definition of length, $\operatorname{length}([])=0$, while a non-empty list has length $1+\operatorname{length}(\operatorname{tail}(xs))$. Each call processes a shorter tail, so it eventually reaches the empty list. The library's size() supplies the same required operation without making a recursive call in our code.

These boundary cases distinguish list structure from the values stored in it.

Prepending and appending

Prepending and appending construct a list with one new element at different ends.

Prepend places an item before every original element: $\operatorname{prepend}\;7\;[4,3,5]=[7,4,3,5]$. This is the same construction as $7:[4,3,5]$. Append places an item after every original element: $\operatorname{append}\;7\;[4,3,5]=[4,3,5,7]$. Appending the item 7 differs from appending a whole list as one nested item.

Both operations on an empty list produce the singleton list $[7]$. On a non-empty list they usually produce different orders. Both increase length by one; neither removes repetitions. Functional construction leaves the original list available unchanged.