Lists

In list.cecil:

abstract object list[T] isa sequence[T];
extend type list[`T] subtypes list[`S >= T];
signature first(list[`T]):T;
signature rest(list[`T]):list[T];
method collection_name(@:list[`T]):string;
predicate empty_list[T] isa list[T], empty_collection[T];
predicate non_empty_list[T] isa list[T], non_empty_collection[T];
implementation first(@:empty_list[`T]):none;
implementation rest(@:empty_list[`T]):none;

Lists are sequences based on a linked-list representation. General lists support first (a.k.a. car, head) and rest (a.k.a. cdr, tail) operations, plus all the standard sequence operations, like length, is_empty, do, pick_any, includes, find, copy, reverse_do, flatten, ||, etc.

abstract object simple_list[T] isa list[T],
                                   functionally_extensible_collection[T];
var field signature first(simple_list[`T]):T;
var field signature rest(simple_list[`T]):simple_list[T];
signature copy(simple_list[`T]):simple_list[T];
method add_functional(l@:simple_list[`T], x:T):simple_list[T];
method do(c1@:simple_list[`T1], c2@:simple_list[`T2],
               c:&(T1, T2):void):void;
method do(c1@:simple_list[`T1], c2@:simple_list[`T2],
                 c3@:simple_list[`T3], c:&(T1, T2, T3):void):void;
concrete representation nil[T] isa simple_list[T];
method first(@:nil[`T]):none;
method rest(@:nil[`T]):none;
method length(@:nil[`T]):int;
method is_empty(@:nil[`T]):bool;
method do(@:nil[`T], :&(T):void):void;
method reverse_do(@:nil[`T], :&(T):void):void;
method copy(n@:nil[`T]):simple_list[T];
method set_first(@:nil[`T], :T):none;
method set_rest(@:nil[`T], :simple_list[T]):none;
template representation cons[T] isa simple_list[T];
var field first(@:cons[`T]):T;
var field rest(@:cons[`T]):simple_list[T];
method length(c@:cons[`T]):int;
method is_empty(@:cons[`T]):bool;
method do(c@:cons[`T], closure:&(T):void):void;
method reverse_do(c@:cons[`T], closure:&(T):void):void;
method do(c1@:cons[`T1], c2@:cons[`T2], c:&(T1,T2):void):void;
method do(c1@:cons[`T1], c2@:cons[`T2], c3@:cons[`T3],
                 c:&(T1,T2,T3):void):void;
method copy(c@:cons[`T]):simple_list[T];
method cons(hd:T, tl@:simple_list[`T]):cons[T];

Simple lists are mutable Lisp-style singly-linked lists with two representations, nil and cons. Method cons creates a new cons cell; object nil[T] can be used directly. Simple lists are mutable, in the sense that set_first and set_rest operations are defined (they produce run-time errors when invoked on nil). However, simple lists are not extensible_sequences because they do not support add in place. Instead, cons (a.k.a. add_functional) adds to the front of a simple list, returning a new list.

template object m_list[T] isa list[T], extensible_sequence[T];
extend m_list[`T <= comparable[T]] isa removable_collection[T];
method reverse_do(l@:m_list[`T], c:&(T):void):void;
method do(l@:m_list[`T], c:&(T):void):void;
method do(l1@:m_list[`T1], l2@:m_list[`T2], c:&(T1,T2):void):void;
method do(l1@:m_list[`T1], l2@:m_list[`T2], l3@:m_list[`T3],
                 c:&(T1,T2,T3):void):void;
method first(l@:m_list[`T]):T;
method second(l@:m_list[`T]):T;
method rest(l@:m_list[`T]):m_list[T];
method add_first(l@:m_list[`T], x:T):void;
method add_last(l@:m_list[`T], x:T):void;
method remove(l@:m_list[`T <= comparable[T]], x:T, if_absent:&():void):void;
method remove_and_return_one(l@:m_list[`T], test:&(T):bool,
                             if_absent:&():`Else):T|Else;
method remove_if(l@:m_list[`T], test:&(T):bool):int;
method remove_first(l@:m_list[`T], if_empty:&():`S):T|S;
method remove_last(l@:m_list[`T], if_empty:&():`S):T|S;
method splice_onto_end(l1@:m_list[`T], l2:m_list[T]):m_list[T];
method remove_all(l@:m_list[`T]):void;
method new_m_list[T]():m_list[T];
method copy_empty(l@:m_list[`T]):m_list[T];
method copy(l@:`L <= m_list[`T]):LC where signature copy_empty(L):`LC;

To correct this problem, the m_list type defines a full-fledged mutable, extensible list data structure, implemented as a wrapper around a simple list. m_list inherits add and remove from extensible_collection. For historical reasons, add is defined to add to the front of the list. m_list also inherits {add,remove}_{first,last} from extensible_sequence. (This data structure definition doesn't follow the usual pattern: add adds to the front of the collection, not to the end; there is no i_list data type defined and the m_list data type is concrete rather than abstract.) In the future, it would be really nice to define a view of doubly-linked lists that treats them as a sequence of link nodes. Then lots of list splicing operations could be supported that aren't really supported through the existing generic m_list interface. E.g. removing an element from a list during an iteration through it requires two traversals if written in terms of the m_list interface. Doubly-linked and circular lists might also be useful data structures.