17 cord
%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 2002-2011 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: cord.m.
% Author: Ralph Becket <rafe@cs.mu.oz.au>
% Stability: medium.
%
% A cord is a sequence type supporting O(1) consing and concatenation.
% A cord is essentially a tree structure with data stored in the leaf nodes.
% Joining two cords together to construct a new cord is therefore an O(1)
% operation.
%
% This data type is intended for situations where efficient, linearised
% collection of data is required.
%
% While this data type presents a list-like interface, calls to list/1 and
% head_tail/3 in particular are O(n) in the size of the cord.
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module cord.
:- interface.
:- import_module list.
%--------------------------------------------------%
% Cords that contain the same members in the same order will not
% necessarily have the same representation and will, therefore,
% not necessarily either unify or compare as equal.
%
% The exception to this rule is that the empty cord does have a
% unique representation.
%
:- type cord(T).
% Return the empty cord.
%
:- func init = cord(T).
% The unique representation for the empty cord:
%
% list(empty) = []
%
:- func empty = cord(T).
% The list of data in a cord:
%
% list(empty ) = []
% list(from_list(Xs)) = Xs
% list(cons(X, C) ) = [X | list(C)]
% list(TA ++ TB ) = list(TA) ++ list(TB)
%
:- func list(cord(T)) = list(T).
% rev_list(Cord) = list.reverse(list(Cord).
%
:- func rev_list(cord(T)) = list(T).
% Succeed iff the given cord is empty.
%
:- pred is_empty(cord(T)::in) is semidet.
% list(singleton(X)) = [X]
%
:- func singleton(T) = cord(T).
% list(from_list(Xs)) = Xs
% An O(1) operation.
%
:- func from_list(list(T)) = cord(T).
% list(cons(X, C)) = [X | list(C)]
% An O(1) operation.
%
:- func cons(T, cord(T)) = cord(T).
% list(snoc(C, X)) = list(C) ++ [X]
% An O(1) operation.
%
:- func snoc(cord(T), T) = cord(T).
% list(CA ++ CB) = list(CA) ++ list(CB)
% An O(1) operation.
%
:- func cord(T) ++ cord(T) = cord(T).
% Append together a list of cords.
%
:- func cord_list_to_cord(list(cord(T))) = cord(T).
% Append together a list of cords, and return the result as a list.
%
:- func cord_list_to_list(list(cord(T))) = list(T).
% head_tail(C0, X, C) => list(C0) = [X | list(C)]
% not head_tail(C0, _, _) => C0 = empty
% An O(n) operation, although traversing an entire cord with
% head_tail/3 gives O(1) amortized cost for each call.
%
:- pred head_tail(cord(T)::in, T::out, cord(T)::out) is semidet.
% split_last(C0, C, X) => list(C0) = C ++ [X].
% not split_last(C0, _, _) => C0 = empty
% An O(n) operation, although traversing an entire cord with
% split_last/3 gives O(1) amortized cost for each call.
%
:- pred split_last(cord(T)::in, cord(T)::out, T::out) is semidet.
% get_first(C0, X) => some [C]: list(C0) = [X] ++ C.
% not get_first(C0, _) => C0 = empty
%
:- pred get_first(cord(T)::in, T::out) is semidet.
% get_last(C0, X) => some [C]: list(C0) = C ++ [X].
% not get_last(C0, _) => C0 = empty
%
:- pred get_last(cord(T)::in, T::out) is semidet.
% length(C) = list.length(list(C))
% An O(n) operation.
%
:- func length(cord(T)) = int.
% member(X, C) <=> list.member(X, list(C)).
%
:- pred member(T::out, cord(T)::in) is nondet.
% list(map(F, C)) = list.map(F, list(C))
%
:- func map(func(T) = U, cord(T)) = cord(U).
:- pred map_pred(pred(T, U)::in(pred(in, out) is det),
cord(T)::in, cord(U)::out) is det.
% filter(Pred, Cord, TrueCord):
%
% Pred is a closure with one input argument.
% For each member X of Cord,
% - Pred(X) is true, then X is included in TrueCord.
%
:- pred filter(pred(T)::in(pred(in) is semidet),
cord(T)::in, cord(T)::out) is det.
% filter(Pred, Cord, TrueCord, FalseCord):
%
% Pred is a closure with one input argument.
% For each member X of Cord,
% - Pred(X) is true, then X is included in TrueCord.
% - Pred(X) is false, then X is included in FalseCord.
%
:- pred filter(pred(T)::in(pred(in) is semidet),
cord(T)::in, cord(T)::out, cord(T)::out) is det.
% foldl(F, C, A) = list.foldl(F, list(C), A).
%
:- func foldl(func(T, U) = U, cord(T), U) = U.
:- pred foldl_pred(pred(T, U, U), cord(T), U, U).
:- mode foldl_pred(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldl_pred(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldl_pred(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldl_pred(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldl_pred(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldl_pred(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.
% foldr(F, C, A) = list.foldr(F, list(C), A).
%
:- func foldr(func(T, U) = U, cord(T), U) = U.
:- pred foldr_pred(pred(T, U, U), cord(T), U, U).
:- mode foldr_pred(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldr_pred(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldr_pred(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldr_pred(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldr_pred(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldr_pred(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.
% map_foldl(P, CA, CB, !Acc):
%
% This predicate calls P on each element of the input cord, working
% left to right. Each call to P transforms an element of the input cord
% to the corresponding element of the output cord, and updates the
% accumulator.
%
:- pred map_foldl(pred(A, B, C, C), cord(A), cord(B), C, C).
:- mode map_foldl(in(pred(in, out, in, out) is det), in, out, in, out)
is det.
:- mode map_foldl(in(pred(in, out, mdi, muo) is det), in, out, mdi, muo)
is det.
:- mode map_foldl(in(pred(in, out, di, uo) is det), in, out, di, uo)
is det.
:- mode map_foldl(in(pred(in, out, in, out) is semidet), in, out, in, out)
is semidet.
:- mode map_foldl(in(pred(in, out, mdi, muo) is semidet), in, out, mdi, muo)
is semidet.
:- mode map_foldl(in(pred(in, out, di, uo) is semidet), in, out, di, uo)
is semidet.
% As above, but with two accumulators.
%
:- pred map_foldl2(pred(A, B, C, C, D, D)::
in(pred(in, out, in, out, in, out) is det),
cord(A)::in, cord(B)::out, C::in, C::out, D::in, D::out) is det.
% As above, but with three accumulators.
%
:- pred map_foldl3(pred(A, B, C, C, D, D, E, E)::
in(pred(in, out, in, out, in, out, in, out) is det),
cord(A)::in, cord(B)::out, C::in, C::out, D::in, D::out, E::in, E::out)
is det.
% equal(CA, CB) <=> list(CA) = list(CB).
% An O(n) operation where n = length(CA) + length(CB).
%
% (Note: the current implementation works exactly this way.)
%
:- pred equal(cord(T)::in, cord(T)::in) is semidet.
%--------------------------------------------------%
%--------------------------------------------------%