    """Represents a collection in which every element has a
       unique non-negative integer index.

       A `List` is a `Collection` of its elements, and a
       `Correspondence` from indices to elements.

       Direct access to a list element by index produces a
       value of optional type. The following idiom may be
       used instead of upfront bounds-checking, as long as
       the list element type is a non-`null` type:

           value char = "hello world"[index];
           if (exists char) { /*do something*/ }
           else { /*out of bounds*/ }

       To iterate the indexes of a `List`, use the following
       idiom:

           for (i->char in "hello world".indexed) { ... }"""
    see (`interface Sequence`,
         `interface Empty`,
         `class Array`)
    shared interface List<out Element>
            satisfies Collection<Element> &
                      Correspondence<Integer,Element> &
                      Ranged<Integer,List<Element>> &
                      Cloneable<List<Element>> {

        "The index of the last element of the list, or
         null if the list is empty."
        see (`value List.size`)
        shared formal Integer? lastIndex;

        "The number of elements in this sequence, always
         `sequence.lastIndex+1`."
        see (`value List.lastIndex`)
        shared actual default Integer size => (lastIndex else -1) + 1;

        shared actual default Boolean shorterThan(Integer length)
                => size<length;

        shared actual default Boolean longerThan(Integer length)
                => size>length;

        "The rest of the list, without the first element."
        shared actual formal List<Element> rest;

        "Determines if the given index refers to an element
             of this sequence, that is, if
             `index<=sequence.lastIndex`."
        shared actual default Boolean defines(Integer index)
                => index <= (lastIndex else -1);

        "Returns the element of this sequence with the given
             index, or `null` if the given index is past the end
             of the sequence, that is, if
             `index>sequence.lastIndex`. The first element of
             the sequence has index `0`."
        shared actual formal Element? get(Integer index);

        shared actual default Iterator<Element> iterator() {
            object listIterator
                    satisfies Iterator<Element> {
                variable Integer index = 0;
                shared actual Element|Finished next() {
                    if (index <= (lastIndex else -1)) {
                        assert (is Element elem = outer.get(index++));
                        return elem;
                    }
                    else {
                        return finished;
                    }
                }
            }
            return listIterator;
        }

        "Reverse this list, returning a new list."
        shared formal List<Element> reversed;

        "Two `List`s are considered equal iff they have the
         same `size` and _entry sets_. The entry set of a
         list `l` is the set of elements of `l.indexed`.
         This definition is equivalent to the more intuitive
         notion that two lists are equal iff they have the
         same `size` and for every index either:

         - the lists both have the element `null`, or
         - the lists both have a non-null element, and the
           two elements are equal."
        shared actual default Boolean equals(Object that) {
            if (is List<Anything> that) {
                if (that.size==size) {
                    for (i in 0..size-1) {
                        value x = this[i];
                        value y = that[i];
                        if (exists x) {
                            if (exists y) {
                                if (x!=y) {
                                    return false;
                                }
                            }
                            else {
                                return false;
                            }
                        }
                        else if (exists y) {
                            return false;
                        }
                    }
                    else {
                        return true;
                    }
                }
            }
            return false;
        }

        shared actual default Integer hash {
            variable value hash = 1;
            for (elem in this) {
                hash *= 31;
                if (exists elem) {
                    hash += elem.hash;
                }
            }
            return hash;
        }

        shared default actual Element? findLast(
                Boolean selecting(Element elem)) {
            if (exists l=lastIndex) {
                variable value index = l;
                while (index >= 0) {
                    if (exists elem = this[index--]) {
                        if (selecting(elem)) {
                            return elem;
                        }
                    }
                }
            }
            return null;
        }

        "Returns the first element of this `List`, if any."
        shared actual default Element? first => this[0];

        "Returns the last element of this `List`, if any."
        shared actual default Element? last {
            if (exists i = lastIndex) {
                return this[i];
            }
            else {
                return null;
            }
        }

        "Returns a new `List` that starts with the specified
         element, followed by the elements of this `List`."
        see (`function following`)
        shared default [Element|Other+] withLeading<Other>(
                "The first element of the resulting sequence."
                Other element) {
            value sb = SequenceBuilder<Element|Other>();
            sb.append(element);
            if (!empty) {
                sb.appendAll(this);
            }
            assert (nonempty seq=sb.sequence);
            return seq;
        }

        "Returns a new `List` that contains the specified
         element appended to the end of the elements of this
         `List`."
        shared default [Element|Other+] withTrailing<Other>(
                "The last element of the resulting sequence."
                Other element) {
            value sb = SequenceBuilder<Element|Other>();
            if (!empty) {
                sb.appendAll(this);
            }
            sb.append(element);
            assert (nonempty seq=sb.sequence);
            return seq;
        }

        "Determine if the given list occurs at the start of this
         list."
        shared default Boolean startsWith(List<Anything> sublist)
                => includesAt(0, sublist);

        "Determine if the given list occurs at the end of this
         list."
        shared default Boolean endsWith(List<Anything> sublist)
                => includesAt(size-sublist.size, sublist);

        "Determine if the given list occurs at the given index
         of this list."
        shared default Boolean includesAt(
                "The index at which this list might occur"
                Integer index,
                List<Anything> sublist) {
            for (i in 0:sublist.size) {
                value x = this[index+i];
                value y = sublist[i];
                if (exists x) {
                    if (exists y) {
                        if (x!=y) {
                            return false;
                        }
                    }
                    else {
                        return false;
                    }
                }
                else if (exists y) {
                    return false;
                }
            }
            else {
                return true;
            }
        }

        "Determine if the given list occurs at some index in
         this list."
        shared default Boolean includes(List<Anything> sublist) {
            for (index in 0:size) {
                if (includesAt(index,sublist)) {
                    return true;
                }
            }
            return false;
        }

        "The indexes in this list at which the given list
         occurs."
        shared default {Integer*} inclusions(List<Anything> sublist)
                => { for (index in 0:size)
                        if (includesAt(index,sublist)) index };

        "The first index in this list at which the given list
         occurs."
        shared default Integer? firstInclusion(List<Anything> sublist) {
            for (index in 0:size) {
                if (includesAt(index,sublist)) {
                    return index;
                }
            }
            else {
                return null;
            }
        }

        "The last index in this list at which the given list
         occurs."
        shared default Integer? lastInclusion(List<Anything> sublist) {
            for (index in (0:size).reversed) {
                if (includesAt(index,sublist)) {
                    return index;
                }
            }
            else {
                return null;
            }
        }

        "Determines if the given value occurs at the
         given index in this list."
        shared default Boolean occursAt(Integer index, Anything element) {
             value elem = this[index];
             if (exists element) {
                 if (exists elem) {
                     return elem==element;
                 }
                 else {
                     return false;
                 }
             }
             else {
                 return !elem exists;
             }
        }

        "Determines if the given value occurs as an
         element in this list."
        shared default Boolean occurs(Anything element) {
             for (index in 0:size) {
                 if (occursAt(index,element)) {
                     return true;
                 }
             }
             return false;
        }

        "Determines if this list contains the given
         value. Equivalent to `occurs()`."
        see (`function occurs`)
        shared actual default Boolean contains(Object element)
                => occurs(element);

        "The indexes in this list at which the given element
         occurs."
        shared default {Integer*} occurrences(Anything element)
                => { for (index in 0:size)
                        if (occursAt(index,element)) index };

        "The first index in this list at which the given element
         occurs."
        shared default Integer? firstOccurrence(Anything element) {
            for (index in 0:size) {
                if (occursAt(index,element)) {
                    return index;
                }
            }
            else {
                return null;
            }
        }

        "The last index in this list at which the given element
         occurs."
        shared default Integer? lastOccurrence(Anything element) {
            for (index in (0:size).reversed) {
                if (occursAt(index,element)) {
                    return index;
                }
            }
            else {
                return null;
            }
        }

        "The indexes in this list for which the element
         satisfies the given predicate."
        shared default {Integer*} indexes(
                "The predicate the indexed elements must satisfy"
                Boolean selecting(Element element))
                => { for (index in 0:size)
                        //TODO: fix this awful hack
                        if (selecting(this[index] else nothing)) index };

        "Trim the elements satisfying the given predicate
         function from the start and end of this list,
         returning a list no longer than this list."
        shared default List<Element> trim(Boolean trimming(Element elem)) {
            if (exists l=lastIndex) {
                variable Integer from=-1;
                variable Integer to=-1;
                for (index in 0..l) {
                    if (!trimming(this[index] else nothing)) {
                        from = index;
                        break;
                    }
                }
                else {
                    return [];
                }
                for (index in l..0) {
                    if (!trimming(this[index] else nothing)) {
                        to = index;
                        break;
                    }
                }
                else {
                    return [];
                }
                return this[from..to];
            }
            else {
                return [];
            }
        }

        "Trim the elements satisfying the given predicate
         function from the start of this list, returning
         a list no longer than this list."
        shared default List<Element> trimLeading(Boolean trimming(Element elem)) {
            if (exists l=lastIndex) {
                for (index in 0..l) {
                    if (!trimming(this[index] else nothing)) {
                        return this[index..l];
                    }
                }
            }
            return [];
        }

        "Trim the elements satisfying the given predicate
         function from the end of this list, returning a
         list no longer than this list."
        shared default List<Element> trimTrailing(Boolean trimming(Element elem)) {
            if (exists l=lastIndex) {
                for (index in l..0) {
                    if (!trimming(this[index] else nothing)) {
                        return this[0..index];
                    }
                }
            }
            return [];
        }

        "Select the first elements of this list, returning a
         list no longer than the given length. If this list is
         shorter than the given length, return this list.
         Otherwise return a list of the given length."
        see (`function List.terminal`)
        shared default List<Element> initial(Integer length)
                => this[0:length];

        "Select the last elements of the list, returning a list
         no longer than the given length. If this list is
         shorter than the given length, return this list.
         Otherwise return a list of the given length."
        see (`function List.initial`)
        shared default List<Element> terminal(Integer length) {
            if (exists l = lastIndex, length>0) {
                return this[l-length+1..l];
            }
            else {
                return [];
            }
        }

        /*"Select the elements between the given indices. If
             the start index is the same as the end index,
             return a list with a single element. If the start
             index is larger than the end index, return the
             elements in the reverse order from the order in
             which they appear in this list. If both the
             start index and the end index are larger than the
             last index in the list, return an empty list.
             Otherwise, if the last index is larger than the
             last index in the list, return all elements from
             the start index to last element of the list."
        shared actual formal List<Element> span(Integer from,
                                            Integer? to);

        "Returns a list containing the elements beginning
             from the given index, with the given length."
        shared actual formal List<Element> segment(Integer from,
                                               Integer length);*/

    }