4.12.3.1 - Functional lists, heads, tails and construction (VB.NET)

Head, tail and empty lists

A non-empty list can be described as one first element followed by the remaining list. Its head is that first element; its tail is the list of everything after the head, preserving order.

The same list can be built recursively as 4 : (3 : (5 : [])). The symbol [] denotes the empty list. The square brackets and colon are functional list notation; VB.NET does not use that colon as a list constructor.

The tail of a singleton is still a list, even though it has no elements. The empty list has no first element to remove. A program must check emptiness before using operations that require a head; it must not invent a head of zero. Zero could be a real list element and would hide the distinction.

In our VB.NET representations an Integer() array holds the list values. values(0) reads the head of a non-empty array and values.Skip(1).ToArray() constructs its tail. The source is preserved. Arrays remain mutable objects; we use them without mutation to demonstrate functional list operations.

Length and empty-list operations

Length counts the elements of a list; an empty list has length zero. Testing this condition lets a function choose a safe base case before reading a head.

Imports System
Imports System.Linq

Module Program
    Function EmptyList() As Integer()
        Return New Integer() {}
    End Function

    Function IsEmpty(values As Integer()) As Boolean
        Return values.Length = 0
    End Function

    Function LengthOf(values As Integer()) As Integer
        Return values.Length
    End Function

    Function Head(values As Integer()) As Integer
        If IsEmpty(values) Then
            Throw New ArgumentException("Head requires a non-empty list.")
        End If
        Return values(0)
    End Function

    Function Tail(values As Integer()) As Integer()
        If IsEmpty(values) Then
            Throw New ArgumentException("Tail requires a non-empty list.")
        End If
        Return values.Skip(1).ToArray()
    End Function

    Sub Main()
        Dim empty As Integer() = EmptyList()
        Dim singleton As Integer() = {8}
        Console.WriteLine(IsEmpty(empty))
        Console.WriteLine(LengthOf(singleton))
        Console.WriteLine(LengthOf(Tail(singleton)))
    End Sub
End Module

The outputs are True, 1, and 0. The functions receive a non-null array, a condition supplied by our tasks. New Integer() {} constructs an array with no elements; it is a list value, not Nothing. Both Head and the explicitly defined Tail reject an empty input. LINQ Skip(1) alone would yield an empty sequence for an empty input, but the guard preserves the non-empty precondition of this mathematical tail operation.

To test these operations, include [] for empty detection and length zero, [8] for the singleton-to-empty tail, and [8,2] for length two and tail [2]. Reading a head on [] should trigger the stated exception. These cases check distinct boundaries rather than repeating many similar long lists.

Prepending and appending

Prepending places a new item before all existing items. Appending places a new item after them. These operations return new lists in our functional representation; they preserve the original ordering and source list.