Basic collections

extend module Stdlib;

module Collection;

collection[T] is a collection of items of some type T (or any subtype of T). A collection of some type T is a subtype of all collections of types that are supertypes of T.

abstract class collection[T] isa collection[`S >= T];
abstract class collection_exactly[T] isa collection[T];

Collections support a length operation (implemented by subclasses) which returns the number of elements in the collection, plus a number of length-related predicates.

fun length(:collection[`T]):int;
fun is_empty(c:collection[`T]):bool;  - length = 0
fun non_empty(c:collection[`T]):bool;  - length > 0
fun is_singleton(c:collection[`T]):bool;  - length = 1
fun is_multiple(c:collection[`T]):bool;  - length > 0

Collections support a number of control structures. Primary among all control structures is the do method that iterates through the collection and invokes an argument closure on each element. Elements are processed in some unspecified order which may vary from invocation to invocation, even if the collection is not modified between finishing one do loop and starting the next. For example:

  myCollection.do(&(elem:elemType){     - bind elem to each element
      ...                               - of myCollection in turn
  });

fun do(:collection[`T], closure:&(T):void):void;

The collection cannot be modified while do is active without potentially bizarre results. A related control structure, do_allowing_updates, allows the collection to be modified during the iteration. (The effect of modification during iteration depends on the kind of collection and the kind of update.)

fun do_allowing_updates(t:collection[`T], closure:&(T):void):void;

The do_exit iterator passes an additional argument to its argument closure, which can be invoked to exit the do loop prematurely, analogously to the loop_exit control structure. The do[_exit]_continue iterators are similarly analogous.

fun do_exit(t:collection[`T], closure:&(T, &():none):void):void;
fun do_continue(t:collection[`T], closure:&(T, &():none):void):void;
fun do_exit_continue(t:collection[`T],
                            closure:&(T, &():none, &():none):void):void;

Two collections of comparable elements can be compared to see if they have the same elements, ignoring order, using =_unordered.

fun =_unordered(c1:collection_exactly[`T],
                       c2:collection_exactly[`T]):bool
                                               where T <= comparable[T];
fun !=_unordered(c1:collection_exactly[`T],
                        c2:collection_exactly[`T]):bool
                                               where T <= comparable[T];

The includes method computes whether the collection c contains an element which is equal, using =, to x. The includes_all method returns true if c contains elements which are equal to all the elements of c2. The includes_some method returns true if c contains an element which satisfies the predicate test.

fun includes(c:collection_exactly[`T], x:T):bool where =(:T,:T):bool;
fun includes_all(c1:collection_exactly[`T],
                        c2:collection_exactly[`T]):bool where =(:T,:T):bool;
fun includes_generically(c:collection[`T1 <= `T], x:T):bool
                                                        where =(:T,:T):bool;
fun includes_all_generically(c1:collection[`T1 <= `T],
                                    c2:collection[`T2 <= `T]):bool
                                                        where =(:T,:T):bool;
fun includes_some(c:collection[`T], test:&(T):bool):bool;

The count method returns the number of times an element appears in a collection.

fun count(c:collection_exactly[`T], x:T):int where T <= comparable[T];
fun count_generically(c:collection[`T1 <= `T], x:T):int
                                                where T <= comparable[T];

The count_pred method returns the number of elements of the collection c for which the predicate test evaluates to true.

fun count_pred(c:collection[`T], test:&(T):bool):int;

The find method returns an element of collection c satisfying the predicate test.

fun find(c:collection[`T], test:&(T):bool):T;
fun find(c:collection[`T], test:&(T):bool, if_absent:&():`S):T|S;

Tests whether the predicate is true of every or any collection element. (any is the same as includes_some.)

fun every(c:collection[`T], test:&(T):bool):bool;
fun any(c:collection[`T], test:&(T):bool):bool;

Implements the classic functional reduce operation over collections. Order of reduction is in the collection's order of iteration (i.e., left-to-right for ordered collections, unspecified for unordered collections).

fun reduce(t:collection[`T], bin_op:&(T,S):S, init:`S):S;

Implements a streamlined version that works only on nonempty collections, invoking a closure on an empty collection, and doesn't require an init value.

fun reduce(t:collection[`T], bin_op:&(T,`S >= T):S):S;
fun reduce_nonempty(t:collection[`T], bin_op:&(T,`S >= T):S):S;
fun reduce_nonempty(t:collection[`T], bin_op:&(T,`S >= T):S,
                           if_empty:&():`E):S|E;

The min, max, and average methods are defined on collections as well as pairs of values. They are synonyms of the (min|max|average)_over_all methods, which optionally take a closure to handle empty conditions.

fun min(t:collection[`T <= ordered[T]]):T;
fun min_over_all(t:collection[`T <= ordered[T]]):T;
fun min_over_all(t:collection[`T <= ordered[T]], if_empty:&():`S):T|S;
fun max(t:collection[`T <= ordered[T]]):T;
fun max_over_all(t:collection[`T <= ordered[T]]):T;
fun max_over_all(t:collection[`T <= ordered[T]], if_empty:&():`S):T|S;
fun average(t:collection[`T <= num]):T;
fun average_over_all(t:collection[`T <= num]):T;
fun average_over_all(t:collection[`T <= num], if_empty:&():`S):T|S;
fun total(t:collection[`T <= num]):T|int;

The pick_any method returns some element of the collection, invoking if_empty or producing an error if the collection is empty. The only method returns the only element of the argument collection, producing an error or invoking if_non_singleton if the collection has zero or multiple elements.

fun pick_any(c:collection[`T]):T;
fun pick_any(c:collection[`T1], if_empty:&():`T2):T1|T2;
fun only(c:collection[`T]):T;
fun only(c:collection[`T1], if_non_singleton:&():`T2):T1|T2;
fun select(c:collection[`T], pred:&(T):bool):collection[T];
fun select_first(c:collection[`T], howmany:int):collection[T];
fun select_first(c:collection[`T], hmy:int,
                        pred:&(T):bool):collection[T];
fun select_as_m_list(c:collection[`T], howmany:int, pred:&(T):bool
                            ):m_list[T];
fun select_as_array(c:collection[`T], howmany:int, pred:&(T):bool
                           ):array[T];
fun select_as(c:collection[`T], howmany:int, pred:&(T):bool,
                     result:`R <= extensible_sequence[T]):R;

Collections can be copied. This copy is a shallow copy; the elements of the collection are not copied. If the collection is immutable, the copy function usually returns the collection itself without doing a copy.

fun copy(:collection[`T]):collection[T];

Various files define operations like as_vector, as_m_indexed, etc., for ``downcasting'' and/or converting a collection to a specific kind. Note that if the collection is already of that kind, no copying is done, so don't assume that as_X does a copy!

Various variations on printing a collection are available. The standard print_string behavior includes open_brace, elems_print_string, and then close_brace. By default open_brace contains the name of the collection and an open brace, elems_print_string consists of the elements of the collection, separated by the elem_separator (by default, a comma), and close_brace is a close brace.

fun collection_name(:collection[`T]):string;
fun open_brace(c:collection[`T]):string;
fun close_brace(:collection[`T]):string;
fun elems_print_string(c:collection[`T]):string;
fun elems_print(c:collection[`T]):void;
fun elem_separator(:collection[`T]):string;
fun elem_print_string(t:collection[`T], elem:T, first:bool):string;
fun elem_print(t:collection[`T], elem:T, first:bool):void;

end module Collection;