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