4.12.3.1 - Functional lists, heads, tails and construction (C#)

Head, tail and empty lists

A non-empty list can be separated into its first element, the head, and a list of the remaining elements, the tail.

The colon denotes construction of a list from an element and a list, as used in Haskell; it is not C#'s list syntax. Repeating the construction gives $4:(3:(5:[]))$. The empty list $[]$ has no head. The singleton list $[5]$ has head 5 and empty tail $[]$, not tail 5. Taking a tail removes only the first element, keeping the remaining order and any duplicate values.

C# List<int> can hold the values. The functions below give explicit head and tail operations; in this interface both require a non-empty input. Rejecting empty input avoids inventing a head value such as 0, which might be a genuine element.

// Methods in class Program; System, System.Collections.Generic and System.Linq imported.
static int Head(List<int> items)
{
    if (items.Count == 0)
        throw new InvalidOperationException("An empty list has no head.");
    return items[0];
}

static List<int> Tail(List<int> items)
{
    if (items.Count == 0)
        throw new InvalidOperationException("Tail requires a non-empty list.");
    return items.Skip(1).ToList();
}

Skip(1) selects the elements after the first, and ToList() constructs a new list. The tail of [4, 3, 5] is therefore a separate [3, 5]; the original is unchanged. For a singleton, skipping its sole element produces an empty list. Some libraries choose a different empty-tail convention, but these functions state their contract; never apply head or tail to empty input without checking it.

Empty checks, length and construction

An empty-list test tells a program when there is no next element to process, while length counts the elements that exist.

// Methods in class Program; System.Collections.Generic imported.
static bool IsEmpty(List<int> items)
{
    return items.Count == 0;
}

static int Length(List<int> items)
{
    return items.Count;
}

static List<int> Empty()
{
    return new List<int>();
}

Empty() constructs a new list containing no elements. It is different from null, which does not refer to a list object. These functions assume the argument refers to a list. Length([]) is 0; Length([0]) is 1. Testing whether the first element equals 0 would not be an empty-list test.

The structural length rule is $\operatorname{length}([])=0$ and $\operatorname{length}(h:t)=1+\operatorname{length}(t)$. For $[4,3,5]$, successive tails have lengths 2, 1 and 0, so there are three elements. A recursive implementation can use this rule; C#'s Count already provides the length directly. Checking emptiness before head/tail access is also the base-case decision needed for recursive processing.

Prepending and appending items

Prepending places an item at the start of a list, while appending places it at the end.