%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1993-2012 The University of Melbourne.
% Copyright (C) 2013-2024 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: list.m.
% Authors: fjh, conway, trd, zs, philip, warwick, ...
% Stability: medium to high.
%
% This module defines the list type, and various utility predicates that
% operate on lists.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module list.
:- interface.

:- import_module pretty_printer.

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

    % The definition of the type list(T).
    % A list is either an empty list, denoted `[]',
    % or an element Head of type T followed by a tail Tail
    % of type list(T), denoted `[Head | Tail]'.
    %
:- type list(T)
    --->    []
    ;       [T | list(T)].

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

    % These instantiation states and modes can be used for instantiation
    % state subtyping.
    %
    % They could also be used for partial instantiation but partial
    % instantiation does not work completely, for information see the
    % LIMITATIONS.md file distributed with Mercury.
    %
:- inst list_skel(I) for list/1
    --->    []
    ;       [I | list_skel(I)].
:- inst list(I) == list_skel(I).

:- inst empty_list for list/1
    --->    [].
:- inst non_empty_list for list/1
    --->    [ground | ground].

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

:- pred is_empty(list(T)::in) is semidet.

:- pred is_non_empty(list(T)::in) is semidet.
:- pred is_not_empty(list(T)::in) is semidet.

:- pred is_singleton(list(T)::in, T::out) is semidet.

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

    % head(List) returns the head of List (i.e. its first element),
    % failing if List is empty.
    %
:- func head(list(T)) = T is semidet.
:- pred head(list(T)::in, T::out) is semidet.

    % det_head(List) returns the first element of List,
    % calling error/1 if List is empty.
    %
:- func det_head(list(T)) = T.
:- pred det_head(list(T)::in, T::out) is det.

    % tail(List) returns the tail of List (i.e. all its elements
    % except the first), failing if List is empty.
    %
:- func tail(list(T)) = list(T) is semidet.
:- pred tail(list(T)::in, list(T)::out) is semidet.

    % det_tail(List) returns the tail of List,
    % calling error/1 if List is empty.
    %
:- func det_tail(list(T)) = list(T).
:- pred det_tail(list(T)::in, list(T)::out) is det.

    % det_head_tail(List, Head, Tail) returns the head and the tail of List,
    % calling error/1 if List is empty.
    %
:- pred det_head_tail(list(T)::in, T::out, list(T)::out) is det.

    % cons(X, Y) = Z <=> Z = [X | Y].
    %
:- func cons(T, list(T)) = list(T).
:- pred cons(T::in, list(T)::in, list(T)::out) is det.

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

    % Standard append predicate:
    % append(Start, End, List) is true iff
    % List is the result of concatenating Start and End.
    %
:- pred append(list(T), list(T), list(T)).
:- mode append(di, di, uo) is det.
:- mode append(in, in, out) is det.
:- mode append(in, in, in) is semidet.    % implied
:- mode append(in, out, in) is semidet.
:- mode append(out, out, in) is multi.
% The following mode is semidet in the sense that it does not
% succeed more than once - but operationally, it does create a choice-point,
% which means both that it is inefficient, and that the compiler can't deduce
% that it is semidet. Use remove_suffix instead.
% :- mode append(out, in, in) is semidet.

:- func append(list(T), list(T)) = list(T).

    % L1 ++ L2 = L :- append(L1, L2, L).
    %
:- func list(T) ++ list(T) = list(T).

    % remove_suffix(List, Suffix, Prefix):
    %
    % The same as append(Prefix, Suffix, List) except that
    % this is semidet, whereas append(out, in, in) is nondet.
    %
:- pred remove_suffix(list(T)::in, list(T)::in, list(T)::out) is semidet.

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

    % Associativity of append.
:- promise all [A, B, C, ABC]
    (
        ( some [AB] (list.append(A, B, AB), list.append(AB, C, ABC)) )
    <=>
        ( some [BC] (list.append(B, C, BC), list.append(A, BC, ABC)) )
    ).
    % Construction equivalence law.
:- promise all [L, H, T] ( append([H], T, L) <=> L = [H | T] ).

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

    % length(List) = Length:
    % length(List, Length):
    %
    % True iff Length is the length of List, i.e. if List contains
    % Length elements.
    %
:- func length(list(T)) = int.

:- pred length(list(_T), int).
:- mode length(in, out) is det.

    % same_length(ListA, ListB):
    %
    % True iff ListA and ListB have the same length,
    % i.e. iff they both contain the same number of elements.
    %
    % Does not traverse *either* list further than the length
    % of the shorter list.
    %
:- pred same_length(list(T1), list(T2)).
:- mode same_length(in, in) is semidet.

    % As above, but for three lists.
    %
    % Does not traverse *any* of the three lists further than the length
    % of the shortest list.
    %
:- pred same_length3(list(T1)::in, list(T2)::in, list(T3)::in)
    is semidet.

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

    % member(Elem, List):
    %
    % True iff List contains Elem.
    %
:- pred member(T, list(T)).
:- mode member(in, in) is semidet.
:- mode member(out, in) is nondet.

    % member(Elem, List, SubList):
    %
    % True iff List contains Elem, and SubList is a suffix of List
    % beginning with Elem.
    % Same as `SubList = [Elem | _], append(_, SubList, List)'.
    %
:- pred member(T::out, list(T)::in, list(T)::out) is nondet.

    % member_index0(Elem, List, Index):
    %
    % True iff List contains Elem at the zero-based index Index.
    %
:- pred member_index0(T, list(T), int).
:- mode member_index0(in, in, in) is semidet.
:- mode member_index0(in, in, out) is nondet.
:- mode member_index0(out, in, out) is nondet.

    % member_indexes0(Elem, List, Indexes):
    %
    % True iff List contains Elem at the zero-based indexes Indexes.
    % Indexes will be sorted.
    %
:- pred member_indexes0(T::in, list(T)::in, list(int)::out) is det.

    % contains(List, Elem):
    %
    % Equivalent to member(Elem, List).
    %
    % Sometimes you need the arguments in this order, because you want to
    % construct a closure with only the list.
    %
:- pred contains(list(T)::in, T::in) is semidet.

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

    % index*(List, Position, Elem):
    %
    % These predicates select an element in a list from its position.
    % The `index0' preds consider the first element to be element
    % number zero, whereas the `index1' preds consider the first element
    % to be element number one. The `det_' preds call error/1 if the index
    % is out of range, whereas the semidet preds fail if the index is out of
    % range.
    %
:- pred index0(list(T)::in, int::in, T::out) is semidet.
:- pred index1(list(T)::in, int::in, T::out) is semidet.

:- func det_index0(list(T), int) = T.
:- pred det_index0(list(T)::in, int::in, T::out) is det.
:- func det_index1(list(T), int) = T.
:- pred det_index1(list(T)::in, int::in, T::out) is det.

    % nth_member_search(List, Elem, Position):
    %
    % Elem is the Position'th member of List.
    % (Position numbers start from 1.)
    %
:- pred nth_member_search(list(T)::in, T::in, int::out) is semidet.

    % nth_member_lookup(List, Elem, Position):
    %
    % A deterministic version of nth_member_search, which throws an exception
    % instead of failing if the element is not found in the list.
    %
:- pred nth_member_lookup(list(T)::in, T::in, int::out) is det.

    % index*_of_first_occurrence(List, Elem, Position):
    %
    % Computes the least value of Position such that
    % list_index*(List, Position, Elem).
    %
    % The `det_' funcs call error/1 if Elem is not a member of List.
    %
:- pred index0_of_first_occurrence(list(T)::in, T::in, int::out) is semidet.
:- pred index1_of_first_occurrence(list(T)::in, T::in, int::out) is semidet.
:- func det_index0_of_first_occurrence(list(T), T) = int.
:- func det_index1_of_first_occurrence(list(T), T) = int.

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

    % reverse(List, Reverse):
    %
    % Reverse is a list containing the same elements as List
    % but in reverse order.
    %
:- pred reverse(list(T), list(T)).
:- mode reverse(in, out) is det.
:- mode reverse(out, in) is det.

:- func reverse(list(T)) = list(T).

    % reverse_prepend(Xs, Ys, Zs):
    %
    % Same as `Zs = list.reverse(Xs) ++ Ys' but more efficient.
    %
:- pred reverse_prepend(list(T)::in, list(T)::in, list(T)::out) is det.
:- func reverse_prepend(list(T), list(T)) = list(T).

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

    % insert(Elem, List0, List):
    %
    % List is the result of inserting Elem somewhere in List0.
    % Same as `delete(List, Elem, List0)'.
    %
:- pred insert(T, list(T), list(T)).
:- mode insert(in, in, in) is semidet.
:- mode insert(in, out, in) is nondet.
:- mode insert(out, out, in) is nondet.
:- mode insert(in, in, out) is multi.

    % delete(List, Elem, Remainder):
    %
    % True iff Elem occurs in List, and Remainder is the result of
    % deleting one occurrence of Elem from List.
    %
:- pred delete(list(T), T, list(T)).
:- mode delete(in, in, in) is semidet.
:- mode delete(in, in, out) is nondet.
:- mode delete(in, out, out) is nondet.
:- mode delete(out, in, in) is multi.

    % delete_first(List0, Elem, List):
    %
    % True iff Elem occurs in List0
    % and List is List0 with the first occurrence of Elem removed.
    %
:- pred delete_first(list(T)::in, T::in, list(T)::out) is semidet.

    % delete_all(List0, Elem) = List:
    %
    % True iff List is List0 with all occurrences of Elem removed.
    %
:- func delete_all(list(T), T) = list(T).
:- pred delete_all(list(T), T, list(T)).
:- mode delete_all(di, in, uo) is det.
:- mode delete_all(in, in, out) is det.

    % delete_nth(List0, N, List):
    %
    % True iff List0 has an N'th element,
    % and List is List0 with this element deleted.
    %
:- pred delete_nth(list(T)::in, int::in, list(T)::out) is semidet.

    % delete_elems(List0, Elems) = List:
    %
    % True iff List is List0 with all occurrences of all elements of Elems
    % removed.
    %
:- func delete_elems(list(T), list(T)) = list(T).
:- pred delete_elems(list(T)::in, list(T)::in, list(T)::out) is det.

    % sublist(SubList, FullList):
    %
    % True if one can obtain SubList by starting with FullList
    % and deleting some of its elements.
    %
:- pred sublist(list(T)::in, list(T)::in) is semidet.

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

    % replace(List0, D, R, List):
    %
    % True iff List is List0 with an occurrence of D replaced with R.
    %
:- pred replace(list(T), T, T, list(T)).
:- mode replace(in, in, in, in) is semidet.
:- mode replace(in, in, in, out) is nondet.

    % replace_first(List0, D, R, List):
    %
    % True iff List is List0 with the first occurrence of D replaced with R.
    %
:- pred replace_first(list(T)::in, T::in, T::in, list(T)::out) is semidet.

    % replace_all(List0, D, R) = List:
    %
    % True iff List is List0 with all occurrences of D replaced with R.
    %
:- func replace_all(list(T), T, T) = list(T).
:- pred replace_all(list(T)::in, T::in, T::in, list(T)::out) is det.

    % replace_nth(List0, N, R, List):
    %
    % True iff List is List0 with its N'th element replaced with R.
    % Fails if N < 1 or if length of List0 < N.
    % (Position numbers start from 1.)
    %
:- pred replace_nth(list(T)::in, int::in, T::in, list(T)::out) is semidet.

    % det_replace_nth(List0, N, R) = List:
    %
    % True iff List is List0 with its N'th element replaced with R.
    % Throws an exception if N < 1 or if length of List0 < N.
    % (Position numbers start from 1.)
    %
:- func det_replace_nth(list(T), int, T) = list(T).
:- pred det_replace_nth(list(T)::in, int::in, T::in, list(T)::out) is det.

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

    % Lo `..` Hi = [Lo, Lo + 1, ..., Hi] if Lo =< Hi, and [] otherwise.
    %
:- func int `..` int = list(int).

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

    % series(X, OK, Succ) = [X0, X1, ..., Xn]
    %
    % where X0 = X and successive elements Xj, Xk are computed as
    % Xk = Succ(Xj). The series terminates as soon as an element Xi is
    % generated such that OK(Xi) fails; Xi is not included in the output.
    %
:- func series(T::in, pred(T)::in(pred(in) is semidet),
    (func(T) = T)::in(func(in) = out is det)) = (list(T)::out) is det.

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

    % remove_dups(L0) = L:
    %
    % L is the result of deleting the second and subsequent occurrences
    % of every element that occurs twice in L0.
    %
:- func remove_dups(list(T)) = list(T).
:- pred remove_dups(list(T)::in, list(T)::out) is det.

    % remove_adjacent_dups(L0) = L:
    %
    % L is the result of replacing every sequence of duplicate elements in L0
    % with a single such element.
    %
:- func remove_adjacent_dups(list(T)) = list(T).
:- pred remove_adjacent_dups(list(T)::in, list(T)::out) is det.

    % remove_adjacent_dups(P, L0, L):
    %
    % True iff L is the result of replacing every sequence of elements in L0
    % which are equivalent with respect to the ordering, with the first
    % occurrence in L0 of such an element.
    %
:- pred remove_adjacent_dups(comparison_pred(X)::in(comparison_pred),
    list(X)::in, list(X)::out) is det.

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

    % merge(L1, L2) = L:
    %
    % L is the result of merging the elements of L1 and L2, in ascending order.
    % Both L1 and L2 must already be sorted into ascending order.
    %
:- func merge(list(T), list(T)) = list(T).
:- pred merge(list(T)::in, list(T)::in, list(T)::out) is det.

    % merge(Compare, As, Bs) = Sorted:
    %
    % True iff, assuming As and Bs are sorted with respect to the ordering
    % defined by Compare, Sorted is a sorted list containing the elements
    % of As and Bs. For elements which are equivalent in the ordering,
    % if they come from the same list then they appear in the same sequence
    % in Sorted as they do in that list, otherwise the elements from As
    % appear before the elements from Bs.
    %
:- func merge(comparison_func(X), list(X), list(X)) = list(X).
:- pred merge(comparison_pred(X)::in(comparison_pred),
    list(X)::in, list(X)::in, list(X)::out) is det.

    % merge_and_remove_dups(L1, L2) = L:
    %
    % L is the result of merging the elements of L1 and L2, in ascending order,
    % and eliminating any duplicates. L1 and L2 must be sorted and must each
    % not contain any duplicates.
    %
:- func merge_and_remove_dups(list(T), list(T)) = list(T).
:- pred merge_and_remove_dups(list(T)::in, list(T)::in, list(T)::out) is det.

    % merge_and_remove_dups(Compare, As, Bs) = Sorted:
    %
    % True iff, assuming As and Bs are sorted with respect to the ordering
    % defined by Compare and neither contains any duplicates, Sorted is a
    % sorted list containing the elements of As and Bs without any duplicates.
    % If an element from As is duplicated in Bs (that is, they are equivalent
    % in the ordering), then the element from As is the one that appears
    % in Sorted.
    %
:- func merge_and_remove_dups(comparison_func(X), list(X), list(X))
    = list(X).
:- pred merge_and_remove_dups(comparison_pred(X)::in(comparison_pred),
    list(X)::in, list(X)::in, list(X)::out) is det.

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

    % sort(List) = SortedList:
    %
    % Sorts List and returns the result as SortedList.
    %
:- func sort(list(T)) = list(T).
:- pred sort(list(T)::in, list(T)::out) is det.

    % sort_and_remove_dups(List) = SortedList:
    %
    % Sorts List, removes the second and subsequent occurrences of
    % any duplicates, and returns the result as SortedList.
    %
:- func sort_and_remove_dups(list(T)) = list(T).
:- pred sort_and_remove_dups(list(T)::in, list(T)::out) is det.

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

    % sort(Compare, Unsorted) = Sorted:
    %
    % True iff Sorted is a list containing the same elements as Unsorted,
    % where Sorted is sorted with respect to the ordering defined by Compare,
    % and the elements that are equivalent in this ordering appear
    % in the same sequence in Sorted as they do in Unsorted
    % (that is, the sort is stable).
    %
:- func sort(comparison_func(X), list(X)) = list(X).
:- pred sort(comparison_pred(X)::in(comparison_pred), list(X)::in,
    list(X)::out) is det.

    % sort_and_remove_dups(Compare, Unsorted, Sorted):
    %
    % True iff Sorted is a list containing the same elements as Unsorted,
    % where Sorted is sorted with respect to the ordering defined by the
    % predicate term Compare, except that if two elements in Unsorted
    % are equivalent with respect to this ordering only the one which
    % occurs first will be in Sorted.
    %
:- pred sort_and_remove_dups(comparison_pred(X)::in(comparison_pred),
    list(X)::in, list(X)::out) is det.

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

    % split_list(N, List, Start, End):
    %
    % Splits List into a prefix Start of length N, and a remainder End.
    % Fails if N is not in `0 .. length(List)'.
    % See also: take, drop and split_upto.
    %
:- pred split_list(int::in, list(T)::in, list(T)::out, list(T)::out)
    is semidet.

    % det_split_list(N, List, Start, End):
    %
    % A deterministic version of split_list, which throws an exception
    % instead of failing if N is not in 0 .. length(List).
    %
:- pred det_split_list(int::in, list(T)::in, list(T)::out, list(T)::out)
    is det.

    % split_upto(N, List, Start, End):
    %
    % Splits List into a prefix Start of length `min(N, length(List))',
    % and a remainder End. Throws an exception if N < 0.
    % See also: split_list, take, drop.
    %
:- pred split_upto(int::in, list(T)::in, list(T)::out, list(T)::out) is det.

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

    % last(List, Last):
    %
    % True if Last is the last element of List.
    %
:- pred last(list(T)::in, T::out) is semidet.

    % det_last(List, Last):
    %
    % A deterministic version of last, which throws an exception instead of
    % failing if the input list is empty.
    %
:- func det_last(list(T)) = T.
:- pred det_last(list(T)::in, T::out) is det.

    % split_last(List, AllButLast, Last):
    %
    % True if Last is the last element of List and AllButLast is the list
    % of elements before it.
    %
:- pred split_last(list(T)::in, list(T)::out, T::out) is semidet.

    % det_split_last(List, AllButLast, Last):
    %
    % A deterministic version of split_last, which throws an exception
    % instead of failing if the input list is empty.
    %
:- pred det_split_last(list(T)::in, list(T)::out, T::out) is det.

    % intersperse(Sep, List, ListWithSep):
    %
    % Insert Sep between each pair of elements in List, and return
    % the result as ListWithSep.
    %
    % For example, intersperse("and", ["jan", "feb", "mar"], ListWithSep)
    % will bind ListWithSep to ["jan", "and", "feb", "and", "mar"].
    %
:- pred intersperse(T::in, list(T)::in, list(T)::out) is det.

    % intersperse_list(Seps, List, ListWithSeps):
    %
    % Insert Seps between each pair of elements in List, and return
    % the result as ListWithSeps.
    %
    % For example, intersperse_list(["and", "then"], ["jan", "feb", "mar"],
    % ListWithSeps) will bind ListWithSeps to
    % ["jan", "and", "then", "feb", "and", "then", "mar"].
    %
:- pred intersperse_list(list(T)::in, list(T)::in, list(T)::out) is det.

    % intersperse_list_last(NonLastSeps, LastSeps, List, ListWithSeps):
    %
    % Insert NonLastSeps between each pair of elements in List except
    % the last pair, insert LastSeps between the last pair of elements,
    % and return the result as ListWithSeps.
    %
    % For example, intersperse_list_last(["and", "then"], ["and", "finally"],
    % ["jan", "feb", "mar"], ListWithSeps) will bind ListWithSeps to
    % ["jan", "and", "then", "feb", "and", "finally", "mar"].
    %
:- pred intersperse_list_last(list(T)::in, list(T)::in, list(T)::in,
    list(T)::out) is det.

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

    % take(N, List, Start):
    %
    % Start is the first Len elements of List.
    % Fails if N is not in `0 .. length(List)'.
    %
:- pred take(int::in, list(T)::in, list(T)::out) is semidet.

    % det_take(Len, List, Start):
    %
    % As above, but throw an exception instead of failing.
    %
:- pred det_take(int::in, list(T)::in, list(T)::out) is det.

    % take_upto(Len, List) = Start:
    %
    % Start is the first Len elements of List. If List has less than
    % Len elements, return the entire list. Throws an exception if N < 0.
    %
:- func take_upto(int, list(T)) = list(T).
:- pred take_upto(int::in, list(T)::in, list(T)::out) is det.

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

    % drop(N, List, End):
    %
    % End is the remainder of List after removing the first N elements.
    % Fails if N is not in `0 .. length(List)'.
    % See also: split_list.
    %
:- pred drop(int::in, list(T)::in, list(T)::out) is semidet.

    % det_drop(N, List, End):
    %
    % End is the remainder of List after removing the first N elements.
    % Throws an exception if N is not in `0 .. length(List)'.
    % See also: split_list.
    %
:- pred det_drop(int::in, list(T)::in, list(T)::out) is det.

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

    % take_while(Pred, List, Start, End)
    %
    % List = Start ++ End. Start is the longest prefix of List where Pred
    % succeeds for every element in Start. End is the remainder of the list.
    %
:- pred take_while(pred(T)::in(pred(in) is semidet), list(T)::in,
    list(T)::out, list(T)::out) is det.

    % take_while_not(Pred, List, Start, End)
    %
    % List = Start ++ End. Start is the longest prefix of List where Pred
    % fails for every element in Start. End is the remainder of the list.
    %
:- pred take_while_not(pred(T)::in(pred(in) is semidet), list(T)::in,
    list(T)::out, list(T)::out) is det.

    % take_while(Pred, List) = Start :-
    %     take_while(Pred, List, Start, _End)
    %
    % Start is the longest prefix of List where Pred succeeds for every element
    % in Start.
    %
:- func take_while(pred(T)::in(pred(in) is semidet), list(T)::in) =
    (list(T)::out) is det.
:- pred take_while(pred(T)::in(pred(in) is semidet), list(T)::in,
    list(T)::out) is det.

    % take_while(Pred, List) = Start :-
    %     take_while(Pred, List, Start, _End)
    %
    % Start is the longest prefix of List where Pred fails for every element
    % in Start.
    %
:- func take_while_not(pred(T)::in(pred(in) is semidet), list(T)::in) =
    (list(T)::out) is det.
:- pred take_while_not(pred(T)::in(pred(in) is semidet), list(T)::in,
    list(T)::out) is det.

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

    % drop_while(Pred, List) = End :-
    %     take_while(Pred, List, _Start, End).
    %
    % End is the remainder of List after removing all the consecutive
    % elements from the start of List for which Pred succeeds.
    %
:- func drop_while(pred(T)::in(pred(in) is semidet), list(T)::in) =
    (list(T)::out) is det.
:- pred drop_while(pred(T)::in(pred(in) is semidet), list(T)::in,
    list(T)::out) is det.

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

    % duplicate(Count, Elem) = List:
    %
    % True iff List is a list containing Count duplicate copies of Elem.
    %
:- func duplicate(int, T) = list(T).
:- pred duplicate(int::in, T::in, list(T)::out) is det.

    % all_same(List):
    %
    % True if all elements of the list are the same.
    %
:- pred all_same(list(T)::in) is semidet.

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

    % condense(ListOfLists) = List:
    %
    % List is the result of concatenating all the elements of ListOfLists.
    %
:- func condense(list(list(T))) = list(T).
:- pred condense(list(list(T))::in, list(T)::out) is det.

    % chunk(List, ChunkSize) = Chunks:
    %
    % Takes a list List and breaks it into a list of lists Chunks,
    % such that the length of each list in Chunks is at most ChunkSize.
    % (More precisely, the length of each list in Chunks other than the
    % last one is exactly ChunkSize, while the length of the last list in
    % Chunks may vary between one and ChunkSize.)
    %
:- func chunk(list(T), int) = list(list(T)).
:- pred chunk(list(T)::in, int::in, list(list(T))::out) is det.

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

    % zip(ListA, ListB) = List:
    %
    % List is the result of alternating the elements of ListA and ListB,
    % starting with the first element of ListA (followed by the first element
    % of ListB, then the second element of listA, then the second element
    % of ListB, etc.). When there are no more elements remaining in one of
    % the lists, the remainder of the other list is appended.
    %
:- func zip(list(T), list(T)) = list(T).
:- pred zip(list(T)::in, list(T)::in, list(T)::out) is det.

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

    % perm(List0, List):
    %
    % True iff List is a permutation of List0.
    %
:- pred perm(list(T)::in, list(T)::out) is multi.

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

    % list_to_doc(List) = Doc:
    %
    % Convert a list to a pretty_printer.doc for formatting.
    %
:- func list_to_doc(list(T)) = pretty_printer.doc.
:- pragma obsolete(func(list_to_doc/1), [pretty_printer.list_to_doc/1]).

%--------------------------------------------------%
%
% The following group of predicates use higher-order terms to simplify
% various list processing tasks. They implement pretty much standard
% sorts of operations provided by standard libraries for functional languages.
%
%--------------------------------------------------%

    % find_first_match(Pred, List, FirstMatch):
    %
    % Takes a closure with one input argument. It returns the first element X
    % of the list (if any) for which Pred(X) is true.
    %
:- pred find_first_match(pred(X)::in(pred(in) is semidet), list(X)::in,
    X::out) is semidet.

    % any_true(Pred, List):
    %
    % Succeeds iff Pred succeeds for at least one element of List.
    % Same as `not all_false(Pred, List)'.
    %
:- pred any_true(pred(X)::in(pred(in) is semidet), list(X)::in) is semidet.

    % any_false(Pred, List):
    %
    % Succeeds iff Pred fails for at least one element of List.
    % Same as `not all_true(Pred, List)'.
    %
:- pred any_false(pred(X)::in(pred(in) is semidet), list(X)::in) is semidet.

    % all_true(Pred, List):
    %
    % Takes a closure with one input argument.
    % If Pred succeeds for every member of List, all_true succeeds.
    % If Pred fails for any member of List, all_true fails.
    %
:- pred all_true(pred(X)::in(pred(in) is semidet), list(X)::in) is semidet.

    % all_false(Pred, List):
    %
    % Takes a closure with one input argument.
    % If Pred fails for every member of List, all_false succeeds.
    % If Pred succeeds for any member of List, all_false fails.
    %
:- pred all_false(pred(X)::in(pred(in) is semidet), list(X)::in) is semidet.

    % all_true_corresponding(Pred, ListA, ListB):
    %
    % Succeeds if Pred succeeds for every corresponding pair of elements from
    % ListA and ListB. Fails if Pred fails for any pair of corresponding
    % elements.
    %
    % Raises an exception if the list arguments differ in length.
    %
:- pred all_true_corresponding(pred(X, Y)::in(pred(in, in) is semidet),
    list(X)::in, list(Y)::in) is semidet.

    % all_false_corresponding(Pred, ListA, ListB):
    %
    % Succeeds if Pred fails for every corresponding pair of elements from
    % ListA and ListB. Fails if Pred succeeds for any pair of corresponding
    % elements.
    %
    % Raises an exception if the list arguments differ in length.
    %
:- pred all_false_corresponding(pred(X, Y)::in(pred(in, in) is semidet),
    list(X)::in, list(Y)::in) is semidet.

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

    % filter(Pred, List) = TrueList:
    %
    % Takes a closure Pred with one input argument. It calls Pred(X)
    % on each member X of List, and includes X in TrueList iff Pred(X) is true.
    %
:- func filter(pred(X)::in(pred(in) is semidet), list(X)::in)
    = (list(X)::out) is det.
:- pred filter(pred(X)::in(pred(in) is semidet), list(X)::in,
    list(X)::out) is det.

    % filter(Pred, List, TrueList, FalseList):
    %
    % Takes a closure Pred with one input argument. It calls Pred(X)
    % on each member X of List. Includes X in TrueList iff Pred(X) is true,
    % and includes X in FalseList iff Pred(X) is false.
    %
:- pred filter(pred(X)::in(pred(in) is semidet), list(X)::in,
    list(X)::out, list(X)::out) is det.

    % negated_filter(Pred, List) = FalseList:
    %
    % Takes a closure Pred with one input argument. It calls Pred(X)
    % on each member X of List, and includes X in FalseList iff Pred(X)
    % is false.
    %
:- func negated_filter(pred(X)::in(pred(in) is semidet), list(X)::in)
    = (list(X)::out) is det.
:- pred negated_filter(pred(X)::in(pred(in) is semidet), list(X)::in,
    list(X)::out) is det.

    % filter_map(Transformer, List, TrueList):
    %
    % Takes a semidet function Transformer and calls it on each element X
    % of List. If Transformer(X) succeeds, then it includes its return value
    % in TrueList.
    %
:- func filter_map((func(X) = Y)::in((func(in) = out) is semidet),
    list(X)::in) = (list(Y)::out) is det.

    % filter_map(Transformer, List, TrueList):
    %
    % Takes a predicate Transformer with one input and one output argument,
    % and calls it on each element of X of List. If Transformer(X, Y) succeeds,
    % then it includes Y in TrueList.
    %
:- pred filter_map(pred(X, Y)::in(pred(in, out) is semidet),
    list(X)::in, list(Y)::out) is det.

    % filter_map(Transformer, List, TrueList, FalseList):
    %
    % Takes a predicate Transformer with one input and one output argument,
    % and calls it on each element of X of List. If Transformer(X, Y) succeeds,
    % then it includes Y in TrueList; if it fails, then it includes X
    % in FalseList.
    %
:- pred filter_map(pred(X, Y)::in(pred(in, out) is semidet),
    list(X)::in, list(Y)::out, list(X)::out) is det.

    % find_first_map(Transformer, List, FirstTrue):
    %
    % Same as filter_map/3 except that it only returns the first match,
    % so that
    %
    %   find_first_map(Transformer, List, FirstTrue)
    %
    % is equivalent to
    %
    %   filter_map(Transformer, List, [FirstTrue | _])
    %
:- pred find_first_map(pred(X, Y)::in(pred(in, out) is semidet),
    list(X)::in, Y::out) is semidet.

    % find_first_map2(Transformer, List, FirstTrueA, FirstTrueB):
    %
    % Same as find_first_map, except with two outputs.
    %
:- pred find_first_map2(pred(X, A, B)::in(pred(in, out, out) is semidet),
    list(X)::in, A::out, B::out) is semidet.

    % find_first_map3(Transformer, List, FirstTrueA, FirstTrueB, FirstTrueB):
    %
    % Same as find_first_map, except with three outputs.
    %
:- pred find_first_map3(
    pred(X, A, B, C)::in(pred(in, out, out, out) is semidet),
    list(X)::in, A::out, B::out, C::out) is semidet.

    % find_index_of_match(Match, List, Index0, Index):
    %
    % Find the index of the first item in List for which Match is true,
    % where the first element in the list has the index Index0.
    % (Index0 is *not* the number of items to skip at the head of List.)
    %
:- pred find_index_of_match(pred(T)::in(pred(in) is semidet),
    list(T)::in, int::in, int::out) is semidet.

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

    % map(F, L) = M:
    % map(P, L, M):
    %
    % Apply the function F or the predicate P to transform the elements of L
    % into the elements of M.
    %
:- func map(func(X) = Y, list(X)) = list(Y).
:- pred map(pred(X, Y), list(X), 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.

    % map2(P, L, M1, M2):
    %
    % Apply the predicate P to transform the elements of L
    % into the elements of M1 and M2.
    %
:- pred map2(pred(A, B, C), list(A), list(B), list(C)).
:- mode map2(in(pred(in, out, out) is det), in, out, out) is det.
:- mode map2(in(pred(in, out, out) is cc_multi), in, out, out) is cc_multi.
:- mode map2(in(pred(in, out, out) is semidet), in, out, out) is semidet.
:- mode map2(in(pred(in, out, out) is multi), in, out, out) is multi.
:- mode map2(in(pred(in, out, out) is nondet), in, out, out) is nondet.
:- mode map2(in(pred(in, in, in) is semidet), in, in, in) is semidet.

    % map3(T, L, M1, M2, M3) uses the closure T
    % to transform the elements of L into the elements of M1, M2 and M3.
    %
:- pred map3(pred(A, B, C, D), list(A), list(B), list(C), list(D)).
:- mode map3(in(pred(in, out, out, out) is det), in, out, out, out) is det.
:- mode map3(in(pred(in, out, out, out) is cc_multi), in, out, out, out)
    is cc_multi.
:- mode map3(in(pred(in, out, out, out) is semidet), in, out, out, out)
    is semidet.
:- mode map3(in(pred(in, out, out, out) is multi), in, out, out, out)
    is multi.
:- mode map3(in(pred(in, out, out, out) is nondet), in, out, out, out)
    is nondet.
:- mode map3(in(pred(in, in, in, in) is semidet), in, in, in, in) is semidet.

    % map4(T, L, M1, M2, M3, M4) uses the closure T
    % to transform the elements of L into the elements of M1, M2, M3 and M4.
    %
:- pred map4(pred(A, B, C, D, E), list(A), list(B), list(C), list(D),
    list(E)).
:- mode map4(in(pred(in, out, out, out, out) is det), in, out, out, out, out)
    is det.
:- mode map4(in(pred(in, out, out, out, out) is cc_multi), in, out, out, out,
    out) is cc_multi.
:- mode map4(in(pred(in, out, out, out, out) is semidet), in, out, out, out,
    out) is semidet.
:- mode map4(in(pred(in, out, out, out, out) is multi), in, out, out, out,
    out) is multi.
:- mode map4(in(pred(in, out, out, out, out) is nondet), in, out, out, out,
    out) is nondet.
:- mode map4(in(pred(in, in, in, in, in) is semidet), in, in, in, in, in)
    is semidet.

    % map5(T, L, M1, M2, M3, M4, M5) uses the closure T
    % to transform the elements of L into the elements of M1, M2, M3, M4
    % and M5.
    %
:- pred map5(pred(A, B, C, D, E, F), list(A), list(B), list(C), list(D),
    list(E), list(F)).
:- mode map5(in(pred(in, out, out, out, out, out) is det), in, out, out, out,
    out, out) is det.
:- mode map5(in(pred(in, out, out, out, out, out) is cc_multi), in, out, out,
    out, out, out) is cc_multi.
:- mode map5(in(pred(in, out, out, out, out, out) is semidet), in, out, out,
    out, out, out) is semidet.
:- mode map5(in(pred(in, out, out, out, out, out) is multi), in, out, out,
    out, out, out) is multi.
:- mode map5(in(pred(in, out, out, out, out, out) is nondet), in, out, out,
    out, out, out) is nondet.
:- mode map5(in(pred(in, in, in, in, in, in) is semidet), in, in, in, in, in,
    in) is semidet.

    % map6(T, L, M1, M2, M3, M4, M5, M6) uses the closure T
    % to transform the elements of L into the elements of M1, M2, M3, M4,
    % M5 and M6.
    %
:- pred map6(pred(A, B, C, D, E, F, G), list(A), list(B), list(C),
    list(D), list(E), list(F), list(G)).
:- mode map6(in(pred(in, out, out, out, out, out, out) is det), in, out, out,
    out, out, out, out) is det.
:- mode map6(in(pred(in, out, out, out, out, out, out) is cc_multi), in, out,
    out, out, out, out, out) is cc_multi.
:- mode map6(in(pred(in, out, out, out, out, out, out) is semidet), in, out,
    out, out, out, out, out) is semidet.
:- mode map6(in(pred(in, out, out, out, out, out, out) is multi), in, out,
    out, out, out, out, out) is multi.
:- mode map6(in(pred(in, out, out, out, out, out, out) is nondet), in, out,
    out, out, out, out, out) is nondet.
:- mode map6(in(pred(in, in, in, in, in, in, in) is semidet), in, in, in, in,
    in, in, in) is semidet.

    % map7(T, L, M1, M2, M3, M4, M5, M6, M7) uses the closure T
    % to transform the elements of L into the elements of M1, M2, M3, M4,
    % M5, M6 and M7.
    %
:- pred map7(pred(A, B, C, D, E, F, G, H), list(A), list(B), list(C),
    list(D), list(E), list(F), list(G), list(H)).
:- mode map7(in(pred(in, out, out, out, out, out, out, out) is det),
    in, out, out, out, out, out, out, out) is det.
:- mode map7(in(pred(in, out, out, out, out, out, out, out) is cc_multi),
    in, out, out, out, out, out, out, out) is cc_multi.
:- mode map7(in(pred(in, out, out, out, out, out, out, out) is semidet),
    in, out, out, out, out, out, out, out) is semidet.
:- mode map7(in(pred(in, out, out, out, out, out, out, out) is multi),
    in, out, out, out, out, out, out, out) is multi.
:- mode map7(in(pred(in, out, out, out, out, out, out, out) is nondet),
    in, out, out, out, out, out, out, out) is nondet.
:- mode map7(in(pred(in, in, in, in, in, in, in, in) is semidet),
    in, in, in, in, in, in, in, in) is semidet.

    % map8(T, L, M1, M2, M3, M4, M5, M6, M7) uses the closure T
    % to transform the elements of L into the elements of M1, M2, M3, M4,
    % M5, M6, M7 and M8.
    %
:- pred map8(pred(A, B, C, D, E, F, G, H, I), list(A), list(B), list(C),
    list(D), list(E), list(F), list(G), list(H), list(I)).
:- mode map8(in(pred(in, out, out, out, out, out, out, out, out) is det),
    in, out, out, out, out, out, out, out, out) is det.
:- mode map8(in(pred(in, out, out, out, out, out, out, out, out) is cc_multi),
    in, out, out, out, out, out, out, out, out) is cc_multi.
:- mode map8(in(pred(in, out, out, out, out, out, out, out, out) is semidet),
    in, out, out, out, out, out, out, out, out) is semidet.
:- mode map8(in(pred(in, out, out, out, out, out, out, out, out) is multi),
    in, out, out, out, out, out, out, out, out) is multi.
:- mode map8(in(pred(in, out, out, out, out, out, out, out, out) is nondet),
    in, out, out, out, out, out, out, out, out) is nondet.
:- mode map8(in(pred(in, in, in, in, in, in, in, in, in) is semidet),
    in, in, in, in, in, in, in, in, in) is semidet.

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

    % map_corresponding(F, [A1, .. An], [B1, .. Bn]) =
    %   [F(A1, B1), .., F(An, Bn)].
    %
    % Raises an exception if the list arguments differ in length.
    %
:- func map_corresponding(func(A, B) = R, list(A), list(B)) = list(R).
:- pred map_corresponding(pred(A, B, R), list(A), list(B), list(R)).
:- mode map_corresponding(in(pred(in, in, out) is det), in, in, out)
    is det.
:- mode map_corresponding(in(pred(in, in, out) is semidet), in, in, out)
    is semidet.

    % map_corresponding3(F, [A1, .. An], [B1, .. Bn], [C1, .. Cn]) =
    %   [F(A1, B1, C1), .., F(An, Bn, Cn)].
    %
    % Raises an exception if the list arguments differ in length.
    %
:- func map_corresponding3(func(A, B, C) = R, list(A), list(B), list(C))
    = list(R).
:- pred map_corresponding3(pred(A, B, C, R), list(A), list(B), list(C),
    list(R)).
:- mode map_corresponding3(in(pred(in, in, in, out) is det),
    in, in, in, out) is det.
:- mode map_corresponding3(in(pred(in, in, in, out) is semidet),
    in, in, in, out) is semidet.

    % map_corresponding4(F, [A1, .. An], [B1, .. Bn], [C1, .. Cn],
    %   [D1, .. Dn]) = [F(A1, B1, C1, D1), .., F(An, Bn, Cn, Dn)].
    %
    % Raises an exception if the list arguments differ in length.
    %
:- func map_corresponding4(func(A, B, C, D) = R, list(A), list(B), list(C),
    list(D)) = list(R).
:- pred map_corresponding4(pred(A, B, C, D, R), list(A), list(B), list(C),
    list(D), list(R)).
:- mode map_corresponding4(in(pred(in, in, in, in, out) is det),
    in, in, in, in, out) is det.
:- mode map_corresponding4(in(pred(in, in, in, in, out) is semidet),
    in, in, in, in, out) is semidet.

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

    % filter_map_corresponding/3 does the same job as map_corresponding/3,
    % except the function argument is semidet, and the output list consists of
    % only those applications of the function argument that succeeded.
    %
:- func filter_map_corresponding(func(A, B) = R, list(A), list(B))
    = list(R).
:- mode filter_map_corresponding(in(func(in, in) = out is semidet), in, in)
    = out is det.
:- pred filter_map_corresponding(
    pred(A, B, R)::in(pred(in, in, out) is semidet),
    list(A)::in, list(B)::in, list(R)::out) is det.

    % filter_map_corresponding3/4 does the same job as map_corresponding3/4,
    % except the function argument is semidet, and the output list consists of
    % only those applications of the function argument that succeeded.
    %
:- func filter_map_corresponding3(func(A, B, C) = R,
    list(A), list(B), list(C)) = list(R).
:- mode filter_map_corresponding3(in(func(in, in, in) = out is semidet),
    in, in, in) = out is det.
:- pred filter_map_corresponding3(
    pred(A, B, C, R)::in(pred(in, in, in, out) is semidet),
    list(A)::in, list(B)::in, list(C)::in, list(R)::out) is det.

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

    % 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, list(L), A) = A.
:- pred foldl(pred(L, A, A), 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.

    % foldl2(Pred, List, !Acc1, !Acc2):
    %
    % Does the same job as foldl, but with two accumulators.
    % Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient.
    % The last accumulator may be an I/O state, or some other
    % destructively updated piece of state.
    %
:- pred foldl2(pred(L, A, A, B, B), list(L), A, A, B, B).
:- 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, di, uo, di, uo) is det),
    in, di, uo, 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.
:- mode foldl2(in(pred(in, in, out, in, out) is nondet),
    in, in, out, in, out) is nondet.
:- mode foldl2(in(pred(in, in, out, mdi, muo) is nondet),
    in, in, out, mdi, muo) is nondet.
:- mode foldl2(in(pred(in, in, out, in, out) is cc_multi),
    in, in, out, in, out) is cc_multi.
:- mode foldl2(in(pred(in, in, out, mdi, muo) is cc_multi),
    in, in, out, mdi, muo) is cc_multi.
:- mode foldl2(in(pred(in, in, out, di, uo) is cc_multi),
    in, in, out, di, uo) is cc_multi.
:- mode foldl2(in(pred(in, di, uo, di, uo) is cc_multi),
    in, di, uo, di, uo) is cc_multi.

    % foldl3(Pred, List, !Acc1, !Acc2, !Acc3):
    %
    % Does the same job as foldl, but with three accumulators.
    % Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient.
    % The last accumulator may be an I/O state, or some other
    % destructively updated piece of state.
    %
:- pred foldl3(pred(L, A, A, B, B, C, C), list(L),
    A, A, B, B, C, C).
:- 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.
:- mode foldl3(in(pred(in, in, out, in, out, in, out) is nondet),
    in, in, out, in, out, in, out) is nondet.
:- mode foldl3(in(pred(in, in, out, in, out, mdi, muo) is nondet),
    in, in, out, in, out, mdi, muo) is nondet.
:- mode foldl3(in(pred(in, in, out, in, out, in, out) is cc_multi),
    in, in, out, in, out, in, out) is cc_multi.
:- mode foldl3(in(pred(in, in, out, in, out, di, uo) is cc_multi),
    in, in, out, in, out, di, uo) is cc_multi.

    % foldl4(Pred, List, !Acc1, !Acc2, !Acc3, !Acc4):
    % Does the same job as foldl, but with four accumulators.
    % Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient.
    % The last accumulator may be an I/O state, or some other
    % destructively updated piece of state.
    %
:- pred foldl4(pred(L, A, A, B, B, C, C, D, D), list(L),
    A, A, B, B, C, C, D, D).
:- 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 cc_multi),
    in, in, out, in, out, in, out, in, out) is cc_multi.
:- mode foldl4(in(pred(in, in, out, in, out, in, out, di, uo) is cc_multi),
    in, in, out, in, out, in, out, di, uo) is cc_multi.
:- 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.
:- mode foldl4(in(pred(in, in, out, in, out, in, out, in, out) is nondet),
    in, in, out, in, out, in, out, in, out) is nondet.
:- mode foldl4(in(pred(in, in, out, in, out, in, out, mdi, muo) is nondet),
    in, in, out, in, out, in, out, mdi, muo) is nondet.

    % foldl5(Pred, List, !Acc1, !Acc2, !Acc3, !Acc4, !Acc5):
    % Does the same job as foldl, but with five accumulators.
    % Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient.
    % The last accumulator may be an I/O state, or some other
    % destructively updated piece of state.
    %
:- pred foldl5(pred(L, A, A, B, B, C, C, D, D, E, E), list(L),
    A, A, B, B, C, C, D, D, E, E).
:- 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.
:- mode foldl5(in(pred(in, in, out, in, out, in, out, in, out, in, out)
    is nondet),
    in, in, out, in, out, in, out, in, out, in, out) is nondet.
:- mode foldl5(in(pred(in, in, out, in, out, in, out, in, out, mdi, muo)
    is nondet),
    in, in, out, in, out, in, out, in, out, mdi, muo) is nondet.
:- mode foldl5(in(pred(in, in, out, in, out, in, out, in, out, in, out)
    is cc_multi),
    in, in, out, in, out, in, out, in, out, in, out) is cc_multi.
:- mode foldl5(in(pred(in, in, out, in, out, in, out, in, out, di, uo)
    is cc_multi),
    in, in, out, in, out, in, out, in, out, di, uo) is cc_multi.

    % foldl6(Pred, List, !Acc1, !Acc2, !Acc3, !Acc4, !Acc5, !Acc6):
    % Does the same job as foldl, but with six accumulators.
    % Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient.
    % The last accumulator may be an I/O state, or some other
    % destructively updated piece of state.
    %
:- pred foldl6(pred(L, A, A, B, B, C, C, D, D, E, E, F, F), list(L),
    A, A, B, B, C, C, D, D, E, E, F, F).
:- mode foldl6(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out) is det),
    in, in, out, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldl6(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    mdi, muo) is det),
    in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl6(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    di, uo) is det),
    in, in, out, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldl6(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out) is cc_multi),
    in, in, out, in, out, in, out, in, out, in, out, in, out) is cc_multi.
:- mode foldl6(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    di, uo) is cc_multi),
    in, in, out, in, out, in, out, in, out, in, out, di, uo) is cc_multi.
:- mode foldl6(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out) is semidet),
    in, in, out, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl6(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    mdi, muo) is semidet),
    in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl6(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    di, uo) is semidet),
    in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet.
:- mode foldl6(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out) is nondet),
    in, in, out, in, out, in, out, in, out, in, out, in, out) is nondet.

    % foldl7(Pred, List, !Acc1, !Acc2, !Acc3, !Acc4, !Acc5, !Acc6, !Acc7):
    % Does the same job as foldl, but with seven accumulators.
    % Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient.
    % The last accumulator may be an I/O state, or some other
    % destructively updated piece of state.
    %
:- pred foldl7(pred(L, A, A, B, B, C, C, D, D, E, E, F, F, G, G), list(L),
    A, A, B, B, C, C, D, D, E, E, F, F, G, G).
:- mode foldl7(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is det),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is det.
:- mode foldl7(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, mdi, muo) is det),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, mdi, muo) is det.
:- mode foldl7(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, di, uo) is det),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, di, uo) is det.
:- mode foldl7(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is cc_multi),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is cc_multi.
:- mode foldl7(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, di, uo) is cc_multi),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, di, uo) is cc_multi.
:- mode foldl7(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is semidet),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is semidet.
:- mode foldl7(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, mdi, muo) is semidet),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, mdi, muo) is semidet.
:- mode foldl7(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, di, uo) is semidet),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, di, uo) is semidet.
:- mode foldl7(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is nondet),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is nondet.

    % foldl8(Pred, List, !Acc1, !Acc2, !Acc3, !Acc4, !Acc5, !Acc6, !Acc7,
    %   !Acc8):
    % Does the same job as foldl, but with seven accumulators.
    % Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient.
    % The last accumulator may be an I/O state, or some other
    % destructively updated piece of state.
    %
:- pred foldl8(pred(L, A, A, B, B, C, C, D, D, E, E, F, F, G, G, H, H),
    list(L),
    A, A, B, B, C, C, D, D, E, E, F, F, G, G, H , H).
:- mode foldl8(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, in, out) is det),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, in, out) is det.
:- mode foldl8(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, mdi, muo) is det),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, mdi, muo) is det.
:- mode foldl8(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, di, uo) is det),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, di, uo) is det.
:- mode foldl8(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, in, out) is cc_multi),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, in, out) is cc_multi.
:- mode foldl8(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, di, uo) is cc_multi),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, di, uo) is cc_multi.
:- mode foldl8(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, in, out) is semidet),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, in, out) is semidet.
:- mode foldl8(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, mdi, muo) is semidet),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, mdi, muo) is semidet.
:- mode foldl8(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, di, uo) is semidet),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, di, uo) is semidet.
:- mode foldl8(in(pred(in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, in, out) is nondet),
    in, in, out, in, out, in, out, in, out, in, out,
    in, out, in, out, in, out) is nondet.

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

    % gap_foldl(ProcessPred, GapPred, List, !Acc):
    %
    % Invoke ProcessPred on every element of List,
    % and invoke GapPred on every gap *between* elements in List.
    % The intended use case is printing a list, using ProcessPred to print
    % each element, and using GapPred to print e.g. commas between
    % the elements.
    %
:- pred gap_foldl(pred(L, A, A), pred(A, A), list(L), A, A).
:- mode gap_foldl(in(pred(in, di, uo) is det), in(pred(di, uo) is det),
    in, di, uo) is det.
:- mode gap_foldl(in(pred(in, in, out) is det), in(pred(in, out) is det),
    in, in, out) is det.

    % last_gap_foldl(ProcessPred, GapPred, LastGapPred, List, !Acc):
    %
    % Invoke ProcessPred on every element of List,
    % invoke GapPred on every gap between elements in List except the last,
    % and invoke LastGapPred on the last gap between elements.
    % The intended use case is printing a list, using ProcessPred to print
    % each element, and using GapPred to print e.g. commas between
    % the elements, and using LastGapPred to print something else,
    % such as "and".
    %
:- pred last_gap_foldl(pred(L, A, A), pred(A, A), pred(A, A), list(L), A, A).
:- mode last_gap_foldl(in(pred(in, di, uo) is det), in(pred(di, uo) is det),
    in(pred(di, uo) is det), in, di, uo) is det.
:- mode last_gap_foldl(in(pred(in, in, out) is det), in(pred(in, out) is det),
    in(pred(in, out) is det), in, in, out) is det.

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

    % chunk_foldl(ChunkSize, Pred, List, !Acc):
    %
    % Does the same job as foldl(Pred, List, !Acc), but using
    % two nested loops, not one.
    %
    % In most grades, the implementation of foldl can handle lists
    % of arbitrary length, the reason being that tail recursion optimization
    % allows it to do its work using only one stack frame. However, in some
    % grades (including debugging and some profiling grades) tail recursion
    % optimization is not available, which means that foldl will need
    % a separate stack frame for processing each element. With long lists,
    % this can exhaust the stack.
    %
    % chunk_foldl addresses this issue by replacing foldl's single loop
    % with an outer and an inner loop. Each invocation of the inner loop
    % processes one chunk of the list (whose length is given by ChunkSize),
    % and when it is done with that chunk, the inner loop returns, which
    % means that it frees up all the stack frames that it used. The outer loop
    % then continues to invoke the inner loop until all elements of List
    % have been processed.
    %
    % With this arrangement, the maximum number of stack frames needed
    % to process a list of length N is N/ChunkSize + ChunkSize, the former
    % being the number of frames used by the outer loop, and the latter
    % being the max number of frames used by the inner loop. This means that
    % the optimal ChunkSize for a list of length N is the square root of N,
    % but usually optimality is not required, and any reasonable chunk size
    % will work.
    %
:- pred chunk_foldl(int, pred(L, A, A), list(L), A, A).
:- mode chunk_foldl(in, in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode chunk_foldl(in, in(pred(in, in, out) is det), in, in, out) is det.

    % Does the same job of chunk_foldl, but with two accumulators.
    %
:- pred chunk_foldl2(int, pred(L, A, A, B, B), list(L), A, A, B, B).
:- mode chunk_foldl2(in, in(pred(in, di, uo, di, uo) is det),
    in, di, uo, di, uo) is det.
:- mode chunk_foldl2(in, in(pred(in, in, out, di, uo) is det),
    in, in, out, di, uo) is det.
:- mode chunk_foldl2(in, in(pred(in, in, out, in, out) is det),
    in, in, out, in, out) is det.

    % Does the same job of chunk_foldl, but with three accumulators.
    %
:- pred chunk_foldl3(int, pred(L, A, A, B, B, C, C),
    list(L), A, A, B, B, C, C).
:- mode chunk_foldl3(in, in(pred(in, in, out, di, uo, di, uo) is det),
    in, in, out, di, uo, di, uo) is det.
:- mode chunk_foldl3(in, in(pred(in, in, out, in, out, di, uo) is det),
    in, in, out, in, out, di, uo) is det.
:- mode chunk_foldl3(in, in(pred(in, in, out, in, out, in, out) is det),
    in, in, out, in, out, in, out) is det.

    % Does the same job of chunk_foldl, but with four accumulators.
    %
:- pred chunk_foldl4(int, pred(L, A, A, B, B, C, C, D, D),
    list(L), A, A, B, B, C, C, D, D).
:- mode chunk_foldl4(in,
    in(pred(in, in, out, in, out, di, uo, di, uo) is det),
    in, in, out, in, out, di, uo, di, uo) is det.
:- mode chunk_foldl4(in,
    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 chunk_foldl4(in,
    in(pred(in, in, out, in, out, in, out, in, out) is det),
    in, in, out, in, out, in, out, in, out) is det.

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

    % 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, list(L), A) = A.
:- pred foldr(pred(L, A, A), 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.

    % foldr2(Pred, List, !Acc1, !Acc2):
    %
    % Does the same job as foldr, but with two accumulators.
    % Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient.
    % The last accumulator may be an I/O state, or some other
    % destructively updated piece of state.
    %
:- pred foldr2(pred(L, A, A, B, B), list(L), A, A, B, B).
:- 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.
:- mode foldr2(in(pred(in, in, out, in, out) is nondet), in, in, out,
    in, out) is nondet.
:- mode foldr2(in(pred(in, in, out, mdi, muo) is nondet), in, in, out,
    mdi, muo) is nondet.

    % foldr3(Pred, List, !Acc1, !Acc2, !Acc3):
    %
    % Does the same job as foldr, but with two accumulators.
    % Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient.
    % The last accumulator may be an I/O state, or some other
    % destructively updated piece of state.
    %
:- pred foldr3(pred(L, A, A, B, B, C, C), list(L), A, A, B, B, C, C).
:- 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.
:- mode foldr3(in(pred(in, in, out, in, out, in, out) is nondet), in,
    in, out, in, out, in, out) is nondet.
:- mode foldr3(in(pred(in, in, out, in, out, mdi, muo) is nondet), in,
    in, out, in, out, mdi, muo) is nondet.

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

    % foldl_corresponding(P, As, Bs, !Acc):
    %
    % Does the same job as foldl, but works on two lists in parallel.
    % Raises an exception if the list arguments differ in length.
    %
:- pred foldl_corresponding(pred(A, B, C, C), list(A), list(B), C, C).
:- 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.
:- mode foldl_corresponding(in(pred(in, in, in, out) is nondet),
    in, in, in, out) is nondet.
:- mode foldl_corresponding(in(pred(in, in, mdi, muo) is nondet),
    in, in, mdi, muo) is nondet.
:- mode foldl_corresponding(in(pred(in, in, in, out) is cc_multi),
    in, in, in, out) is cc_multi.
:- mode foldl_corresponding(in(pred(in, in, di, uo) is cc_multi),
    in, in, di, uo) is cc_multi.

:- func foldl_corresponding(func(A, B, C) = C, list(A), list(B), C) = C.

    % foldl2_corresponding(F, As, Bs, !Acc1, !Acc2):
    %
    % Does the same job as foldl_corresponding, but with two accumulators.
    %
:- pred foldl2_corresponding(pred(A, B, C, C, D, D), list(A), list(B),
    C, C, D, D).
:- 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.
:- mode foldl2_corresponding(in(pred(in, in, in, out, in, out) is nondet),
    in, in, in, out, in, out) is nondet.
:- mode foldl2_corresponding(in(pred(in, in, in, out, mdi, muo) is nondet),
    in, in, in, out, mdi, muo) is nondet.
:- mode foldl2_corresponding(in(pred(in, in, in, out, in, out) is cc_multi),
    in, in, in, out, in, out) is cc_multi.
:- mode foldl2_corresponding(in(pred(in, in, in, out, di, uo) is cc_multi),
    in, in, in, out, di, uo) is cc_multi.

    % foldl3_corresponding(F, As, Bs, !Acc1, !Acc2, !Acc3):
    %
    % Does the same job as foldl_corresponding, but with three accumulators.
    %
:- pred foldl3_corresponding(pred(A, B, C, C, D, D, E, E),
    list(A), list(B), C, C, D, D, E, E).
:- mode foldl3_corresponding(
    in(pred(in, in, in, out, in, out, in, out) is det),
    in, in, in, out, in, out, in, out) is det.
:- mode foldl3_corresponding(
    in(pred(in, in, in, out, in, out, mdi, muo) is det),
    in, in, in, out, in, out, mdi, muo) is det.
:- mode foldl3_corresponding(
    in(pred(in, in, in, out, in, out, di, uo) is det),
    in, in, in, out, in, out, di, uo) is det.
:- mode foldl3_corresponding(
    in(pred(in, in, in, out, in, out, in, out) is semidet),
    in, in, in, out, in, out, in, out) is semidet.
:- mode foldl3_corresponding(
    in(pred(in, in, in, out, in, out, mdi, muo) is semidet),
    in, in, in, out, in, out, mdi, muo) is semidet.
:- mode foldl3_corresponding(
    in(pred(in, in, in, out, in, out, di, uo) is semidet),
    in, in, in, out, in, out, di, uo) is semidet.

    % foldl4_corresponding(F, As, Bs, !Acc1, !Acc2, !Acc3, !Acc4):
    %
    % Does the same job as foldl_corresponding, but with four accumulators.
    %
:- pred foldl4_corresponding(pred(A, B, C, C, D, D, E, E, F, F),
    list(A), list(B), C, C, D, D, E, E, F, F).
:- mode foldl4_corresponding(
    in(pred(in, in, in, out, in, out, in, out, in, out) is det),
    in, in, in, out, in, out, in, out, in, out) is det.
:- mode foldl4_corresponding(
    in(pred(in, in, in, out, in, out, in, out, mdi, muo) is det),
    in, in, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl4_corresponding(
    in(pred(in, in, in, out, in, out, in, out, di, uo) is det),
    in, in, in, out, in, out, in, out, di, uo) is det.
:- mode foldl4_corresponding(
    in(pred(in, in, in, out, in, out, in, out, in, out) is semidet),
    in, in, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl4_corresponding(
    in(pred(in, in, in, out, in, out, in, out, mdi, muo) is semidet),
    in, in, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl4_corresponding(
    in(pred(in, in, in, out, in, out, in, out, di, uo) is semidet),
    in, in, in, out, in, out, in, out, di, uo) is semidet.

    % foldl_corresponding3(P, As, Bs, Cs, !Acc):
    %
    % Does the same jobs as foldl_corresponding, but folds over
    % three corresponding lists.
    %
:- pred foldl_corresponding3(pred(A, B, C, D, D),
    list(A), list(B), list(C), D, D).
:- mode foldl_corresponding3(in(pred(in, in, in, in, out) is det),
    in, in, in, in, out) is det.
:- mode foldl_corresponding3(in(pred(in, in, in, mdi, muo) is det),
    in, in, in, mdi, muo) is det.
:- mode foldl_corresponding3(in(pred(in, in, in, di, uo) is det),
    in, in, in, di, uo) is det.
:- mode foldl_corresponding3(in(pred(in, in, in, in, out) is semidet),
    in, in, in, in, out) is semidet.
:- mode foldl_corresponding3(in(pred(in, in, in, mdi, muo) is semidet),
    in, in, in, mdi, muo) is semidet.
:- mode foldl_corresponding3(in(pred(in, in, in, di, uo) is semidet),
    in, in, in, di, uo) is semidet.

    % foldl2_corresponding3(P, As, Bs, Cs, !Acc1, !Acc2):
    %
    % Does the same jobs as foldl_corresponding3, but with two accumulators.
    %
:- pred foldl2_corresponding3(pred(A, B, C, D, D, E, E),
    list(A), list(B), list(C), D, D, E, E).
:- mode foldl2_corresponding3(in(pred(in, in, in, in, out, in, out) is det),
    in, in, in, in, out, in, out) is det.
:- mode foldl2_corresponding3(in(pred(in, in, in, in, out, mdi, muo) is det),
    in, in, in, in, out, mdi, muo) is det.
:- mode foldl2_corresponding3(in(pred(in, in, in, in, out, di, uo) is det),
    in, in, in, in, out, di, uo) is det.
:- mode foldl2_corresponding3(
    in(pred(in, in, in, in, out, in, out) is semidet),
    in, in, in, in, out, in, out) is semidet.
:- mode foldl2_corresponding3(
    in(pred(in, in, in, in, out, mdi, muo) is semidet),
    in, in, in, in, out, mdi, muo) is semidet.
:- mode foldl2_corresponding3(
    in(pred(in, in, in, in, out, di, uo) is semidet),
    in, in, in, in, out, di, uo) is semidet.

    % foldl3_corresponding3(P, As, Bs, Cs, !Acc1, !Acc2, !Acc3):
    %
    % like foldl_corresponding3 but with three accumulators.
    %
:- pred foldl3_corresponding3(pred(A, B, C, D, D, E, E, F, F),
    list(A), list(B), list(C), D, D, E, E, F, F).
:- mode foldl3_corresponding3(
    in(pred(in, in, in, in, out, in, out, in, out) is det),
    in, in, in, in, out, in, out, in, out) is det.
:- mode foldl3_corresponding3(
    in(pred(in, in, in, in, out, in, out, mdi, muo) is det),
    in, in, in, in, out, in, out, mdi, muo) is det.
:- mode foldl3_corresponding3(
    in(pred(in, in, in, in, out, in, out, di, uo) is det),
    in, in, in, in, out, in, out, di, uo) is det.
:- mode foldl3_corresponding3(
    in(pred(in, in, in, in, out, in, out, in, out) is semidet),
    in, in, in, in, out, in, out, in, out) is semidet.
:- mode foldl3_corresponding3(
    in(pred(in, in, in, in, out, in, out, mdi, muo) is semidet),
    in, in, in, in, out, in, out, mdi, muo) is semidet.
:- mode foldl3_corresponding3(
    in(pred(in, in, in, in, out, in, out, di, uo) is semidet),
    in, in, in, in, out, in, out, di, uo) is semidet.

    % foldl4_corresponding3(P, As, Bs, Cs, !Acc1, !Acc2, !Acc3, !Acc4):
    %
    % like foldl_corresponding3 but with four accumulators.
    %
:- pred foldl4_corresponding3(pred(A, B, C, D, D, E, E, F, F, G, G),
    list(A), list(B), list(C), D, D, E, E, F, F, G, G).
:- mode foldl4_corresponding3(
    in(pred(in, in, in, in, out, in, out, in, out, in, out) is det),
    in, in, in, in, out, in, out, in, out, in, out) is det.
:- mode foldl4_corresponding3(
    in(pred(in, in, in, in, out, in, out, in, out, mdi, muo) is det),
    in, in, in, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl4_corresponding3(
    in(pred(in, in, in, in, out, in, out, in, out, di, uo) is det),
    in, in, in, in, out, in, out, in, out, di, uo) is det.
:- mode foldl4_corresponding3(
    in(pred(in, in, in, in, out, in, out, in, out, in, out) is semidet),
    in, in, in, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl4_corresponding3(
    in(pred(in, in, in, in, out, in, out, in, out, mdi, muo) is semidet),
    in, in, in, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl4_corresponding3(
    in(pred(in, in, in, in, out, in, out, in, out, di, uo) is semidet),
    in, in, in, in, out, in, out, in, out, di, uo) is semidet.

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

    % map_foldl(Pred, InList, OutList, Start, End):
    %
    % Calls Pred on each element of InList, working left-to-right.
    % The second argument of that call will be included in OutList,
    % while the third and fourth will 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 Pred
    % accumulate pieces of information.) The initial value of the accumulator
    % is Start, each call to Pred updates it to the next value, and
    % foldl returns its final value as End.
    %
:- pred map_foldl(pred(L, M, A, A), list(L), list(M), A, A).
:- 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.
:- mode map_foldl(in(pred(in, in, di, uo) is semidet), in, in, di, uo)
    is semidet.
:- mode map_foldl(in(pred(in, out, in, out) is nondet), in, out, in, out)
    is nondet.
:- mode map_foldl(in(pred(in, out, mdi, muo) is nondet), in, out, mdi, muo)
    is nondet.
:- mode map_foldl(in(pred(in, out, in, out) is cc_multi), in, out, in, out)
    is cc_multi.
:- mode map_foldl(in(pred(in, out, mdi, muo) is cc_multi), in, out, mdi, muo)
    is cc_multi.
:- mode map_foldl(in(pred(in, out, di, uo) is cc_multi), in, out, di, uo)
    is cc_multi.

    % Same as map_foldl, but with two accumulators.
    %
:- pred map_foldl2(pred(L, M, A, A, B, B), list(L), list(M), A, A, B, B).
:- mode map_foldl2(in(pred(in, out, in, out, in, out) is det),
    in, out, in, out, in, out) is det.
:- mode map_foldl2(in(pred(in, out, in, out, mdi, muo) is det),
    in, out, in, out, mdi, muo) is det.
:- mode map_foldl2(in(pred(in, out, in, out, di, uo) is det),
    in, out, in, out, di, uo) is det.
:- mode map_foldl2(in(pred(in, out, in, out, in, out) is semidet),
    in, out, in, out, in, out) is semidet.
:- mode map_foldl2(in(pred(in, out, in, out, mdi, muo) is semidet),
    in, out, in, out, mdi, muo) is semidet.
:- mode map_foldl2(in(pred(in, out, in, out, di, uo) is semidet),
    in, out, in, out, di, uo) is semidet.
:- mode map_foldl2(in(pred(in, in, in, out, di, uo) is semidet),
    in, in, in, out, di, uo) is semidet.
:- mode map_foldl2(in(pred(in, out, in, out, in, out) is cc_multi),
    in, out, in, out, in, out) is cc_multi.
:- mode map_foldl2(in(pred(in, out, in, out, mdi, muo) is cc_multi),
    in, out, in, out, mdi, muo) is cc_multi.
:- mode map_foldl2(in(pred(in, out, in, out, di, uo) is cc_multi),
    in, out, in, out, di, uo) is cc_multi.
:- mode map_foldl2(in(pred(in, out, in, out, in, out) is nondet),
    in, out, in, out, in, out) is nondet.

    % Same as map_foldl, but with three accumulators.
    %
:- pred map_foldl3(pred(L, M, A, A, B, B, C, C), list(L), list(M),
    A, A, B, B, C, C).
:- mode map_foldl3(in(pred(in, out, in, out, in, out, di, uo) is det),
    in, out, in, out, in, out, di, uo) is det.
:- mode map_foldl3(in(pred(in, out, in, out, in, out, in, out) is det),
    in, out, in, out, in, out, in, out) is det.
:- mode map_foldl3(in(pred(in, out, in, out, in, out, di, uo) is cc_multi),
    in, out, in, out, in, out, di, uo) is cc_multi.
:- mode map_foldl3(in(pred(in, out, in, out, in, out, in, out) is cc_multi),
    in, out, in, out, in, out, in, out) is cc_multi.
:- mode map_foldl3(in(pred(in, out, in, out, in, out, in, out) is semidet),
    in, out, in, out, in, out, in, out) is semidet.
:- mode map_foldl3(in(pred(in, out, in, out, in, out, in, out) is nondet),
    in, out, in, out, in, out, in, out) is nondet.

    % Same as map_foldl, but with four accumulators.
    %
:- pred map_foldl4(pred(L, M, A, A, B, B, C, C, D, D), list(L), list(M),
    A, A, B, B, C, C, D, D).
:- mode map_foldl4(in(pred(in, out, in, out, in, out, in, out, di, uo)
    is det),
    in, out, in, out, in, out, in, out, di, uo) is det.
:- mode map_foldl4(in(pred(in, out, in, out, in, out, in, out, in, out)
    is det),
    in, out, in, out, in, out, in, out, in, out) is det.
:- mode map_foldl4(in(pred(in, out, in, out, in, out, in, out, di, uo)
    is cc_multi),
    in, out, in, out, in, out, in, out, di, uo) is cc_multi.
:- mode map_foldl4(in(pred(in, out, in, out, in, out, in, out, in, out)
    is cc_multi),
    in, out, in, out, in, out, in, out, in, out) is cc_multi.
:- mode map_foldl4(in(pred(in, out, in, out, in, out, in, out, in, out)
    is semidet),
    in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode map_foldl4(in(pred(in, out, in, out, in, out, in, out, in, out)
    is nondet),
    in, out, in, out, in, out, in, out, in, out) is nondet.

    % Same as map_foldl, but with five accumulators.
    %
:- pred map_foldl5(pred(L, M, A, A, B, B, C, C, D, D, E, E),
    list(L), list(M), A, A, B, B, C, C, D, D, E, E).
:- mode map_foldl5(in(pred(in, out, in, out, in, out, in, out, in, out,
    di, uo) is det),
    in, out, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode map_foldl5(in(pred(in, out, in, out, in, out, in, out, in, out,
    in, out) is det),
    in, out, in, out, in, out, in, out, in, out, in, out) is det.
:- mode map_foldl5(in(pred(in, out, in, out, in, out, in, out, in, out,
    di, uo) is cc_multi),
    in, out, in, out, in, out, in, out, in, out, di, uo) is cc_multi.
:- mode map_foldl5(in(pred(in, out, in, out, in, out, in, out, in, out,
    in, out) is cc_multi),
    in, out, in, out, in, out, in, out, in, out, in, out) is cc_multi.
:- mode map_foldl5(in(pred(in, out, in, out, in, out, in, out, in, out,
    in, out) is semidet),
    in, out, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode map_foldl5(in(pred(in, out, in, out, in, out, in, out, in, out,
    in, out) is nondet),
    in, out, in, out, in, out, in, out, in, out, in, out) is nondet.

    % Same as map_foldl, but with six accumulators.
    %
:- pred map_foldl6(pred(L, M, A, A, B, B, C, C, D, D, E, E, F, F),
    list(L), list(M), A, A, B, B, C, C, D, D, E, E, F, F).
:- mode map_foldl6(in(pred(in, out, in, out, in, out, in, out, in, out,
    in, out, di, uo) is det),
    in, out, in, out, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode map_foldl6(in(pred(in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is det),
    in, out, in, out, in, out, in, out, in, out, in, out, in, out) is det.
:- mode map_foldl6(in(pred(in, out, in, out, in, out, in, out, in, out,
    in, out, di, uo) is cc_multi),
    in, out, in, out, in, out, in, out, in, out, in, out, di, uo)
    is cc_multi.
:- mode map_foldl6(in(pred(in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is cc_multi),
    in, out, in, out, in, out, in, out, in, out, in, out, in, out)
    is cc_multi.
:- mode map_foldl6(in(pred(in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is semidet),
    in, out, in, out, in, out, in, out, in, out, in, out, in, out)
    is semidet.
:- mode map_foldl6(in(pred(in, out, in, out, in, out, in, out, in, out,
    in, out, in, out) is nondet),
    in, out, in, out, in, out, in, out, in, out, in, out, in, out)
    is nondet.

    % Same as map_foldl, but with two mapped outputs.
    %
:- pred map2_foldl(pred(L, M, N, A, A), list(L), list(M), list(N),
    A, A).
:- mode map2_foldl(in(pred(in, out, out, in, out) is det), in, out, out,
    in, out) is det.
:- mode map2_foldl(in(pred(in, out, out, mdi, muo) is det), in, out, out,
    mdi, muo) is det.
:- mode map2_foldl(in(pred(in, out, out, di, uo) is det), in, out, out,
    di, uo) is det.
:- mode map2_foldl(in(pred(in, out, out, in, out) is semidet), in, out, out,
    in, out) is semidet.
:- mode map2_foldl(in(pred(in, out, out, mdi, muo) is semidet), in, out, out,
    mdi, muo) is semidet.
:- mode map2_foldl(in(pred(in, out, out, di, uo) is semidet), in, out, out,
    di, uo) is semidet.
:- mode map2_foldl(in(pred(in, out, out, in, out) is nondet), in, out, out,
    in, out) is nondet.
:- mode map2_foldl(in(pred(in, out, out, mdi, muo) is nondet), in, out, out,
    mdi, muo) is nondet.
:- mode map2_foldl(in(pred(in, out, out, in, out) is cc_multi), in, out, out,
    in, out) is cc_multi.
:- mode map2_foldl(in(pred(in, out, out, di, uo) is cc_multi), in, out, out,
    di, uo) is cc_multi.

    % Same as map_foldl, but with two mapped outputs and two accumulators.
    %
:- pred map2_foldl2(pred(L, M, N, A, A, B, B), list(L), list(M), list(N),
    A, A, B, B).
:- mode map2_foldl2(in(pred(in, out, out, in, out, di, uo) is det),
    in, out, out, in, out, di, uo) is det.
:- mode map2_foldl2(in(pred(in, out, out, in, out, in, out) is det),
    in, out, out, in, out, in, out) is det.
:- mode map2_foldl2(in(pred(in, out, out, in, out, di, uo) is cc_multi),
    in, out, out, in, out, di, uo) is cc_multi.
:- mode map2_foldl2(in(pred(in, out, out, in, out, in, out) is cc_multi),
    in, out, out, in, out, in, out) is cc_multi.
:- mode map2_foldl2(in(pred(in, out, out, in, out, in, out) is semidet),
    in, out, out, in, out, in, out) is semidet.
:- mode map2_foldl2(in(pred(in, out, out, in, out, in, out) is nondet),
    in, out, out, in, out, in, out) is nondet.

    % Same as map_foldl, but with two mapped outputs and three accumulators.
    %
:- pred map2_foldl3(pred(L, M, N, A, A, B, B, C, C),
    list(L), list(M), list(N), A, A, B, B, C, C).
:- mode map2_foldl3(
    in(pred(in, out, out, in, out, in, out, in, out) is det),
    in, out, out, in, out, in, out, in, out) is det.
:- mode map2_foldl3(
    in(pred(in, out, out, in, out, in, out, di, uo) is det),
    in, out, out, in, out, in, out, di, uo) is det.
:- mode map2_foldl3(
    in(pred(in, out, out, in, out, in, out, in, out) is cc_multi),
    in, out, out, in, out, in, out, in, out) is cc_multi.
:- mode map2_foldl3(
    in(pred(in, out, out, in, out, in, out, di, uo) is cc_multi),
    in, out, out, in, out, in, out, di, uo) is cc_multi.
:- mode map2_foldl3(
    in(pred(in, out, out, in, out, in, out, in, out) is semidet),
    in, out, out, in, out, in, out, in, out) is semidet.
:- mode map2_foldl3(
    in(pred(in, out, out, in, out, in, out, in, out) is nondet),
    in, out, out, in, out, in, out, in, out) is nondet.

    % Same as map_foldl, but with two mapped outputs and four accumulators.
    %
:- pred map2_foldl4(pred(L, M, N, A, A, B, B, C, C, D, D),
    list(L), list(M), list(N), A, A, B, B, C, C, D, D).
:- mode map2_foldl4(
    in(pred(in, out, out, in, out, in, out, in, out, in, out) is det),
    in, out, out, in, out, in, out, in, out, in, out) is det.
:- mode map2_foldl4(
    in(pred(in, out, out, in, out, in, out, in, out, di, uo) is det),
    in, out, out, in, out, in, out, in, out, di, uo) is det.
:- mode map2_foldl4(
    in(pred(in, out, out, in, out, in, out, in, out, in, out) is cc_multi),
    in, out, out, in, out, in, out, in, out, in, out) is cc_multi.
:- mode map2_foldl4(
    in(pred(in, out, out, in, out, in, out, in, out, di, uo) is cc_multi),
    in, out, out, in, out, in, out, in, out, di, uo) is cc_multi.
:- mode map2_foldl4(
    in(pred(in, out, out, in, out, in, out, in, out, in, out) is semidet),
    in, out, out, in, out, in, out, in, out, in, out) is semidet.
:- mode map2_foldl4(
    in(pred(in, out, out, in, out, in, out, in, out, in, out) is nondet),
    in, out, out, in, out, in, out, in, out, in, out) is nondet.

    % Same as map_foldl, but with three mapped outputs.
    %
:- pred map3_foldl(pred(L, M, N, O, A, A), list(L), list(M), list(N),
    list(O), A, A).
:- mode map3_foldl(in(pred(in, out, out, out, in, out) is det), in, out, out,
    out, in, out) is det.
:- mode map3_foldl(in(pred(in, out, out, out, mdi, muo) is det), in, out, out,
    out, mdi, muo) is det.
:- mode map3_foldl(in(pred(in, out, out, out, di, uo) is det), in, out, out,
    out, di, uo) is det.
:- mode map3_foldl(in(pred(in, out, out, out, in, out) is semidet), in, out,
    out, out, in, out) is semidet.
:- mode map3_foldl(in(pred(in, out, out, out, mdi, muo) is semidet), in, out,
    out, out, mdi, muo) is semidet.
:- mode map3_foldl(in(pred(in, out, out, out, di, uo) is semidet), in, out,
    out, out, di, uo) is semidet.
:- mode map3_foldl(in(pred(in, out, out, out, in, out) is nondet), in, out,
    out, out, in, out) is nondet.
:- mode map3_foldl(in(pred(in, out, out, out, mdi, muo) is nondet), in, out,
    out, out, mdi, muo) is nondet.
:- mode map3_foldl(in(pred(in, out, out, out, in, out) is cc_multi), in, out,
    out, out, in, out) is cc_multi.
:- mode map3_foldl(in(pred(in, out, out, out, di, uo) is cc_multi), in, out,
    out, out, di, uo) is cc_multi.

    % Same as map_foldl, but with three mapped outputs and two accumulators.
    %
:- pred map3_foldl2(pred(L, M, N, O, A, A, B, B), list(L),
    list(M), list(N), list(O), A, A, B, B).
:- mode map3_foldl2(in(pred(in, out, out, out, in, out, di, uo) is det),
    in, out, out, out, in, out, di, uo) is det.
:- mode map3_foldl2(in(pred(in, out, out, out, in, out, in, out) is det),
    in, out, out, out, in, out, in, out) is det.
:- mode map3_foldl2(in(pred(in, out, out, out, in, out, di, uo) is cc_multi),
    in, out, out, out, in, out, di, uo) is cc_multi.
:- mode map3_foldl2(in(pred(in, out, out, out, in, out, in, out) is cc_multi),
    in, out, out, out, in, out, in, out) is cc_multi.
:- mode map3_foldl2(in(pred(in, out, out, out, in, out, in, out) is semidet),
    in, out, out, out, in, out, in, out) is semidet.
:- mode map3_foldl2(in(pred(in, out, out, out, in, out, in, out) is nondet),
    in, out, out, out, in, out, in, out) is nondet.

    % Same as map_foldl, but with four mapped outputs.
    %
:- pred map4_foldl(pred(L, M, N, O, P, A, A), list(L), list(M), list(N),
    list(O), list(P), A, A).
:- mode map4_foldl(in(pred(in, out, out, out, out, in, out) is det),
    in, out, out, out, out, in, out) is det.
:- mode map4_foldl(in(pred(in, out, out, out, out, mdi, muo) is det),
    in, out, out, out, out, mdi, muo) is det.
:- mode map4_foldl(in(pred(in, out, out, out, out, di, uo) is det),
    in, out, out, out, out, di, uo) is det.
:- mode map4_foldl(in(pred(in, out, out, out, out, in, out) is semidet),
    in, out, out, out, out, in, out) is semidet.
:- mode map4_foldl(in(pred(in, out, out, out, out, mdi, muo) is semidet),
    in, out, out, out, out, mdi, muo) is semidet.
:- mode map4_foldl(in(pred(in, out, out, out, out, di, uo) is semidet),
    in, out, out, out, out, di, uo) is semidet.
:- mode map4_foldl(in(pred(in, out, out, out, out, in, out) is nondet),
    in, out, out, out, out, in, out) is nondet.
:- mode map4_foldl(in(pred(in, out, out, out, out, mdi, muo) is nondet),
    in, out, out, out, out, mdi, muo) is nondet.
:- mode map4_foldl(in(pred(in, out, out, out, out, in, out) is cc_multi),
    in, out, out, out, out, in, out) is cc_multi.
:- mode map4_foldl(in(pred(in, out, out, out, out, di, uo) is cc_multi),
    in, out, out, out, out, di, uo) is cc_multi.

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

    % map_foldr(Pred, InList, OutList, Start, End):
    %
    % Calls Pred on each element of InList, working right-to-left.
    % The second argument of that call will be included in OutList,
    % while the third and fourth will 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 Pred
    % accumulate pieces of information.) The initial value of the accumulator
    % is Start, each call to Pred updates it to the next value, and
    % foldl returns its final value as End.
    %
:- pred map_foldr(pred(L, M, A, A), list(L), list(M), A, A).
:- mode map_foldr(in(pred(in, out, in, out) is det), in, out, in, out)
    is det.
:- mode map_foldr(in(pred(in, out, mdi, muo) is det), in, out, mdi, muo)
    is det.
:- mode map_foldr(in(pred(in, out, di, uo) is det), in, out, di, uo)
    is det.
:- mode map_foldr(in(pred(in, out, in, out) is semidet), in, out, in, out)
    is semidet.
:- mode map_foldr(in(pred(in, out, mdi, muo) is semidet), in, out, mdi, muo)
    is semidet.
:- mode map_foldr(in(pred(in, out, di, uo) is semidet), in, out, di, uo)
    is semidet.
:- mode map_foldr(in(pred(in, in, di, uo) is semidet), in, in, di, uo)
    is semidet.

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

    % map_corresponding_foldl/6:
    %
    % A version of map_corresponding that has an accumulator
    % threaded through it.
    %
:- pred map_corresponding_foldl(pred(A, B, C, D, D),
    list(A), list(B), list(C), D, D).
:- mode map_corresponding_foldl(in(pred(in, in, out, in, out) is det),
    in, in, out, in, out) is det.
:- mode map_corresponding_foldl(in(pred(in, in, out, mdi, muo) is det),
    in, in, out, mdi, muo) is det.
:- mode map_corresponding_foldl(in(pred(in, in, out, di, uo) is det),
    in, in, out, di, uo) is det.
:- mode map_corresponding_foldl(in(pred(in, in, out, in, out) is semidet),
    in, in, out, in, out) is semidet.
:- mode map_corresponding_foldl(in(pred(in, in, out, mdi, muo) is semidet),
    in, in, out, mdi, muo) is semidet.
:- mode map_corresponding_foldl(in(pred(in, in, out, di, uo) is semidet),
    in, in, out, di, uo) is semidet.

    % Same as map_corresponding_foldl/6 but with two accumulators.
    %
:- pred map_corresponding_foldl2(pred(A, B, C, D, D, E, E),
    list(A), list(B), list(C), D, D, E, E).
:- mode map_corresponding_foldl2(
    in(pred(in, in, out, in, out, in, out) is det), in, in, out, in, out,
    in, out) is det.
:- mode map_corresponding_foldl2(
    in(pred(in, in, out, in, out, mdi, muo) is det), in, in, out, in, out,
    mdi, muo) is det.
:- mode map_corresponding_foldl2(
    in(pred(in, in, out, in, out, di, uo) is det), in, in, out, in, out,
    di, uo) is det.
:- mode map_corresponding_foldl2(
    in(pred(in, in, out, in, out, in, out) is semidet), in, in, out, in, out,
    in, out) is semidet.
:- mode map_corresponding_foldl2(
    in(pred(in, in, out, in, out, mdi, muo) is semidet), in, in, out, in, out,
    mdi, muo) is semidet.
:- mode map_corresponding_foldl2(
    in(pred(in, in, out, in, out, di, uo) is semidet), in, in, out, in, out,
    di, uo) is semidet.

    % Same as map_corresponding_foldl/6 but with three accumulators.
    %
:- pred map_corresponding_foldl3(pred(A, B, C, D, D, E, E, F, F),
    list(A), list(B), list(C), D, D, E, E, F, F).
:- mode map_corresponding_foldl3(
    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 map_corresponding_foldl3(
    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 map_corresponding_foldl3(
    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 map_corresponding_foldl3(
    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 map_corresponding_foldl3(
    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 map_corresponding_foldl3(
    in(pred(in, in, out, in, out, in, out, di, uo) is semidet),
    in, in, out, in, out, in, out, di, uo) is semidet.

    % map_corresponding3_foldl/6:
    %
    % A version of map_corresponding3 that has an accumulator
    % threaded through it.
    %
:- pred map_corresponding3_foldl(pred(A, B, C, D, E, E),
    list(A), list(B), list(C), list(D), E, E).
:- mode map_corresponding3_foldl(
    in(pred(in, in, in, out, in, out) is det),
    in, in, in, out, in, out) is det.
:- mode map_corresponding3_foldl(
    in(pred(in, in, in, out, mdi, muo) is det),
    in, in, in, out, mdi, muo) is det.
:- mode map_corresponding3_foldl(
    in(pred(in, in, in, out, di, uo) is det),
    in, in, in, out, di, uo) is det.
:- mode map_corresponding3_foldl(
    in(pred(in, in, in, out, in, out) is semidet),
    in, in, in, out, in, out) is semidet.
:- mode map_corresponding3_foldl(
    in(pred(in, in, in, out, mdi, muo) is semidet),
    in, in, in, out, mdi, muo) is semidet.
:- mode map_corresponding3_foldl(
    in(pred(in, in, in, out, di, uo) is semidet),
    in, in, in, out, di, uo) is semidet.

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

    % filter_map_foldl(Transformer, List, TrueList, Start, End):
    %
    % Takes a predicate with one input argument, one output argument and an
    % accumulator. It is called on each element of List. If the call succeeds,
    % then the output is included in TrueList and the accumulator is updated.
    %
:- pred filter_map_foldl(
    pred(X, Y, A, A)::in(pred(in, out, in, out) is semidet),
    list(X)::in, list(Y)::out, A::in, A::out) is det.

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