[m-dev.] Draft collections spec. for library v2

[Ralph Becket]

Comments welcome...

%
----------------------------------------------------------------------------
%
% medison.collections.m
% Ralph Becket <rbeck at microsoft.com>
% Fri Oct 20 13:38:18 BST 2000
% vim: ts=4 sw=4 et tw=0 wm=0 ff=unix
%
% There is an hierarchy of collection types based around whether the
% collection is a set type, a collection of ordered objects, and/or
% a collection of observable objects.
%
% An observable type is one for which two instances that compare as
% equal may still be distinguished by other means (e.g. different
% unordered list representations of the same set).
%
% This makes a difference in that a bag, say, may be implemented using
% run-length encoding for unobservable objects, but not for observable
% objects.
%
% If a collection class does *not* assume that its members are
% observable then the class name takes the suffix `X'.
%
%
----------------------------------------------------------------------------
%

%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%
% coll_x - THE ROOT OF THE HIERARCHY
%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%

:- type coll(T).                        % A collection of T objects.

% CONSTRUCTORS

:- func new = coll(T).

:- func singleton(T) = coll(T).

:- func insert(T, coll(T)) = coll(T).

    % Without extensions to typeclasses, seq(T) == list(T).
    %
:- func insert_seq(seq(T), coll(T)) = coll(T).

:- func union(coll(T), coll(T)) = coll(T).
:- func coll(T) ++ coll(T) = coll(T).   % Synonym for union/2.

    % XXX Is this necessary?  union_seq(S) = foldl(union, new, S).
    %
:- func union_seq(seq(coll(T))) = coll(T).

:- func condense(coll(coll(T))) = coll(T).

:- func from_seq(seq(T)) = coll(T).

% REMOVING MEMBERS

:- func delete_one(T, coll(T)) = coll(T).

:- func delete_all(T, coll(T)) = coll(T).

:- func delete_seq(seq(T), coll(T)) = coll(T).

% OBSERVERS

:- pred empty(coll(T)::in) is semidet.

:- func size(coll(T)) = int.

:- pred contains(coll(T)::in, T::in) is semidet.

:- func count(coll(T), T) = int.

%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%
% ord_coll_x < coll_x - ORDERED COLLECTIONS
%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%

% CONSTRUCTORS

    % These functions exist to cover the cases where the programmer
    % guarantees that the new member has the appropriate property and
    % that testing for it at runtime is too costly.
    %
:- func unsafe_insert_min(T, coll(T)) = coll(T).

:- func unsafe_insert_max(T, coll(T)) = coll(T).

    % The sequence is assumed to be in non-decreasing order.
    %
:- func unsafe_from_ord_seq(seq(T)) = coll(T).

    % Assumes all items in the first ordered collection are =< the
    % items in the second ordered collection.
    %
:- func unsafe_append(coll(T), coll(T)) = coll(T).

% REMOVING MEMBERS

    % Error if collection is empty.
    %
:- func delete_min(coll(T)) = coll(T).

:- func delete_max(coll(T)) = coll(T).

    % As above, but no error if collection is empty.
    %
:- func safe_delete_min(coll(T)) = coll(T).

:- func safe_delete_max(coll(T)) = coll(T).

% FILTERS AND PARTITIONS
%   These allow for more efficient use of built-in comparison functions.
%   XXX Shouldn't deforestation remove higher order calls anyway?

:- func filter_lt(T, coll(T)) = coll(T).
:- func filter_le(T, coll(T)) = coll(T).
:- func filter_gt(T, coll(T)) = coll(T).
:- func filter_ge(T, coll(T)) = coll(T).

:- pred partition_lt_ge(T::in, coll(T)::in, coll(T)::out, coll(T)::out) is
det.
:- pred partition_le_gt(T::in, coll(T)::in, coll(T)::out, coll(T)::out) is
det.
:- pred partition_lt_gt(T::in, coll(T)::in, coll(T)::out, coll(T)::out) is
det.

%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%
% set_x < coll_x - SET COLLECTIONS
%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%

% SET OPERATIONS

:- func intersection(coll(T), coll(T)) = coll(T).

:- func difference(coll(T), coll(T)) = coll(T).

    % subset(S1, S2) succeeds iff all members of S2 are members of S1.
    %
:- pred subset(coll(T)::in, coll(T)::in) is semidet.

    % As above, but S1 must contain a member not in S2.
    %
:- pred proper_subset(coll(T)::in, coll(T)::in) is semidet.

    % Nondeterministically enumerate subsets of a set.
    %
:- pred choose_subset(coll(T)::in, coll(T)::out) is multi.

%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%
% ord_set_x < ord_coll_x, set_x - ORDERED SET COLLECTIONS
%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%

% JUST AN ABBREVIATION FOR THE ABOVE DEPENDENCY

%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%
% coll < coll_x - OBSERVABLE COLLECTIONS
%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%

% OBSERVERS

    % Find all members in the collection equivalent to a given value.
    %
:- func equivalent_members(T, coll(T)) = seq(T).

:- func to_seq(coll(T)) = seq(T).

% FILTERS AND PARTITIONS

:- func filter(pred(T), coll(T)) = coll(T).
:- mode filter(pred(in) is semidet, in) = out is det.

:- pred partition(pred(T) is semidet, coll(T), coll(T), coll(T)).
:- mode partition(pred(in) is semidet, in, out, out) is det.

% FOLDS

:- func fold(func(T1, T2) = T2, T2, coll(T1)) = T2.

:- func fold_1(func(T1, T1) = T1, T1, coll(T1)) = T1.

% MAPPING

:- func map(func(T1) = T2, coll(T1)) = coll(T2).

:- func partial_map(func(T1) = T2, coll(T1)) = coll(T2).
:- mode partial_map(func(in) = out is semidet, in) = out is det.

%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%
% ord_coll < ord_coll_x, coll - OBSERVABLE ORDERED COLLECTIONS
%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%

% DESTRUCTORS

:- func min_member(coll(T)) = T.

:- func max_member(coll(T)) = T.

:- pred min_member_and_rest(coll(T)::in, T::out, coll(T)::out) is semidet.

:- pred max_member_and_rest(coll(T)::in, T::out, coll(T)::out) is semidet.

:- pred min_member_and_rest_det(coll(T)::in, T::out, coll(T)::out) is det.

:- pred max_member_and_rest_det(coll(T)::in, T::out, coll(T)::out) is det.

% OBSERVERS

:- func to_ord_seq(coll(T)) = seq(T).

% FOLDS

:- func foldl(func(T1, T2), T2, coll(T1)) = T2.

:- func foldr(func(T1, T2), T2, coll(T1)) = T2.

:- func foldl_1(func(T1, T1), T1, coll(T1)) = T1.

:- func foldr_1(func(T1, T1), T1, coll(T1)) = T1.

% MAPPING

    % The function argument must satisfy the property
    %
    %   all [X, Y] (X =< Y => f(X) =< f(Y))
    %
:- func unsafe_monotonic_map(func(T1) = T2, coll(T1)) = coll(T2).

%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%
% set < set_x, coll - OBSERVABLE SET COLLECTIONS
%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%

% The `_with' functions take a function argument which decides which of
% two equivalent objects is to be kept.
% XXX Are these really worth it?

:- type select_fn(T)
    ==      ( func(T, T) = T ).

:- func insert_with(select_fn(T), T, coll(T)) = coll(T).

:- func insert_seq_with(select_fn(T), seq(T), coll(T)) = coll(T).

    % Union operations with priority given to members of the
    % left/right collection:
    %
    %   union_l(S1, S2) = union_with(func(X, _) = X, S1, S2)
    %   union_r(S1, S2) = union_with(func(_, Y) = Y, S1, S2)
    %
:- func union_l(coll(T), coll(T)) = coll(T).

:- func union_r(coll(T), coll(T)) = coll(T).

:- func union_with(select_fn(T), coll(T), coll(T)) = coll(T).

:- func union_seq_with(select_fn(T), seq(coll(T))) = coll(T).

:- func from_seq_with(select_fn(T), seq(T)) = coll(T).

:- func intersection_l(coll(T), coll(T)) = coll(T).

:- func intersection_r(coll(T), coll(T)) = coll(T).

:- func intersection_with(select_fn(T), coll(T), coll(T)) = coll(T).

%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%
% ord_set < ord_coll, set - OBSERVABLE ORDERED SETS
%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%

% Just an abbreviation.


--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------