Next: , Previous: queue, Up: Top   [Contents]


67 ra_list

%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1997, 2000, 2003, 2005-2006 The University of Melbourne.
% Copyright (C) 2014-2015, 2021-2024 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: ra_list.m
% Main author: bromage.
% Stability: medium-low
%
% This module implements `random access lists', or ra_lists for short.
% It is very similar to a list data type, and it supports O(1) head/tail/cons
% operations, but it also supports O(log n) lookup and update.
% The representation is a list of perfectly balanced binary trees.
%
% For more details on the implementation:
%
%   Chris Okasaki, "Purely Functional Random-Access Lists".
%   Functional Programming Languages and Computer Architecture,
%   June 1995, pp 86-95.
%
%--------------------------------------------------%

:- module ra_list.
:- interface.

:- import_module list.

:- type ra_list(T).

%--------------------------------------------------%
%
% Constructing ra_lists.
%

    % Return an empty random access list.
    %
:- pred init(ra_list(T)::uo) is det.

    % Return a random access list containing only the given item.
    %
:- func singleton(T) = ra_list(T).

    % Return a random access list with the given head and tail.
    %
:- pred cons(T::in, ra_list(T)::in, ra_list(T)::out) is det.

%--------------------------------------------------%
%
% Deconstructing ra_lists.
%

    % Return the head of the given random access list.
    % Fail if it is empty.
    %
:- pred head(ra_list(T)::in, T::out) is semidet.

    % Return the tail of the given random access list.
    % Fail if it is empty.
    %
:- pred tail(ra_list(T)::in, ra_list(T)::out) is semidet.

    % Return the head and the tail of the given random access list.
    % Fail if it is empty.
    %
:- pred head_tail(ra_list(T)::in, T::out, ra_list(T)::out) is semidet.

%--------------------------------------------------%
%
% Tests on ra_lists.
%

    % Succeed iff the given random access list is empty.
    %
:- pred is_empty(ra_list(T)::in) is semidet.

    % Succeed iff the given random access list is not empty.
    %
:- pred is_non_empty(ra_list(T)::in) is semidet.
:- pred is_not_empty(ra_list(T)::in) is semidet.

    % Succeed iff the given random access list contains only one item.
    % Return that item.
    %
:- pred is_singleton(ra_list(T)::in, T::out) is semidet.

%--------------------------------------------------%
%
% Counting items in ra_lists.
%

    % Return the number of items in the given random access list.
    %
:- func length(ra_list(T)) = int.
:- pred length(ra_list(T)::in, int::out) is det.

%--------------------------------------------------%
%
% Random access on ra_lists.
%

    % Return the item at the given index in the given random access list.
    % The number at the end of the predicate name gives the index of the first
    % element.
    %
    % Fail if the list is not long enough to have an element
    % at the given index.
    %
:- pred index0(ra_list(T)::in, int::in, T::out) is semidet.
:- pred index1(ra_list(T)::in, int::in, T::out) is semidet.

    % Return the item at the given index in the given random access list.
    % The number at the end of the predicate name gives the index of the first
    % element.
    %
    % Fail if the list is not long enough to have an element
    % at the given index.
    %
:- pred det_index0(ra_list(T)::in, int::in, T::out) is det.
:- pred det_index1(ra_list(T)::in, int::in, T::out) is det.

    % Replace the item at the given index in the given random access list.
    % The first element is at index 0.
    %
    % Fail if the list is not long enough to have an element
    % at the given index.
    %
:- pred update(int::in, T::in, ra_list(T)::in, ra_list(T)::out) is semidet.

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

    % Append two random access lists.
    %
:- pred append(ra_list(T)::in, ra_list(T)::in, ra_list(T)::out) is det.

    % Drop the given number of initial items from the given random access list.
    %
    % Returns the list unchanged if the number of elements to drop is zero
    % or negative.
    %
    % Fail if the list does not have at least that number of elements.
    %
:- pred drop(int::in, ra_list(T)::in, ra_list(T)::out) is semidet.

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

    % Convert a list to a random access list.
    %
:- pred list_to_ra_list(list(T)::in, ra_list(T)::out) is det.

    % Convert a random access list to a plain list.
    %
:- pred ra_list_to_list(ra_list(T)::in, list(T)::out) is det.

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

    % map(F, L) = M:
    % map(P, L, M):
    %
    % Apply the function F or predicate P to transform the elements of L
    % into the elements of M.
    %
:- func map(func(X) = Y, ra_list(X)) = ra_list(Y).
:- pred map(pred(X, Y), ra_list(X), ra_list(Y)).
:- mode map(in(pred(in, out) is det), in, out) is det.
:- mode map(in(pred(in, out) is cc_multi), in, out) is cc_multi.
:- mode map(in(pred(in, out) is semidet), in, out) is semidet.
:- mode map(in(pred(in, out) is multi), in, out) is multi.
:- mode map(in(pred(in, out) is nondet), in, out) is nondet.
:- mode map(in(pred(in, in) is semidet), in, in) is semidet.

    % foldl(Func, List, Start) = End:
    % foldl(Pred, List, Start, End):
    %
    % Calls Func or Pred on each element of List, working left-to-right.
    % Each call to Func or Pred will have a pair of arguments that represent
    % respectively the current and the next value of a piece of state.
    % (Such current-next argument pairs are usually called an accumulator,
    % because the usual use case is that the successive calls to Func or Pred
    % accumulate pieces of information.) The initial value of the accumulator
    % is Start, each call to Func or Pred updates it to the next value, and
    % foldl returns its final value as End.
    %
:- func foldl(func(L, A) = A, ra_list(L), A) = A.
:- pred foldl(pred(L, A, A), ra_list(L), A, A).
:- mode foldl(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldl(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldl(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldl(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldl(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldl(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.
:- mode foldl(in(pred(in, in, out) is multi), in, in, out) is multi.
:- mode foldl(in(pred(in, in, out) is nondet), in, in, out) is nondet.
:- mode foldl(in(pred(in, mdi, muo) is nondet), in, mdi, muo) is nondet.
:- mode foldl(in(pred(in, in, out) is cc_multi), in, in, out) is cc_multi.
:- mode foldl(in(pred(in, di, uo) is cc_multi), in, di, uo) is cc_multi.

    % foldr(Func, List, Start) = End:
    % foldr(Pred, List, Start, End):
    %
    % Calls Func or Pred on each element of List, working right-to-left.
    % Each call to Func or Pred will have a pair of arguments that represent
    % respectively the current and the next value of a piece of state.
    % (Such current-next argument pairs are usually called an accumulator,
    % because the usual use case is that the successive calls to Func or Pred
    % accumulate pieces of information.) The initial value of the accumulator
    % is Start, each call to Func or Pred updates it to the next value, and
    % foldl returns its final value as End.
    %
:- func foldr(func(L, A) = A, ra_list(L), A) = A.
:- pred foldr(pred(L, A, A), ra_list(L), A, A).
:- mode foldr(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldr(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldr(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldr(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldr(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldr(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.
:- mode foldr(in(pred(in, in, out) is multi), in, in, out) is multi.
:- mode foldr(in(pred(in, in, out) is nondet), in, in, out) is nondet.
:- mode foldr(in(pred(in, mdi, muo) is nondet), in, mdi, muo) is nondet.
:- mode foldr(in(pred(in, di, uo) is cc_multi), in, di, uo) is cc_multi.
:- mode foldr(in(pred(in, in, out) is cc_multi), in, in, out) is cc_multi.

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


Next: , Previous: queue, Up: Top   [Contents]