%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1993-1995, 1997-2012 The University of Melbourne.
% Copyright (C) 2013-2023 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: array.m.
% Main authors: fjh, bromage.
% Stability: medium-low.
%
% This module provides dynamically-sized one-dimensional arrays.
% Array indices start at zero.
%
% WARNING!
%
% Arrays are currently not unique objects. Until this situation is resolved,
% it is up to the programmer to ensure that arrays are used in ways that
% preserve correctness. In the absence of mode reordering, one should therefore
% assume that evaluation will take place in left-to-right order. For example,
% the following code will probably not work as expected (f is a function,
% A an array, I an index, and X an appropriate value):
%
% Y = f(A ^ elem(I) := X, A ^ elem(I))
%
% The compiler is likely to compile this as
%
% V0 = A ^ elem(I) := X,
% V1 = A ^ elem(I),
% Y = f(V0, V1)
%
% and will be unaware that the first line should be ordered *after* the second.
% The safest thing to do is write things out by hand in the form
%
% A0I = A0 ^ elem(I),
% A1 = A0 ^ elem(I) := X,
% Y = f(A1, A0I)
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module array.
:- interface.
:- import_module list.
:- import_module pretty_printer.
:- type array(T).
:- inst array(I) == ground.
:- inst array == array(ground).
% XXX the current Mercury compiler doesn't support `ui' modes,
% so to work-around that problem, we currently don't use
% unique modes in this module.
% :- inst uniq_array(I) == unique.
% :- inst uniq_array == uniq_array(unique).
:- inst uniq_array(I) == array(I). % XXX work-around
:- inst uniq_array == uniq_array(ground). % XXX work-around
:- mode array_di == di(uniq_array).
:- mode array_uo == out(uniq_array).
:- mode array_ui == in(uniq_array).
% :- inst mostly_uniq_array(I) == mostly_unique).
% :- inst mostly_uniq_array == mostly_uniq_array(mostly_unique).
:- inst mostly_uniq_array(I) == array(I). % XXX work-around
:- inst mostly_uniq_array == mostly_uniq_array(ground). % XXX work-around
:- mode array_mdi == mdi(mostly_uniq_array).
:- mode array_muo == out(mostly_uniq_array).
:- mode array_mui == in(mostly_uniq_array).
% An `index_out_of_bounds' is the exception thrown
% on out-of-bounds array accesses. The string describes
% the predicate or function reporting the error.
:- type index_out_of_bounds
---> index_out_of_bounds(string).
%--------------------------------------------------%
%
% Creating arrays.
%
% init(Size, Init, Array):
%
% Creates an array with bounds from 0 to Size-1, with each element
% initialized to Init. Throws an exception if Size < 0.
%
:- func init(int::in, T::in) = (array(T)::array_uo) is det.
:- pred init(int::in, T::in, array(T)::array_uo) is det.
% make_empty_array(Array):
%
% Creates an array of size zero starting at lower bound 0.
%
:- func make_empty_array = (array(T)::array_uo) is det.
:- pred make_empty_array(array(T)::array_uo) is det.
% generate(Size, Generate) = Array:
%
% Create an array with bounds from 0 to Size - 1 using the function
% Generate to set the initial value of each element of the array.
% The initial value of the element at index K will be the result of
% calling the function Generate(K). Throws an exception if Size < 0.
%
:- func generate(int::in, (func(int) = T)::in) = (array(T)::array_uo) is det.
% generate_foldl(Size, Generate, Array, !AccA):
%
% As above, but using a predicate with an accumulator threaded through it
% to generate the initial value of each element.
%
:- pred generate_foldl(int, pred(int, T, A, A), array(T), A, A).
:- mode generate_foldl(in, in(pred(in, out, in, out) is det),
array_uo, in, out) is det.
:- mode generate_foldl(in, in(pred(in, out, mdi, muo) is det),
array_uo, mdi, muo) is det.
:- mode generate_foldl(in, in(pred(in, out, di, uo) is det),
array_uo, di, uo) is det.
:- mode generate_foldl(in, in(pred(in, out, in, out) is semidet),
array_uo, in, out) is semidet.
:- mode generate_foldl(in, in(pred(in, out, mdi, muo) is semidet),
array_uo, mdi, muo) is semidet.
:- mode generate_foldl(in, in(pred(in, out, di, uo) is semidet),
array_uo, di, uo) is semidet.
% generate_foldl2(Size, Generate, Array, !AccA, !AccB):
%
% As above, but using a predicate with two accumulators threaded through it
% to generate the initial value of each element.
%
:- pred generate_foldl2(int, pred(int, T, A, A, B, B), array(T), A, A, B, B).
:- mode generate_foldl2(in, in(pred(in, out, in, out, in, out) is det),
array_uo, in, out, in, out) is det.
:- mode generate_foldl2(in, in(pred(in, out, mdi, muo, mdi, muo) is det),
array_uo, mdi, muo, mdi, muo) is det.
:- mode generate_foldl2(in, in(pred(in, out, di, uo, di, uo) is det),
array_uo, di, uo, di, uo) is det.
:- mode generate_foldl2(in, in(pred(in, out, in, out, in, out) is semidet),
array_uo, in, out, in, out) is semidet.
:- mode generate_foldl2(in, in(pred(in, out, mdi, muo, mdi, muo) is semidet),
array_uo, mdi, muo, mdi, muo) is semidet.
:- mode generate_foldl2(in, in(pred(in, out, di, uo, di, uo) is semidet),
array_uo, di, uo, di, uo) is semidet.
%--------------------------------------------------%
%
% Reading array elements.
%
% lookup(Array, I) returns the element at index I in Array.
% It throws an exception if the index is out of bounds.
%
:- func lookup(array(T), int) = T.
%:- mode lookup(array_ui, in) = out is det.
:- mode lookup(in, in) = out is det.
:- pred lookup(array(T), int, T).
%:- mode lookup(array_ui, in, out) is det.
:- mode lookup(in, in, out) is det.
% semidet_lookup(Array, I) returns the element at index I in Array.
% It fails if the index is out of bounds.
%
:- pred semidet_lookup(array(T), int, T).
%:- mode semidet_lookup(array_ui, in, out) is semidet.
:- mode semidet_lookup(in, in, out) is semidet.
% unsafe_lookup(Array, I) returns the element at index I in Array.
% Its behavior is undefined if the index is out of bounds.
%
:- pred unsafe_lookup(array(T), int, T).
%:- mode unsafe_lookup(array_ui, in, out) is det.
:- mode unsafe_lookup(in, in, out) is det.
% Array ^ elem(Index) = lookup(Array, Index):
%
% Field selection for arrays.
%
:- func elem(int, array(T)) = T.
%:- mode elem(in, array_ui) = out is det.
:- mode elem(in, in) = out is det.
% As above, but omit the bounds check.
%
:- func unsafe_elem(int, array(T)) = T.
%:- mode unsafe_elem(in, array_ui) = out is det.
:- mode unsafe_elem(in, in) = out is det.
% Returns every element of the array, one by one.
%
:- pred member(array(T)::in, T::out) is nondet.
%--------------------------------------------------%
%
% Writing array elements.
%
% set(Array0, I, Val) = Array:
% set(I, Val, Array0, Array):
%
% Destructively updates the element at index I of Array0 to Val,
% and returns the result as Array.
% It throws an exception if the index is out of bounds.
%
:- func set(array(T)::array_di, int::in, T::in) = (array(T)::array_uo) is det.
:- pred set(int::in, T::in, array(T)::array_di, array(T)::array_uo) is det.
% semidet_set(I, Val, Array0, Array):
%
% Destructively updates the element at index I of Array0 to Val,
% and returns the result as Array.
% It fails if the index is out of bounds.
%
:- pred semidet_set(int::in, T::in, array(T)::array_di, array(T)::array_uo)
is semidet.
% unsafe_set(I, Val, Array0, Array):
%
% Destructively updates the element at index I of Array0 to Val,
% and returns the result as Array.
% Its behavior is undefined if the index is out of bounds.
%
:- pred unsafe_set(int::in, T::in, array(T)::array_di, array(T)::array_uo)
is det.
% slow_set(Array0, I, Val) = Array:
% slow_set(I, Val, Array0, Array):
%
% Returns a copy of Array0 in which all the elements are the same
% as in Array0, except that the element at index I is set to Val.
% It throws an exception if the index is out of bounds.
%
:- func slow_set(array(T), int, T) = array(T).
%:- mode slow_set(array_ui, in, in) = array_uo is det.
:- mode slow_set(in, in, in) = array_uo is det.
:- pred slow_set(int, T, array(T), array(T)).
%:- mode slow_set(in, in, array_ui, array_uo) is det.
:- mode slow_set(in, in, in, array_uo) is det.
% semidet_slow_set(I, Val, Array0, Array):
%
% Returns a copy of Array0 in which all the elements are the same
% as in Array0, except that the element at index I is set to Val.
% It fails if the index is out of bounds.
%
:- pred semidet_slow_set(int, T, array(T), array(T)).
%:- mode semidet_slow_set(in, in, array_ui, array_uo) is semidet.
:- mode semidet_slow_set(in, in, in, array_uo) is semidet.
% (Array ^ elem(Index) := Value) = set(Array, Index, Value):
%
% Field update for arrays.
%
:- func 'elem :='(int, array(T), T) = array(T).
:- mode 'elem :='(in, array_di, in) = array_uo is det.
% As above, but omit the bounds check.
%
:- func 'unsafe_elem :='(int, array(T), T) = array(T).
:- mode 'unsafe_elem :='(in, array_di, in) = array_uo is det.
% swap(I, J, !Array):
%
% Swap the value stored at index I with the value stored at index J.
% Throws an exception if either of I or J is out of bounds.
%
:- pred swap(int::in, int::in, array(T)::array_di, array(T)::array_uo)
is det.
% As above, but omit the bounds checks.
%
:- pred unsafe_swap(int::in, int::in, array(T)::array_di, array(T)::array_uo)
is det.
%--------------------------------------------------%
%
% Accessing the array's bounds.
%
% min returns the lower bound of the array.
% Note: in this implementation, the lower bound is always zero.
%
:- func min(array(_T)) = int.
%:- mode min(array_ui) = out is det.
:- mode min(in) = out is det.
:- pred min(array(_T), int).
%:- mode min(array_ui, out) is det.
:- mode min(in, out) is det.
% max returns the upper bound of the array.
% Returns lower bound - 1 for an empty array
% (always -1 in this implementation).
%
:- func max(array(_T)) = int.
%:- mode max(array_ui) = out is det.
:- mode max(in) = out is det.
:- pred max(array(_T), int).
%:- mode max(array_ui, out) is det.
:- mode max(in, out) is det.
%--------------------------------------------------%
% semidet_least_index returns the lower bound of the array,
% or fails if the array is empty.
%
:- func semidet_least_index(array(T)) = int.
%:- mode semidet_least_index(array_ui) = out is semidet.
:- mode semidet_least_index(in) = out is semidet.
:- pred semidet_least_index(array(T), int).
%:- mode semidet_least_index(array_ui, out) is semidet.
:- mode semidet_least_index(in, out) is semidet.
% det_least_index returns the lower bound of the array.
% Throws an exception if the array is empty.
%
:- func det_least_index(array(T)) = int.
%:- mode det_least_index(array_ui) = out is det.
:- mode det_least_index(in) = out is det.
% semidet_greatest_index returns the upper bound of the array,
% or fails if the array is empty.
%
:- func semidet_greatest_index(array(T)) = int.
%:- mode semidet_greatest_index(array_ui) = out is semidet.
:- mode semidet_greatest_index(in) = out is semidet.
:- pred semidet_greatest_index(array(T), int).
%:- mode semidet_greatest_index(array_ui, out) is semidet.
:- mode semidet_greatest_index(in, out) is semidet.
% det_greatest_index returns the upper bound of the array.
% Throws an exception if the array is empty.
%
:- func det_greatest_index(array(T)) = int.
%:- mode det_greatest_index(array_ui) = out is det.
:- mode det_greatest_index(in) = out is det.
%--------------------------------------------------%
% bounds(Array, Min, Max) returns the lower and upper bounds of an array.
% The upper bound will be lower bound - 1 for an empty array.
% Note: in this implementation, the lower bound is always zero.
%
:- pred bounds(array(_T), int, int).
%:- mode bounds(array_ui, out, out) is det.
:- mode bounds(in, out, out) is det.
% size returns the length of the array,
% i.e. upper bound - lower bound + 1.
%
:- func size(array(_T)) = int.
%:- mode size(array_ui) = out is det.
:- mode size(in) = out is det.
:- pred size(array(_T), int).
%:- mode size(array_ui, out) is det.
:- mode size(in, out) is det.
%--------------------------------------------------%
% is_empty(Array):
%
% True iff Array is an array of size zero.
%
:- pred is_empty(array(_T)).
%:- mode is_empty(array_ui) is semidet.
:- mode is_empty(in) is semidet.
% Check whether the given index is in the bounds of the given array.
%
:- pred in_bounds(array(_T), int).
%:- mode in_bounds(array_ui, in) is semidet.
:- mode in_bounds(in, in) is semidet.
%--------------------------------------------------%
%
% Copying arrays.
%
% copy(Array0) = Array:
% copy(Array0, Array):
%
% Make a new unique copy of an array.
%
:- pred copy(array(T), array(T)).
%:- mode copy(array_ui, array_uo) is det.
:- mode copy(in, array_uo) is det.
:- func copy(array(T)) = array(T).
%:- mode copy(array_ui) = array_uo is det.
:- mode copy(in) = array_uo is det.
% append(A, B) = C:
%
% Make C a concatenation of the arrays A and B.
%
:- func append(array(T)::in, array(T)::in) = (array(T)::array_uo) is det.
%--------------------------------------------------%
%
% Resizing arrays.
%
% resize(Array0, Size, Init) = Array:
% resize(Size, Init, Array0, Array):
%
% Expand or shrink the array to make it fit the new size Size.
% Any new entries are filled with Init. Throws an exception if
% Size < 0.
%
:- func resize(array(T)::array_di, int::in, T::in) = (array(T)::array_uo)
is det.
:- pred resize(int::in, T::in, array(T)::array_di, array(T)::array_uo)
is det.
% shrink(Array0, Size) = Array:
% shrink(Size, Array0, Array):
%
% Shrink the array to make it fit the new size Size.
% Throws an exception if Size is larger than the size of Array0,
% or if Size < 0.
%
:- func shrink(array(T)::array_di, int::in) = (array(T)::array_uo) is det.
:- pred shrink(int::in, array(T)::array_di, array(T)::array_uo) is det.
%--------------------------------------------------%
%
% Filling arrays.
%
% fill(Val, Array0, Array):
%
% Set every element of the array to Val.
%
:- pred fill(T::in, array(T)::array_di, array(T)::array_uo) is det.
% fill_range(Val, Lo, Hi, !Array):
%
% Set every element of the array with index in the range Lo..Hi
% (inclusive) to Val.
% Throws a software_error/1 exception if Lo > Hi.
% Throws an index_out_of_bounds/0 exception if Lo or Hi is out of bounds.
%
:- pred fill_range(T::in, int::in, int::in,
array(T)::array_di, array(T)::array_uo) is det.
%--------------------------------------------------%
%
% Conversions between arrays and lists.
%
% from_list(List) = Array):
%
% Constructs an array from the given list. The array will contain
% the same elements in the same order as the list.
%
:- func from_list(list(T)::in) = (array(T)::array_uo) is det.
:- pred from_list(list(T)::in, array(T)::array_uo) is det.
% array(List) = Array:
%
% A synonym for from_list.
%
% The syntax `array([...])' is used to represent arrays
% for io.read, io.write, term_to_type, and type_to_term.
%
:- func array(list(T)::in) = (array(T)::array_uo) is det.
% from_reverse_list(List) = Array):
%
% Constructs an array from the given list. The array will contain
% the same elements as the list, but in the reverse order.
%
:- func from_reverse_list(list(T)::in) = (array(T)::array_uo) is det.
:- pred from_reverse_list(list(T)::in, array(T)::array_uo) is det.
%--------------------------------------------------%
% to_list(Array) = List:
% to_list(Array, List):
%
% Return a list containing the elements of the array, in their order
% in the array.
%
:- func to_list(array(T)) = list(T).
%:- mode to_list(array_ui) = out is det.
:- mode to_list(in) = out is det.
:- pred to_list(array(T), list(T)).
%:- mode to_list(array_ui, out) is det.
:- mode to_list(in, out) is det.
% fetch_items(Array, Lo, Hi) = List:
% fetch_items(Array, Lo, Hi, List):
%
% Returns a list containing the items in the array with index in the range
% Lo..Hi (both inclusive) in their order in the array.
% Returns an empty list if Hi < Lo.
% Throws an index_out_of_bounds/0 exception if either Lo or Hi
% is out of bounds, *and* Hi >= Lo.
%
% If Hi < Lo, we do not generate an exception even if either or both
% are out of bounds, for two reasons. First, there is no need; if Hi < Lo,
% we can return the empty list without accessing any element of the array.
% Second, without this rule, some programming techniques for accessing
% consecutive contiguous regions of an array would require explicit
% bound checks in the *caller* of fetch_items, which would duplicate
% the checks inside fetch_items itself.
%
:- func fetch_items(array(T), int, int) = list(T).
%:- mode fetch_items(array_ui, in, in) = out is det.
:- mode fetch_items(in, in, in) = out is det.
:- pred fetch_items(array(T), int, int, list(T)).
%:- mode fetch_items(array_ui, in, in, out) is det.
:- mode fetch_items(in, in, in, out) is det.
%--------------------------------------------------%
%
% Sorting arrays.
%
% sort(Array) returns a version of Array sorted into ascending order.
%
% This sort is not stable. That is, elements that compare/3 decides are
% equal will appear together in the sorted array, but not necessarily
% in the same order in which they occurred in the input array. This is
% primarily only an issue with types with user-defined equivalence for
% which `equivalent' objects are otherwise distinguishable.
%
:- func sort(array(T)::array_di) = (array(T)::array_uo) is det.
%--------------------------------------------------%
%
% Searching arrays.
%
% binary_search(A, X, I) does a binary search for the element X
% in the array A. If there is an element with that value in the array,
% it returns its index I; otherwise, it fails.
%
% The array A must be sorted into ascending order with respect to the
% the builtin Mercury order on terms for binary_search/3, and with respect
% to the supplied comparison predicate for binary_search/4.
%
% The array may contain duplicates. If it does, and a search looks for
% a duplicated value, the search will return the index of one of the
% copies, but it is not specified *which* copy's index it will return.
%
:- pred binary_search(array(T)::array_ui,
T::in, int::out) is semidet.
:- pred binary_search(comparison_func(T)::in, array(T)::array_ui,
T::in, int::out) is semidet.
% approx_binary_search(A, X, I) does a binary search for the element X
% in the array A. If there is an element with that value in the array,
% it returns its index I. If there is no element with that value in the
% array, it returns an index whose slot contains the highest value in the
% array that is less than X, as measured by the builtin Mercury order
% on terms for approx_binary_search/3, and as measured by the supplied
% ordering for approx_binary_search/4. It will fail only if there is
% no value smaller than X in the array.
%
% The array A must be sorted into ascending order with respect to the
% the builtin Mercury order on terms for approx_binary_search/3, and
% with respect to supplied comparison predicate for approx_binary_search/4.
%
% The array may contain duplicates. If it does, and if either the
% searched-for value or (if that does not exist) the highest value
% smaller than the searched-for value is duplicated, the search will return
% the index of one of the copies, but it is not specified *which* copy's
% index it will return.
%
:- pred approx_binary_search(array(T)::array_ui,
T::in, int::out) is semidet.
:- pred approx_binary_search(comparison_func(T)::in, array(T)::array_ui,
T::in, int::out) is semidet.
%--------------------------------------------------%
%
% Tests on array elements.
%
% all_true(Pred, Array):
%
% True iff Pred is true for every element of Array.
%
:- pred all_true(pred(T), array(T)).
%:- mode all_true(in(pred(in) is semidet), array_ui) is semidet.
:- mode all_true(in(pred(in) is semidet), in) is semidet.
% all_false(Pred, Array):
%
% True iff Pred is false for every element of Array.
%
:- pred all_false(pred(T), array(T)).
%:- mode all_false(in(pred(in) is semidet), array_ui) is semidet.
:- mode all_false(in(pred(in) is semidet), in) is semidet.
%--------------------------------------------------%
%
% Maps over arrays.
%
% map(Closure, OldArray, NewArray) applies Closure to
% each of the elements of OldArray to create NewArray.
%
:- func map(func(T1) = T2, array(T1)) = array(T2).
%:- mode map(in(func(in) = out is det), array_ui) = array_uo is det.
:- mode map(in(func(in) = out is det), in) = array_uo is det.
:- pred map(pred(T1, T2), array(T1), array(T2)).
%:- mode map(in(pred(in, out) is det), array_ui, array_uo) is det.
:- mode map(in(pred(in, out) is det), in, array_uo) is det.
%--------------------------------------------------%
%
% Folds over arrays.
%
% foldl(Fn, Array, X) is equivalent to
% list.foldl(Fn, to_list(Array), X)
% but more efficient.
%
:- func foldl(func(T1, T2) = T2, array(T1), T2) = T2.
%:- mode foldl(func(in, in) = out is det, array_ui, in) = out is det.
:- mode foldl(in(func(in, in) = out is det), in, in) = out is det.
%:- mode foldl(func(in, di) = uo is det, array_ui, di) = uo is det.
:- mode foldl(in(func(in, di) = uo is det), in, di) = uo is det.
% foldl(Pr, Array, !X) is equivalent to
% list.foldl(Pr, to_list(Array), !X)
% but more efficient.
%
:- pred foldl(pred(T1, T2, T2), array(T1), T2, T2).
:- 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.
% As above, but with two accumulators.
%
:- pred foldl2(pred(T1, T2, T2, T3, T3), array(T1), T2, T2, T3, T3).
:- mode foldl2(in(pred(in, in, out, in, out) is det), in, in, out, in, out)
is det.
:- mode foldl2(in(pred(in, in, out, mdi, muo) is det), in, in, out, mdi, muo)
is det.
:- mode foldl2(in(pred(in, in, out, di, uo) is det), in, in, out, di, uo)
is det.
:- mode foldl2(in(pred(in, in, out, in, out) is semidet), in,
in, out, in, out) is semidet.
:- mode foldl2(in(pred(in, in, out, mdi, muo) is semidet), in,
in, out, mdi, muo) is semidet.
:- mode foldl2(in(pred(in, in, out, di, uo) is semidet), in,
in, out, di, uo) is semidet.
% As above, but with three accumulators.
%
:- pred foldl3(pred(T1, T2, T2, T3, T3, T4, T4), array(T1),
T2, T2, T3, T3, T4, T4).
:- mode foldl3(in(pred(in, in, out, in, out, in, out) is det),
in, in, out, in, out, in, out) is det.
:- mode foldl3(in(pred(in, in, out, in, out, mdi, muo) is det),
in, in, out, in, out, mdi, muo) is det.
:- mode foldl3(in(pred(in, in, out, in, out, di, uo) is det),
in, in, out, in, out, di, uo) is det.
:- mode foldl3(in(pred(in, in, out, in, out, in, out) is semidet),
in, in, out, in, out, in, out) is semidet.
:- mode foldl3(in(pred(in, in, out, in, out, mdi, muo) is semidet),
in, in, out, in, out, mdi, muo) is semidet.
:- mode foldl3(in(pred(in, in, out, in, out, di, uo) is semidet),
in, in, out, in, out, di, uo) is semidet.
% As above, but with four accumulators.
%
:- pred foldl4(pred(T1, T2, T2, T3, T3, T4, T4, T5, T5), array(T1),
T2, T2, T3, T3, T4, T4, T5, T5).
:- mode foldl4(in(pred(in, in, out, in, out, in, out, in, out) is det),
in, in, out, in, out, in, out, in, out) is det.
:- mode foldl4(in(pred(in, in, out, in, out, in, out, mdi, muo) is det),
in, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl4(in(pred(in, in, out, in, out, in, out, di, uo) is det),
in, in, out, in, out, in, out, di, uo) is det.
:- mode foldl4(in(pred(in, in, out, in, out, in, out, in, out) is semidet),
in, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl4(in(pred(in, in, out, in, out, in, out, mdi, muo) is semidet),
in, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl4(in(pred(in, in, out, in, out, in, out, di, uo) is semidet),
in, in, out, in, out, in, out, di, uo) is semidet.
% As above, but with five accumulators.
%
:- pred foldl5(pred(T1, T2, T2, T3, T3, T4, T4, T5, T5, T6, T6),
array(T1), T2, T2, T3, T3, T4, T4, T5, T5, T6, T6).
:- mode foldl5(
in(pred(in, in, out, in, out, in, out, in, out, in, out) is det),
in, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldl5(
in(pred(in, in, out, in, out, in, out, in, out, mdi, muo) is det),
in, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl5(
in(pred(in, in, out, in, out, in, out, in, out, di, uo) is det),
in, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldl5(
in(pred(in, in, out, in, out, in, out, in, out, in, out) is semidet),
in, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl5(
in(pred(in, in, out, in, out, in, out, in, out, mdi, muo) is semidet),
in, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl5(
in(pred(in, in, out, in, out, in, out, in, out, di, uo) is semidet),
in, in, out, in, out, in, out, in, out, di, uo) is semidet.
%--------------------------------------------------%
% foldr(Fn, Array, X) is equivalent to
% list.foldr(Fn, to_list(Array), X)
% but more efficient.
%
:- func foldr(func(T1, T2) = T2, array(T1), T2) = T2.
%:- mode foldr(func(in, in) = out is det, array_ui, in) = out is det.
:- mode foldr(in(func(in, in) = out is det), in, in) = out is det.
%:- mode foldr(func(in, di) = uo is det, array_ui, di) = uo is det.
:- mode foldr(in(func(in, di) = uo is det), in, di) = uo is det.
% foldr(P, Array, !Acc) is equivalent to
% list.foldr(P, to_list(Array), !Acc)
% but more efficient.
%
:- pred foldr(pred(T1, T2, T2), array(T1), T2, T2).
:- 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.
% As above, but with two accumulators.
%
:- pred foldr2(pred(T1, T2, T2, T3, T3), array(T1), T2, T2, T3, T3).
:- mode foldr2(in(pred(in, in, out, in, out) is det), in, in, out, in, out)
is det.
:- mode foldr2(in(pred(in, in, out, mdi, muo) is det), in, in, out, mdi, muo)
is det.
:- mode foldr2(in(pred(in, in, out, di, uo) is det), in, in, out, di, uo)
is det.
:- mode foldr2(in(pred(in, in, out, in, out) is semidet), in,
in, out, in, out) is semidet.
:- mode foldr2(in(pred(in, in, out, mdi, muo) is semidet), in,
in, out, mdi, muo) is semidet.
:- mode foldr2(in(pred(in, in, out, di, uo) is semidet), in,
in, out, di, uo) is semidet.
% As above, but with three accumulators.
%
:- pred foldr3(pred(T1, T2, T2, T3, T3, T4, T4), array(T1),
T2, T2, T3, T3, T4, T4).
:- mode foldr3(in(pred(in, in, out, in, out, in, out) is det), in,
in, out, in, out, in, out) is det.
:- mode foldr3(in(pred(in, in, out, in, out, mdi, muo) is det), in,
in, out, in, out, mdi, muo) is det.
:- mode foldr3(in(pred(in, in, out, in, out, di, uo) is det), in,
in, out, in, out, di, uo) is det.
:- mode foldr3(in(pred(in, in, out, in, out, in, out) is semidet), in,
in, out, in, out, in, out) is semidet.
:- mode foldr3(in(pred(in, in, out, in, out, mdi, muo) is semidet), in,
in, out, in, out, mdi, muo) is semidet.
:- mode foldr3(in(pred(in, in, out, in, out, di, uo) is semidet), in,
in, out, in, out, di, uo) is semidet.
% As above, but with four accumulators.
%
:- pred foldr4(pred(T1, T2, T2, T3, T3, T4, T4, T5, T5), array(T1),
T2, T2, T3, T3, T4, T4, T5, T5).
:- mode foldr4(in(pred(in, in, out, in, out, in, out, in, out) is det),
in, in, out, in, out, in, out, in, out) is det.
:- mode foldr4(in(pred(in, in, out, in, out, in, out, mdi, muo) is det),
in, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldr4(in(pred(in, in, out, in, out, in, out, di, uo) is det),
in, in, out, in, out, in, out, di, uo) is det.
:- mode foldr4(in(pred(in, in, out, in, out, in, out, in, out) is semidet),
in, in, out, in, out, in, out, in, out) is semidet.
:- mode foldr4(in(pred(in, in, out, in, out, in, out, mdi, muo) is semidet),
in, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldr4(in(pred(in, in, out, in, out, in, out, di, uo) is semidet),
in, in, out, in, out, in, out, di, uo) is semidet.
% As above, but with five accumulators.
%
:- pred foldr5(pred(T1, T2, T2, T3, T3, T4, T4, T5, T5, T6, T6),
array(T1), T2, T2, T3, T3, T4, T4, T5, T5, T6, T6).
:- mode foldr5(
in(pred(in, in, out, in, out, in, out, in, out, in, out) is det),
in, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldr5(
in(pred(in, in, out, in, out, in, out, in, out, mdi, muo) is det),
in, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldr5(
in(pred(in, in, out, in, out, in, out, in, out, di, uo) is det),
in, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldr5(
in(pred(in, in, out, in, out, in, out, in, out, in, out) is semidet),
in, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldr5(
in(pred(in, in, out, in, out, in, out, in, out, mdi, muo) is semidet),
in, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldr5(
in(pred(in, in, out, in, out, in, out, in, out, di, uo) is semidet),
in, in, out, in, out, in, out, in, out, di, uo) is semidet.
%--------------------------------------------------%
% foldl_corresponding(P, A, B, !Acc):
%
% Does the same job as foldl, but works on two arrays in parallel.
% Throws an exception if the array arguments differ in size.
%
:- pred foldl_corresponding(pred(T1, T2, T3, T3), array(T1), array(T2),
T3, T3).
:- mode foldl_corresponding(in(pred(in, in, in, out) is det), in, in,
in, out) is det.
:- mode foldl_corresponding(in(pred(in, in, mdi, muo) is det), in, in,
mdi, muo) is det.
:- mode foldl_corresponding(in(pred(in, in, di, uo) is det), in, in,
di, uo) is det.
:- mode foldl_corresponding(in(pred(in, in, in, out) is semidet), in, in,
in, out) is semidet.
:- mode foldl_corresponding(in(pred(in, in, mdi, muo) is semidet), in, in,
mdi, muo) is semidet.
:- mode foldl_corresponding(in(pred(in, in, di, uo) is semidet), in, in,
di, uo) is semidet.
% As above, but with two accumulators.
%
:- pred foldl2_corresponding(pred(T1, T2, T3, T3, T4, T4),
array(T1), array(T2), T3, T3, T4, T4).
:- mode foldl2_corresponding(in(pred(in, in, in, out, in, out) is det),
in, in, in, out, in, out) is det.
:- mode foldl2_corresponding(in(pred(in, in, in, out, mdi, muo) is det),
in, in, in, out, mdi, muo) is det.
:- mode foldl2_corresponding(in(pred(in, in, in, out, di, uo) is det),
in, in, in, out, di, uo) is det.
:- mode foldl2_corresponding(in(pred(in, in, in, out, in, out) is semidet),
in, in, in, out, in, out) is semidet.
:- mode foldl2_corresponding(in(pred(in, in, in, out, mdi, muo) is semidet),
in, in, in, out, mdi, muo) is semidet.
:- mode foldl2_corresponding(in(pred(in, in, in, out, di, uo) is semidet),
in, in, in, out, di, uo) is semidet.
%--------------------------------------------------%
% map_foldl(P, A, B, !Acc):
% Invoke P(Aelt, Belt, !Acc) on each element of the A array,
% and construct array B from the resulting values of Belt.
%
:- pred map_foldl(pred(T1, T2, T3, T3), array(T1), array(T2), T3, T3).
:- mode map_foldl(in(pred(in, out, in, out) is det),
in, array_uo, in, out) is det.
:- mode map_foldl(in(pred(in, out, mdi, muo) is det),
in, array_uo, mdi, muo) is det.
:- mode map_foldl(in(pred(in, out, di, uo) is det),
in, array_uo, di, uo) is det.
:- mode map_foldl(in(pred(in, out, in, out) is semidet),
in, array_uo, in, out) is semidet.
%--------------------------------------------------%
% map_corresponding_foldl(P, A, B, C, !Acc):
%
% Given two arrays A and B, invoke P(Aelt, Belt, Celt, !Acc) on
% each corresponding pair of elements Aelt and Belt. Build up the array C
% from the result Celt values. Return C and the final value of the
% accumulator.
%
% Throws an exception if A and B differ in size.
%
:- pred map_corresponding_foldl(pred(T1, T2, T3, T4, T4),
array(T1), array(T2), array(T3), T4, T4).
:- mode map_corresponding_foldl(
in(pred(in, in, out, in, out) is det),
in, in, array_uo, in, out) is det.
:- mode map_corresponding_foldl(
in(pred(in, in, out, mdi, muo) is det),
in, in, array_uo, mdi, muo) is det.
:- mode map_corresponding_foldl(
in(pred(in, in, out, di, uo) is det),
in, in, array_uo, di, uo) is det.
:- mode map_corresponding_foldl(
in(pred(in, in, out, in, out) is semidet),
in, in, array_uo, in, out) is semidet.
:- mode map_corresponding_foldl(
in(pred(in, in, out, mdi, muo) is semidet),
in, in, array_uo, mdi, muo) is semidet.
:- mode map_corresponding_foldl(
in(pred(in, in, out, di, uo) is semidet),
in, in, array_uo, di, uo) is semidet.
%--------------------------------------------------%
%
% Prettyprinting arrays.
%
% Convert an array to a pretty_printer.doc for formatting.
%
:- func array_to_doc(array(T)::array_ui) = (pretty_printer.doc::out) is det.
:- pragma obsolete(func(array_to_doc/1), [pretty_printer.array_to_doc/1]).
%--------------------------------------------------%
%
% Comparing two arrays.
%
:- func array_compare(array(T)::in, array(T)::in) = (comparison_result::uo)
is det.
%--------------------------------------------------%
%--------------------------------------------------%