[m-dev.] Suggested interface for sequence types in lib-v2

[Ralph Becket]

This is a very rough first cut spec. for the interface to sequence
types for v2 of the std library.  For now, conforming to the
interface will have to be by convention since the typeclass system
isn't up to the job (we need functional dependencies).

Ralph

%
----------------------------------------------------------------------------
%
% medison.sequences.m
% Ralph Becket <rbeck at microsoft.com>
% Wed Oct 11 12:05:57 BST 2000
% vim: ts=4 sw=4 et tw=0 wm=0 ff=unix
%
% This is a draft spec. for the interfaces for various library data
% types for version 2 of the Mercury standard library.  It is inspired
% by Chris Okasaki's Edison library, but does not attempt to conform
% in any particular way (partly due to aesthetic differences, partly
% due to the fact that Mercury is also a logic language.)
%
% Ideally, this specification would be presented as a set of typeclasses.
% Unfortunately, Mercury does not currently support constructor classes
% and functional dependencies on typeclasses, so we can't do this yet.
% 
% The library is divided into four sections:
% - Sequences
% - The collection hierarchy
% - The map hierarchy
% - Miscellaneous
%
% XXX We really want to parameterise the modes for these things where
% appropriate when this facility becomes available.
%
% XXX For now I've omitted documentation where I believe things are
% obvious.  Proper documentation needs to be added.
%
% XXX I think we should provide default implementations for various 
% methods, e.g.
%
%   singleton(X) = cons(X, new)
%   snoc(X, Xs) = append(Xs, singleton(X))
%   from_list(Xs) = foldr(cons, Xs, new)
%   etc.
%
%
----------------------------------------------------------------------------
%

%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%
% SEQUENCES
%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%

:- type seq(T).                         % A sequence of T objects.

% CONSTRUCTORS

:- func new = seq(T).

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

:- func cons(T, seq(T)) = seq(T).

:- func snoc(T, seq(T)) = seq(T).       % RAO'K hates this name.

:- func from_list(list(T)) = seq(T).

:- func n_copies(int, T) = seq(T).

% DESTRUCTORS

    % XXX Should we overload [_|_] for sequences?

:- func head(seq(T)) = T.
:- func semidet_head(seq(T)) = T.

:- func tail(seq(T)) = seq(T).
:- func semidet_tail(seq(T)) = seq(T) is semidet.

:- pred head_tail(seq(T)::in, T::out, seq(T)::out).
:- pred semidet_head_tail(seq(T)::in, T::out, seq(T)::out) is semidet.

:- func last(seq(T)) = T.
:- func semidet_last(seq(T)) = T is semidet.

:- func but_last(seq(T)) = seq(T).
:- func semidet_but_last(seq(T)) = seq(T) is semidet.

% XXX Do we want {semidet_,}but_last_last/1?

% OBSERVERS

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

:- func length(seq(T)) = int.

:- func to_list(seq(T)) = list(T).

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

:- pred member(T::out, seq(T)::in) is nondet.
:- pred project_member(seq(T)::in, T::out) is nondet.

% CONCATENATION AND REVERSAL

:- func append(seq(T), seq(T)) = seq(T).
:- func seq(T) ++ seq(T) = seq(T).      % Synonym for append/2.

:- func reverse(seq(T)) = seq(T).

:- func rev_append(seq(T), seq(T)) = seq(T).

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

% MAPPING AND FOLDING

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

    % Ignores those members for which F is not defined.
    %
:- func partial_map(func(T1) = T2, seq(T1)) = seq(T2).
:- mode partial_map(func(in) = out is semidet, in) = out is det.

:- pred partial_filter_map(func(T1) = T2, seq(T1), seq(T2), seq(T1)).
:- mode partial_filter_map(func(in) = out is semidet, in, out, out) is det.

                                        % XXX Is this really useful?
:- func condense_map(func(T1) = seq(T2), seq(T1)) = seq(T2).

    % The suffix `_1' indicates that the starting value is taken as
    % the head of the sequence.  It is an error to pass an empty
    % sequence to such a function.

:- func foldl(func(T1, T2) = T2, T2, seq(T1)) = T2.
:- func foldl_1(func(T1, T1) = T1, seq(T1)) = T1.

:- func foldr(func(T1, T2) = T2, T2, seq(T1)) = T2.
:- func foldr_1(func(T1, T1) = T1, seq(T1)) = T1.

    % Reduce assumes the function argument to be associative and is
    % free to bracket in any order.
    % e.g. reduce_1((*), [W, X, Y, Z]) = (W*X)*(Y*Z) = (W*(X*Y))*Z = etc.
    %
:- func reduce(func(T1, T1) = T1, T1, seq(T1)) = T1.
:- func reduce_1(func(T1, T1) = T1, seq(T1)) = T1.

    % XXX Do we want partial_{foldl,reduce} etc?

% SUBSEQUENCES

:- func take_n(int, seq(T)) = seq(T).   % Error if length(S) < N.
:- func take_up_to_n(int, seq(T)) = seq(T).

:- func drop_n(int, seq(T)) = seq(T).   % Error if length(S) < N.
:- func drop_up_to_n(int, seq(T)) = seq(T).

    % split_after_n(N, S, F, B) <=> F = take_n(N, S), B = drop_n(N, S).
    %
:- pred split_after_n(int::in, seq(T)::in, seq(T)::out, seq(T)::out).
:- pred split_after_n_or_end(int::in, seq(T)::in, seq(T)::out, seq(T)::out).

    % subseq(I, N, S) = take_n(N, drop_n(I, S))
    %
    % safe_subseq(I, N, S) = take_up_to_n(N, drop_up_to_n(I, S))
    %
:- func subseq(int, int, seq(T)) = seq(T).
:- func safe_subseq(int, int, seq(T)) = seq(T).

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

    % partition(P, S, Ys, Ns) <=> Ys = filter(P, S), Ns = filter(isnt(P), S)
    %
:- pred partition(pred(T), seq(T), seq(T), seq(T)).
:- mode partition(pred(in) is semidet, in, out, out) is det.

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

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

    % split_where(P, S, F, B) <=> F is the prefix of S for which P fails,
    %                             B is the remainder of S.
:- pred split_where(pred(T), seq(T), seq(T), seq(T)).
:- mode split_where(pred(in) is semidet, in, out, out) is det.

% REMOVING MEMBERS

                                        % Error unless S `contains` X.
:- func delete_first(T, seq(T)) = seq(T).
:- func delete_first_if_any(T, seq(T)) = seq(T).

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

% INDEX BASED OPERATIONS
                                        % index_in(S, head(S)) = 0.
:- func index_in(seq(T), T) = int.      % Error unless S `contains` X.
:- func semidet_index_in(seq(T), T) = int is semidet.

:- func lookup(seq(T), int) = T.        % Error unless 0 =< I < length(S).
:- func seq(T) @ int = T.               % Synonym for lookup/2.
:- func semidet_lookup(seq(T), int) = T.

    % replace(S, I, X) = take_n(I - 1, S) ++ cons(X, drop_up_to_n(I, S))
    % Error unless 0 =< I < length(S).
    %
:- func replace(seq(T), int, T) = seq(T).

    % change(S, I, F) = take_n(I - 1, S) ++ cons(F(lookup(S, I)), drop_n(I,
S))
    % Error unless 0 =< I < length(S).
    %
:- func change(seq(T), int, func(T) = T) = seq(T).

    % XXX Do we want {filter,map,foldl,foldr,reduce}_with_index etc?

% ZIPPING AND UNZIPPING

    % interleave([A, B, C], [X, Y, Z]) = [A, X, B, Y, C, Z].
    % Error unless length(S1) = length(S2) + N for N in {0, 1}.
    %
:- func interleave(seq(T), seq(T)) = seq(T).

    % uninterleave([A, X, B, Y, C, Z], [A, B, C], [X, Y, Z]).
    %
:- pred uninterleave(seq(T)::in, seq(T)::out, seq(T)::out) is det.

    % Error unless length(S1) = length(S2).
    %
:- func zip(func(T1, T2) = T3, seq(T1), seq(T2)) = seq(T3).

%
----------------------------------------------------------------------------
%
%
----------------------------------------------------------------------------
%

--
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
--------------------------------------------------------------------------