79 Example: Head-Tail List Functions

The Foundations introduction introduces a simple integer list as a recursive value type. Each list cell has a head value and an optional tail holding the next cell. This chapter uses the same shape to show how ordinary functions can be defined over head-tail lists. Head-tail lists are only an example in this chapter; they are not special syntax and these functions are not assumed to be part of the standard library.

value List
{
    Integer head;
    List tail?;
}

This type represents non-empty finite lists. A one-element list has no tail. Longer lists are built by placing another List in the tail.

var xs =
    List {
        head = 1,
        tail = List {
            head = 2,
            tail = List {
                head = 3,
                tail = none
            }
        }
    };

Membership as an Extension

For membership tests, it is useful to expose the integers contained in the list as a derived extension:

value List
{
    Integer head;
    List tail?;

    → Integer member* = head | tail.member;
}

The derived attribute member contains the head value and all values reached through the tail. This is a membership extension, not the list structure itself: it does not preserve order or duplicates. The ordered head-tail structure is still carried by head and tail.

Boolean Membership Function

The Boolean-valued membership function is then a direct membership test against that extension:

func Boolean memberOf(List list, Integer value) =
    value ∈ list.member;

Because the list is the first parameter, the same function can also be called with receiver-call syntax:

memberOf(xs, 2)
xs.memberOf(2)

Both calls ask whether 2 is a member of the list xs. The receiver-call form does not make memberOf a method stored in List; it is still the ordinary function declared above, with xs supplied as its first argument.

Implementation Note

The definition of memberOf does not require an implementation to materialise the whole member extension before testing membership. Since member is defined as head | tail.member, the expression value ∈ list.member is equivalent to testing value = list.head or, when a tail exists, recursively testing value ∈ list.tail.member.

func Boolean memberOf(List list, Integer value)
{
    if list.head = value {
        return true;
    }

    if list.tail = none {
        return false;
    }

    return list.tail.memberOf(value);
}

This block-bodied version is an implementation strategy for the same function. A compiler or query planner may use a demand-driven traversal, memoisation, indexing, or materialisation, provided the observable result is the same as the declarative definition. The second if statement also demonstrates cardinality flow: after the list.tail = none branch returns, the final statement is checked in the case where list.tail is exactly one.