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

[Ralph Becket]

Here's the updated spec., having taken Fergus' comments on board.

%
----------------------------------------------------------------------------
%
% 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 is semidet.

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

    % not empty(S) => (S = snoc(last(S), all_but_last(S)))
    %
:- func all_but_last(seq(T)) = seq(T).
:- func semidet_all_but_last(seq(T)) = seq(T) is semidet.

% XXX Do we want {semidet_,}all_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.

    % project_member/2 simply reverses the argument order of member/2.
    % It may be more useful for higher order programming.
    %
:- 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.

    % Removed until sufficient demand has been demonstrated.
    % Equivalent code would be
    %   condense(map(F, S))
    % or, more efficiently,
    %   foldl(func(X, Xs) = F(X) ++ Xs, new, S)
    %
% :- 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).
    % The jury is still out on this one.
% :- func seq(T) @ int = T.               % Synonym for lookup/2.
:- func search(seq(T), int) = T is semidet.

    % 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) = replace(S, I, F(S `lookup` I)).
    % 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
--------------------------------------------------------------------------