mirror of
https://github.com/Mercury-Language/mercury.git
synced 2026-04-15 01:13:30 +00:00
4837 lines
172 KiB
Mathematica
4837 lines
172 KiB
Mathematica
%---------------------------------------------------------------------------%
|
|
% vim: ft=mercury ts=4 sw=4 et
|
|
%---------------------------------------------------------------------------%
|
|
% Copyright (C) 1993-2012 The University of Melbourne.
|
|
% Copyright (C) 2013-2026 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: 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)].
|
|
|
|
% UNDOC_PART_START
|
|
% :- type empty_list(T) =< list(T)
|
|
% ---> [].
|
|
%
|
|
% :- type non_empty_list(T) =< list(T)
|
|
% ---> [T | list(T)].
|
|
%
|
|
% XXX Including the above subtype definitions in the code will mean that
|
|
% every occurrence of the [] and [|] function symbols is ambiguous, in that
|
|
% it could refer to a function symbol in the list type, or in one of the
|
|
% empty_list and non_empty_list types. If you have a clause which has
|
|
% many occurrences of these function symbols, you will exceed the
|
|
% current typechecker's ambiguity limit, which it imposes because every
|
|
% ambiguity doubles the number of type assignments it must keep track of.
|
|
% Until that problem is solved, these subtypes should stay commented out.
|
|
% UNDOC_PART_END
|
|
%---------------------------------------------------------------------------%
|
|
|
|
% 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.
|
|
% NOTE_TO_IMPLEMENTORS CFF :- pragma obsolete(func(head/1), [head/2]).
|
|
:- 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.
|
|
% NOTE_TO_IMPLEMENTORS CFF :- pragma obsolete(func(tail/1), [tail/2]).
|
|
:- 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 if-and-only-if
|
|
% 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_prefix(Prefix, List, Suffix):
|
|
%
|
|
% The same as append(Prefix, Suffix, List), but sometimes
|
|
% this predicate name more clearly expresses the intent of the code, and
|
|
% this argument order can also be useful for higher-order programming.
|
|
%
|
|
:- pred remove_prefix(list(T)::in, list(T)::in, list(T)::out) is semidet.
|
|
|
|
% 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.
|
|
% NOTE_TO_IMPLEMENTORS When we implement rewrite rules,
|
|
% NOTE_TO_IMPLEMENTORS we should change this law to a rewrite rule.
|
|
:- promise all [L, H, T] ( append([H], T, L) <=> L = [H | T] ).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
% length(List) = Length:
|
|
% length(List, Length):
|
|
%
|
|
% True if-and-only-if 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.
|
|
% NOTE_TO_IMPLEMENTORS XXX The current mode checker can't handle this mode.
|
|
% NOTE_TO_IMPLEMENTORS :- mode length(input_list_skel, out) is det.
|
|
|
|
% Does the same job as length, but returns the result as an unsigned int.
|
|
%
|
|
:- func ulength(list(T)) = uint.
|
|
:- pred ulength(list(_T)::in, uint::out) is det.
|
|
|
|
% same_length(ListA, ListB):
|
|
%
|
|
% True if-and-only-if ListA and ListB have the same length,
|
|
% i.e. if-and-only-if 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)).
|
|
% NOTE_TO_IMPLEMENTORS XXX The current mode checker can't handle these modes.
|
|
% NOTE_TO_IMPLEMENTORS :- mode same_length(in, output_list_skel) is det.
|
|
% NOTE_TO_IMPLEMENTORS :- mode same_length(output_list_skel, in) is det.
|
|
:- mode same_length(in, in) is semidet.
|
|
% NOTE_TO_IMPLEMENTORS XXX The current mode checker can't handle these modes.
|
|
% NOTE_TO_IMPLEMENTORS :- mode same_length(input_list_skel, output_list_skel)
|
|
% NOTE_TO_IMPLEMENTORS is det.
|
|
% NOTE_TO_IMPLEMENTORS :- mode same_length(output_list_skel, input_list_skel)
|
|
% NOTE_TO_IMPLEMENTORS is det.
|
|
|
|
% 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 if-and-only-if 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 if-and-only-if 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 if-and-only-if 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 if-and-only-if 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) in the (in, in) mode.
|
|
%
|
|
% 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.
|
|
|
|
% nondet_member(List, Elem):
|
|
%
|
|
% Equivalent to member(Elem, List) in the (out, in) mode.
|
|
%
|
|
% Sometimes you need the arguments in this order, because you want to
|
|
% construct a closure with only the list.
|
|
%
|
|
:- pred nondet_member(list(T)::in, T::out) is nondet.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
% 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.)
|
|
% NOTE_TO_IMPLEMENTORS XXX This pred is identical
|
|
% NOTE_TO_IMPLEMENTORS to index1_of_first_occurrence.
|
|
%
|
|
:- 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.
|
|
% NOTE_TO_IMPLEMENTORS XXX This pred is identical
|
|
% NOTE_TO_IMPLEMENTORS to det_index1_of_first_occurrence.
|
|
%
|
|
:- 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 if-and-only-if 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 if-and-only-if 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 if-and-only-if 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 if-and-only-if 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 if-and-only-if 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 if-and-only-if 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 if-and-only-if 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 if-and-only-if 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 if-and-only-if 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:
|
|
%
|
|
% Succeed if-and-only-if List is List0 with its N'th element
|
|
% replaced with R.
|
|
% Throw an exception if either 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, regardless of whether
|
|
% the later occurrences are next to an earlier occurrence or not.
|
|
%
|
|
:- 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 if-and-only-if 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(T)::in(comparison_pred),
|
|
list(T)::in, list(T)::out) is det.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
% merge(As, Bs) = ABs:
|
|
% merge(Compare, As, Bs) = ABs:
|
|
%
|
|
% Given As and Bs, two lists that must both be sorted in non-descending
|
|
% order according to Compare (or the standard comparison operation, for the
|
|
% versions that do not take a Compare argument), return the list ABs
|
|
% which contains the elements of both lists, and which is also
|
|
% in non-descending order. (Note: non-descending order is just another name
|
|
% for "ascending order but with duplicates permitted".)
|
|
%
|
|
% As and Bs may both contain repeated elements, meaning elements for which
|
|
% comparison returns "equal". Given two equal elements, if they come from
|
|
% the same input list, then they appear in the same sequence in ABs
|
|
% as they do in that list. If they come from different input lists,
|
|
% the element(s) from As will appear before the element(s) from Bs.
|
|
%
|
|
:- func merge(list(T), list(T)) = list(T).
|
|
:- pred merge(list(T)::in, list(T)::in, list(T)::out) is det.
|
|
:- func merge(comparison_func(T), list(T), list(T)) = list(T).
|
|
:- pred merge(comparison_pred(T)::in(comparison_pred),
|
|
list(T)::in, list(T)::in, list(T)::out) is det.
|
|
|
|
% merge_and_remove_dups(As, Bs) = ABs:
|
|
% merge_and_remove_dups(Compare, As, Bs) = Sorted:
|
|
%
|
|
% Versions of the merge operation above that operate on lists with
|
|
% strict ascending order. Neither As nor Bs may contain duplicates,
|
|
% and if an element occurs in both As and Bs, ABs will contain
|
|
% only the element from As.
|
|
%
|
|
:- 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.
|
|
:- func merge_and_remove_dups(comparison_func(T), list(T), list(T))
|
|
= list(T).
|
|
:- pred merge_and_remove_dups(comparison_pred(T)::in(comparison_pred),
|
|
list(T)::in, list(T)::in, list(T)::out) is det.
|
|
|
|
%---------------------%
|
|
|
|
% merge_lists(ListOfLists) = MergedList:
|
|
% merge_lists(Compare, ListOfLists) = MergedList:
|
|
%
|
|
% Given ListOfLists, a list containing zero or more lists that must
|
|
% all be sorted in non-descending order according to Compare
|
|
% (or the standard comparison operation, for the versions that
|
|
% do not take a Compare argument), return the list MergedList
|
|
% which contains the elements of all of the lists in ListOfLists
|
|
% and which is also in non-descending order.
|
|
%
|
|
% Lists in ListOfLists may contain repeated elements, meaning elements
|
|
% for which comparison returns "equal". Given two equal elements,
|
|
% if they come from the same input list, then they appear in the same
|
|
% sequence in MergedList as their containing lists do in ListOfLists.
|
|
% If they come from different input lists, the element from earlier
|
|
% lists in ListOfLists will appear before the element from later lists.
|
|
%
|
|
:- func merge_lists(list(list(T))) = list(T).
|
|
:- pred merge_lists(list(list(T))::in, list(T)::out) is det.
|
|
:- func merge_lists(comparison_func(T), list(list(T))) = list(T).
|
|
:- pred merge_lists(comparison_pred(T)::in(comparison_pred),
|
|
list(list(T))::in, list(T)::out) is det.
|
|
|
|
% merge_lists_and_remove_dups(ListOfLists) = MergedList:
|
|
% merge_lists_and_remove_dups(Compare, ListOfLists) = MergedList:
|
|
%
|
|
% Given ListOfLists, a list containing zero or more lists that must
|
|
% all be sorted in ascending order according to Compare (or the standard
|
|
% comparison operation, for the versions that do not take a Compare
|
|
% argument), return the list MergedList which contains the elements
|
|
% of all of the lists in ListOfLists, and which is also in ascending order.
|
|
%
|
|
% No list in ListOfLists may contain repeated elements, meaning
|
|
% elements for which comparison returns "equal". Given two or more
|
|
% equal elements that all come from different input lists, MergedList
|
|
% will contain the element from the earliest of these lists.
|
|
%
|
|
:- func merge_lists_and_remove_dups(list(list(T))) = list(T).
|
|
:- pred merge_lists_and_remove_dups(list(list(T))::in, list(T)::out) is det.
|
|
:- func merge_lists_and_remove_dups(comparison_func(T), list(list(T)))
|
|
= list(T).
|
|
:- pred merge_lists_and_remove_dups(comparison_pred(T)::in(comparison_pred),
|
|
list(list(T))::in, list(T)::out) is det.
|
|
|
|
%---------------------%
|
|
|
|
% intersect(ListA, ListB) = IntersectList:
|
|
% intersect(ListA, ListB, IntersectList):
|
|
%
|
|
% Given ListA and ListB, two lists that must be sorted in ascending order
|
|
% (without duplicates) according to the standard comparison operation,
|
|
% return the list IntersectList which contains only the elements
|
|
% that occur in *both* ListA and ListB.
|
|
%
|
|
:- func intersect(list(T), list(T)) = list(T).
|
|
:- pred intersect(list(T)::in, list(T)::in, list(T)::out) is det.
|
|
|
|
% intersect_lists(ListOfLists) = IntersectList:
|
|
% intersect_lists(ListOfLists, IntersectList):
|
|
%
|
|
% Given ListOfLists, a list containing zero or more lists that must
|
|
% all be sorted in ascending order (without duplicates) according
|
|
% to the standard comparison operation, return the list IntersectList
|
|
% which contains only the elements from ListOfLists that occur in
|
|
% *all* lists in ListOfLists.
|
|
%
|
|
:- func intersect_lists(list(list(T))) = list(T).
|
|
:- pred intersect_lists(list(list(T))::in, list(T)::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 if-and-only-if 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(T), list(T)) = list(T).
|
|
:- pred sort(comparison_pred(T)::in(comparison_pred), list(T)::in,
|
|
list(T)::out) is det.
|
|
|
|
% sort_and_remove_dups(Compare, Unsorted, Sorted):
|
|
%
|
|
% True if-and-only-if 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(T)::in(comparison_pred),
|
|
list(T)::in, list(T)::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):
|
|
%
|
|
% Split List into a prefix Start of length `min(N, length(List))',
|
|
% and a remainder End. Throw 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):
|
|
%
|
|
% Succeed if-and-only-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):
|
|
%
|
|
% Succeed if-and-only-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 N 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(N, 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(N, List) = Start:
|
|
%
|
|
% Return the first N elements of List as Start. If List has less than
|
|
% N elements, return the entire list. Throw 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):
|
|
%
|
|
% Remove the first N elements of List, and return the remainder as End.
|
|
% Fail 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):
|
|
%
|
|
% Remove the first N elements of List, and return the remainder as End.
|
|
% Throw 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):
|
|
%
|
|
% Split List into two parts, Start and End, where List = Start ++ End.
|
|
% Set Start to the longest prefix of List where Pred succeeds for
|
|
% every element. Set End to be the remainder of 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):
|
|
%
|
|
% Split List into two parts, Start and End, where List = Start ++ End.
|
|
% Set Start to the longest prefix of List where Pred fails for
|
|
% every element. Set End to be the remainder of 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):
|
|
%
|
|
% Versions of take_while(Pred, List, Start, End) that do not return End.
|
|
%
|
|
:- 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_not(Pred, List) = Start:
|
|
% take_while_not(Pred, List, Start):
|
|
%
|
|
% Versions of take_while_not(Pred, List, Start, End) that
|
|
% do not return End.
|
|
%
|
|
:- 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:
|
|
% drop_while(Pred, List, End):
|
|
%
|
|
% Versions of take_while(Pred, List, Start, End) that do not return Start.
|
|
%
|
|
:- 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:
|
|
%
|
|
% Return as List a list containing Count copies of Elem.
|
|
%
|
|
:- func duplicate(int, T) = list(T).
|
|
:- pred duplicate(int::in, T::in, list(T)::out) is det.
|
|
|
|
% all_same(List):
|
|
%
|
|
% Succeed if-and-only-if all elements of List are the same.
|
|
%
|
|
:- pred all_same(list(T)::in) is semidet.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
% condense(ListOfLists) = List:
|
|
%
|
|
% Return as List the concatenation of all the lists in ListOfLists.
|
|
%
|
|
:- func condense(list(list(T))) = list(T).
|
|
:- pred condense(list(list(T))::in, list(T)::out) is det.
|
|
|
|
% chunk(List, ChunkSize) = Chunks:
|
|
%
|
|
% Break List 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 will be 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):
|
|
%
|
|
% Succeed if-and-only-if 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(T)::in(pred(in) is semidet), list(T)::in,
|
|
T::out) is semidet.
|
|
|
|
% any_true(Pred, List):
|
|
%
|
|
% Succeeds if-and-only-if Pred succeeds for at least one element of List.
|
|
% Same as `not all_false(Pred, List)'.
|
|
%
|
|
:- pred any_true(pred(T)::in(pred(in) is semidet), list(T)::in) is semidet.
|
|
|
|
% any_false(Pred, List):
|
|
%
|
|
% Succeeds if-and-only-if Pred fails for at least one element of List.
|
|
% Same as `not all_true(Pred, List)'.
|
|
%
|
|
:- pred any_false(pred(T)::in(pred(in) is semidet), list(T)::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(T)::in(pred(in) is semidet), list(T)::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(T)::in(pred(in) is semidet), list(T)::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(T1, T2)::in(pred(in, in) is semidet),
|
|
list(T1)::in, list(T2)::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(T1, T2)::in(pred(in, in) is semidet),
|
|
list(T1)::in, list(T2)::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 if-and-only-if
|
|
% Pred(X) is true.
|
|
%
|
|
:- func filter(pred(T)::in(pred(in) is semidet), list(T)::in)
|
|
= (list(T)::out) is det.
|
|
:- pred filter(pred(T)::in(pred(in) is semidet), list(T)::in,
|
|
list(T)::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 if-and-only-if
|
|
% Pred(X) is true, and includes X in FalseList if-and-only-if
|
|
% Pred(X) is false.
|
|
%
|
|
:- pred filter(pred(T)::in(pred(in) is semidet), list(T)::in,
|
|
list(T)::out, list(T)::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 if-and-only-if
|
|
% Pred(X) is false.
|
|
%
|
|
:- func negated_filter(pred(T)::in(pred(in) is semidet), list(T)::in)
|
|
= (list(T)::out) is det.
|
|
:- pred negated_filter(pred(T)::in(pred(in) is semidet), list(T)::in,
|
|
list(T)::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(T1) = T2)::in((func(in) = out) is semidet),
|
|
list(T1)::in) = (list(T2)::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 X of List. If Transformer(X, Y) succeeds,
|
|
% then it includes Y in TrueList.
|
|
%
|
|
:- pred filter_map(pred(T1, T2)::in(pred(in, out) is semidet),
|
|
list(T1)::in, list(T2)::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 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(T1, T2)::in(pred(in, out) is semidet),
|
|
list(T1)::in, list(T2)::out, list(T1)::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(T1, T2)::in(pred(in, out) is semidet),
|
|
list(T1)::in, T2::out) is semidet.
|
|
|
|
% find_first_map2(Transformer, List, FirstTrueA, FirstTrueB):
|
|
%
|
|
% Same as find_first_map, except with two outputs.
|
|
%
|
|
:- pred find_first_map2(pred(T, A, B)::in(pred(in, out, out) is semidet),
|
|
list(T)::in, A::out, B::out) is semidet.
|
|
|
|
% find_first_map3(Transformer, List, FirstTrueA, FirstTrueB, FirstTrueC):
|
|
%
|
|
% Same as find_first_map, except with three outputs.
|
|
%
|
|
:- pred find_first_map3(
|
|
pred(T, A, B, C)::in(pred(in, out, out, out) is semidet),
|
|
list(T)::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(T1) = T2, list(T1)) = list(T2).
|
|
:- pred map(pred(T1, T2), list(T1), list(T2)).
|
|
:- 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, M8) 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 eight 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 as 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 as 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 as 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
|
|
% foldr 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 foldr, 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 three accumulators.
|
|
% Although no more expressive than foldr, 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 job 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 job 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
|
|
% map_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
|
|
% map_foldr 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(T1, T2, A, A)::in(pred(in, out, in, out) is semidet),
|
|
list(T1)::in, list(T2)::out, A::in, A::out) is det.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%---------------------------------------------------------------------------%
|
|
|
|
:- implementation.
|
|
|
|
% Everything below here is not intended to be part of the public interface,
|
|
% and will not be included in the Mercury library reference manual.
|
|
|
|
:- interface.
|
|
|
|
% Some declarations for complicated modes using lists.
|
|
%
|
|
% See our comment above regarding incomplete support for partial
|
|
% instantiation.
|
|
|
|
:- inst list_skel == list_skel(free).
|
|
|
|
:- mode in_list_skel == list_skel >> list_skel.
|
|
:- mode out_list_skel == free >> list_skel.
|
|
:- mode list_skel_out == list_skel >> ground.
|
|
|
|
% These modes are useful for passing around lists of higher order terms,
|
|
% since they have complicated insts which are not correctly approximated
|
|
% by "ground".
|
|
%
|
|
% These could be made public (not deprecated) however I prefer to
|
|
% encourage the in(list_skel(I)) and out(list_skel(I)) style syntax.
|
|
%
|
|
:- mode list_skel_in(I) == list_skel(I) >> list_skel(I).
|
|
:- mode list_skel_out(I) == free >> list_skel(I).
|
|
|
|
% This is the same as the usual forward mode of append, but preserves
|
|
% any extra information available in the input arguments.
|
|
% NOTE_TO_IMPLEMENTORS If Mercury recorded the mode and determinism
|
|
% NOTE_TO_IMPLEMENTORS information of higher order types in the *types*
|
|
% NOTE_TO_IMPLEMENTORS of higher order variables instead of in their
|
|
% NOTE_TO_IMPLEMENTORS *insts*, this function would not be needed.
|
|
%
|
|
:- func inst_preserving_append(list(T)::in(list_skel(I =< ground)),
|
|
list(T)::in(list_skel(I =< ground))) =
|
|
(list(T)::out(list_skel(I =< ground))) is det.
|
|
|
|
:- func inst_preserving_condense(
|
|
list(list(T))::in(list_skel(list_skel(I =< ground)))) =
|
|
(list(T)::out(list_skel(I =< ground))) is det.
|
|
|
|
% This is the same as the usual forward mode of reverse, but preserves
|
|
% any extra information available in the input argument.
|
|
%
|
|
:- func inst_preserving_reverse(list(T)::in(list_skel(I =< ground))) =
|
|
(list(T)::out(list_skel(I =< ground))) is det.
|
|
|
|
:- import_module term. % for var/1.
|
|
|
|
:- pragma type_spec(list.merge(in, in, out), T = var(_)).
|
|
|
|
:- pragma type_spec(list.merge_and_remove_dups(in, in, out), T = var(_)).
|
|
:- pragma type_spec(list.merge_and_remove_dups(in, in) = out, T = var(_)).
|
|
|
|
:- pragma type_spec(pred(list.remove_adjacent_dups/2), T = var(_)).
|
|
:- pragma type_spec(func(list.remove_adjacent_dups/1), T = var(_)).
|
|
|
|
:- pragma type_spec(list.member(in, in), T = var(_)).
|
|
|
|
:- pragma type_spec(pred(list.sort_and_remove_dups/2), T = var(_)).
|
|
:- pragma type_spec(func(list.sort_and_remove_dups/1), T = var(_)).
|
|
|
|
:- pragma type_spec(list.sort(in, out), T = var(_)).
|
|
:- pragma type_spec(list.sort(in) = out, T = var(_)).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
:- implementation.
|
|
|
|
:- import_module int.
|
|
:- import_module require.
|
|
:- import_module set_tree234.
|
|
:- import_module string.
|
|
:- import_module uint.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
is_empty([]).
|
|
|
|
is_non_empty([_ | _]).
|
|
|
|
is_not_empty([_ | _]).
|
|
|
|
is_singleton([X], X).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
head([H | _]) = H.
|
|
|
|
head([H | _], H).
|
|
|
|
det_head([]) = _ :-
|
|
unexpected($pred, "empty list").
|
|
det_head([H | _]) = H.
|
|
|
|
det_head([], _) :-
|
|
unexpected($pred, "empty list").
|
|
det_head([H | _], H).
|
|
|
|
tail([_ | T]) = T.
|
|
|
|
tail([_ | T], T).
|
|
|
|
det_tail([]) = _ :-
|
|
unexpected($pred, "empty list").
|
|
det_tail([_ | T]) = T.
|
|
|
|
det_tail([], _) :-
|
|
unexpected($pred, "empty list").
|
|
det_tail([_ | T], T).
|
|
|
|
det_head_tail([], _, _) :-
|
|
unexpected($pred, "empty list").
|
|
det_head_tail([H | T], H, T).
|
|
|
|
cons(H, T) = [H | T].
|
|
|
|
cons(H, T, [H | T]).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
append([], Ys, Ys).
|
|
append([X | Xs], Ys, [X | Zs]) :-
|
|
list.append(Xs, Ys, Zs).
|
|
|
|
append(Xs, Ys) = Zs :-
|
|
list.append(Xs, Ys, Zs).
|
|
|
|
L1 ++ L2 = list.append(L1, L2).
|
|
|
|
remove_prefix([], ListB, LeftOverB) :-
|
|
LeftOverB = ListB.
|
|
remove_prefix([HeadA | TailA], [HeadB | TailB], LeftOverB) :-
|
|
HeadA = HeadB,
|
|
remove_prefix(TailA, TailB, LeftOverB).
|
|
|
|
remove_suffix(List, Suffix, Prefix) :-
|
|
list.length(List, ListLength),
|
|
list.length(Suffix, SuffixLength),
|
|
PrefixLength = ListLength - SuffixLength,
|
|
list.split_list(PrefixLength, List, Prefix, Suffix).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
% Note - it is not possible to write a version of list.length/1
|
|
% in pure Mercury that works in both directions unless you make it semidet
|
|
% rather than det.
|
|
|
|
length(L) = uint.cast_to_int(N) :-
|
|
ulength_acc(L, 0u, N).
|
|
|
|
length(L, uint.cast_to_int(N)) :-
|
|
ulength_acc(L, 0u, N).
|
|
|
|
ulength(L) = N :-
|
|
ulength_acc(L, 0u, N).
|
|
|
|
ulength(L, N) :-
|
|
ulength_acc(L, 0u, N).
|
|
|
|
:- pred ulength_acc(list(T), uint, uint).
|
|
:- mode ulength_acc(in, in, out) is det.
|
|
|
|
ulength_acc([], N, N).
|
|
ulength_acc([_ | Tail], N0, N) :-
|
|
N1 = N0 + 1u,
|
|
ulength_acc(Tail, N1, N).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
same_length([], []).
|
|
same_length([_ | TailA], [_ | TailB]) :-
|
|
list.same_length(TailA, TailB).
|
|
|
|
same_length3([], [], []).
|
|
same_length3([_ | TailA], [_ | TailB], [_ | TailC]) :-
|
|
list.same_length3(TailA, TailB, TailC).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
member(X, [X | _]).
|
|
member(X, [_ | Xs]) :-
|
|
list.member(X, Xs).
|
|
|
|
member(Element, List, SubList) :-
|
|
SubList = [Element | _],
|
|
list.append(_, SubList, List).
|
|
|
|
member_index0(X, [X | _], 0).
|
|
member_index0(X, [_ | Xs], Index + 1) :-
|
|
list.member_index0(X, Xs, Index).
|
|
|
|
member_indexes0(X, List, Indexes) :-
|
|
list.member_indexes0_loop(X, 0, List, Indexes).
|
|
|
|
:- pred member_indexes0_loop(T::in, int::in, list(T)::in,
|
|
list(int)::out) is det.
|
|
|
|
member_indexes0_loop(_X, _I, [], []).
|
|
member_indexes0_loop(X, I, [H | T], Indexes) :-
|
|
list.member_indexes0_loop(X, I + 1, T, IndexesTail),
|
|
( if X = H then
|
|
Indexes = [I | IndexesTail]
|
|
else
|
|
Indexes = IndexesTail
|
|
).
|
|
|
|
contains(List, Elem) :-
|
|
list.member(Elem, List).
|
|
|
|
nondet_member(List, Elem) :-
|
|
list.member(Elem, List).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
index0([X | Xs], N, Elem) :-
|
|
( if N = 0 then
|
|
Elem = X
|
|
else
|
|
list.index0(Xs, N - 1, Elem)
|
|
).
|
|
|
|
index1(List, N, Elem) :-
|
|
list.index0(List, N - 1, Elem).
|
|
|
|
det_index0(Xs, N) = A :-
|
|
list.det_index0(Xs, N, A).
|
|
|
|
det_index0(List, N, Elem) :-
|
|
( if list.index0(List, N, Elem0) then
|
|
Elem = Elem0
|
|
else
|
|
unexpected($pred, "index out of range")
|
|
).
|
|
|
|
det_index1(Xs, N) = A :-
|
|
list.det_index1(Xs, N, A).
|
|
|
|
det_index1(Xs, N, Elem) :-
|
|
list.det_index0(Xs, N - 1, Elem).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
nth_member_search(Xs, SearchX, N) :-
|
|
list.index1_of_first_occurrence(Xs, SearchX, N).
|
|
|
|
nth_member_lookup(Xs, SearchX, N) :-
|
|
N = list.det_index1_of_first_occurrence(Xs, SearchX).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
index0_of_first_occurrence(Xs, SearchX, Index) :-
|
|
list.index0_of_first_occurrence_loop(Xs, SearchX, 0, Index).
|
|
|
|
:- pred index0_of_first_occurrence_loop(list(T)::in, T::in,
|
|
int::in, int::out) is semidet.
|
|
|
|
index0_of_first_occurrence_loop([X | Xs], SearchX, CurIndex, Index) :-
|
|
( if X = SearchX then
|
|
Index = CurIndex
|
|
else
|
|
list.index0_of_first_occurrence_loop(Xs, SearchX, CurIndex + 1, Index)
|
|
).
|
|
|
|
index1_of_first_occurrence(Xs, SearchX, Index0 + 1) :-
|
|
list.index0_of_first_occurrence(Xs, SearchX, Index0).
|
|
|
|
det_index0_of_first_occurrence(Xs, SearchX) = Index :-
|
|
( if list.index0_of_first_occurrence(Xs, SearchX, Index0) then
|
|
Index = Index0
|
|
else
|
|
unexpected($pred, "item not found")
|
|
).
|
|
|
|
det_index1_of_first_occurrence(Xs, SearchX) = Index :-
|
|
( if list.index1_of_first_occurrence(Xs, SearchX, Index0) then
|
|
Index = Index0
|
|
else
|
|
unexpected($pred, "item not found")
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
% reverse(A, B) <=> reverse(B, A).
|
|
:- pragma promise_equivalent_clauses(pred(list.reverse/2)).
|
|
|
|
reverse(L0::in, L::out) :-
|
|
list.reverse_prepend(L0, [], L).
|
|
reverse(L::out, L0::in) :-
|
|
list.reverse_prepend(L0, [], L).
|
|
|
|
reverse(Xs) = Ys :-
|
|
list.reverse(Xs, Ys).
|
|
|
|
reverse_prepend([], L, L).
|
|
reverse_prepend([X | Xs], L0, L) :-
|
|
list.reverse_prepend(Xs, [X | L0], L).
|
|
|
|
reverse_prepend(Xs, Ys) = Zs :-
|
|
list.reverse_prepend(Xs, Ys, Zs).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
insert(Elem, List0, List) :-
|
|
list.delete(List, Elem, List0).
|
|
|
|
delete([X | Xs], ToDelete, Xs) :-
|
|
X = ToDelete.
|
|
delete([X | Xs], ToDelete, [X | DXs]) :-
|
|
list.delete(Xs, ToDelete, DXs).
|
|
|
|
delete_first([X | Xs], ToDelete, DXs) :-
|
|
( if X = ToDelete then
|
|
DXs = Xs
|
|
else
|
|
list.delete_first(Xs, ToDelete, DXs0),
|
|
DXs = [X | DXs0]
|
|
).
|
|
|
|
delete_all(Xs, A) = DXs :-
|
|
list.delete_all(Xs, A, DXs).
|
|
|
|
delete_all([], _, []).
|
|
delete_all([X | Xs], ToDelete, DXs) :-
|
|
( if X = ToDelete then
|
|
list.delete_all(Xs, ToDelete, DXs)
|
|
else
|
|
list.delete_all(Xs, ToDelete, DXs0),
|
|
DXs = [X | DXs0]
|
|
).
|
|
|
|
delete_nth([X | Xs], N, Result) :-
|
|
( if N > 1 then
|
|
delete_nth(Xs, N - 1, ResultTail),
|
|
Result = [X | ResultTail]
|
|
else
|
|
Result = Xs
|
|
).
|
|
|
|
delete_elems(Xs, ToDeletes) = DXs :-
|
|
list.delete_elems(Xs, ToDeletes, DXs).
|
|
|
|
delete_elems(Xs, [], Xs).
|
|
delete_elems(Xs, [ToDelete | ToDeletes], DDXs) :-
|
|
list.delete_all(Xs, ToDelete, DXs),
|
|
list.delete_elems(DXs, ToDeletes, DDXs).
|
|
|
|
sublist([], _).
|
|
sublist([SH | ST], [FH | FT]) :-
|
|
( if SH = FH then
|
|
list.sublist(ST, FT)
|
|
else
|
|
list.sublist([SH | ST], FT)
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
replace([X | Xs0], From, To, [To | Xs0]) :-
|
|
X = From.
|
|
replace([X | Xs0], From, To, [X | Xs]) :-
|
|
list.replace(Xs0, From, To, Xs).
|
|
|
|
replace_first([X | Xs], From, To, RXs) :-
|
|
( if X = From then
|
|
RXs = [To | Xs]
|
|
else
|
|
list.replace_first(Xs, From, To, RXs0),
|
|
RXs = [X | RXs0]
|
|
).
|
|
|
|
replace_all(Xs, A, B) = RXs :-
|
|
list.replace_all(Xs, A, B, RXs).
|
|
|
|
replace_all([], _, _, []).
|
|
replace_all([X | Xs], From, To, RXs) :-
|
|
( if X = From then
|
|
list.replace_all(Xs, From, To, RXs0),
|
|
RXs = [To | RXs0]
|
|
else
|
|
list.replace_all(Xs, From, To, RXs0),
|
|
RXs = [X | RXs0]
|
|
).
|
|
|
|
replace_nth(Xs, N, To, RXs) :-
|
|
N > 0,
|
|
list.replace_nth_loop(Xs, N, To, RXs).
|
|
|
|
:- pred replace_nth_loop(list(T)::in, int::in, T::in, list(T)::out)
|
|
is semidet.
|
|
|
|
replace_nth_loop([X | Xs], N, To, RXs) :-
|
|
( if N > 1 then
|
|
list.replace_nth_loop(Xs, N - 1, To, RXs0),
|
|
RXs = [X | RXs0]
|
|
else if N = 1 then
|
|
RXs = [To | Xs]
|
|
else
|
|
fail
|
|
).
|
|
|
|
det_replace_nth(Xs, N, To) = RXs :-
|
|
list.det_replace_nth(Xs, N, To, RXs).
|
|
|
|
det_replace_nth(Xs, N, To, RXs) :-
|
|
( if N > 0 then
|
|
( if list.replace_nth_loop(Xs, N, To, RXsPrime) then
|
|
RXs = RXsPrime
|
|
else
|
|
unexpected($pred,
|
|
"Cannot replace element whose index position " ++
|
|
"is past the end of the list")
|
|
)
|
|
else
|
|
unexpected($pred,
|
|
"Cannot replace element whose index position is less than 1.")
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
Lo `..` Hi = List :-
|
|
successive_integers(Lo, Hi, [], List).
|
|
|
|
:- pred successive_integers(int::in, int::in, list(int)::in, list(int)::out)
|
|
is det.
|
|
|
|
successive_integers(Lo, Hi, !Ints) :-
|
|
( if Lo =< Hi then
|
|
!:Ints = [Hi | !.Ints],
|
|
successive_integers(Lo, Hi - 1, !Ints)
|
|
else
|
|
true
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
series(I, OK, Succ) = Series :-
|
|
% In order to ensure that our stack consumption is constant,
|
|
% not linear, we build the series "backwards" and then reverse it.
|
|
series_acc(I, OK, Succ, [], RevSeries),
|
|
reverse(RevSeries, Series).
|
|
|
|
:- pred series_acc(T::in,
|
|
pred(T)::in(pred(in) is semidet),
|
|
(func(T) = T)::in(func(in) = out is det),
|
|
list(T)::in, list(T)::out) is det.
|
|
|
|
series_acc(I, OK, Succ, !RevSeries) :-
|
|
( if OK(I) then
|
|
!:RevSeries = [I | !.RevSeries],
|
|
series_acc(Succ(I), OK, Succ, !RevSeries)
|
|
else
|
|
true
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
remove_dups(Xs) = FilteredXs :-
|
|
remove_dups(Xs, FilteredXs).
|
|
|
|
remove_dups(Xs, FilteredXs) :-
|
|
remove_dups_loop(Xs, set_tree234.init, FilteredXs).
|
|
|
|
:- pred remove_dups_loop(list(T)::in, set_tree234(T)::in, list(T)::out)
|
|
is det.
|
|
|
|
remove_dups_loop([], _SoFar, []).
|
|
remove_dups_loop([X | Xs], SoFar0, FilteredXs) :-
|
|
( if set_tree234.contains(SoFar0, X) then
|
|
remove_dups_loop(Xs, SoFar0, FilteredXs)
|
|
else
|
|
set_tree234.insert(X, SoFar0, SoFar),
|
|
remove_dups_loop(Xs, SoFar, FilteredXsTail),
|
|
FilteredXs = [X | FilteredXsTail]
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
remove_adjacent_dups(Xs) = FilteredXs :-
|
|
list.remove_adjacent_dups(Xs, FilteredXs).
|
|
|
|
remove_adjacent_dups([], []).
|
|
remove_adjacent_dups([X | Xs], FilteredXs) :-
|
|
remove_adjacent_dups_loop(X, Xs, FilteredXs).
|
|
|
|
:- pred remove_adjacent_dups_loop(T::in, list(T)::in, list(T)::out) is det.
|
|
:- pragma type_spec(pred(list.remove_adjacent_dups_loop/3), T = var(_)).
|
|
|
|
remove_adjacent_dups_loop(X, [], [X]).
|
|
remove_adjacent_dups_loop(X0, [X1 | Xs], FilteredXs) :-
|
|
( if X0 = X1 then
|
|
remove_adjacent_dups_loop(X0, Xs, FilteredXs)
|
|
else
|
|
remove_adjacent_dups_loop(X1, Xs, FilteredXsTail),
|
|
FilteredXs = [X0 | FilteredXsTail]
|
|
).
|
|
|
|
remove_adjacent_dups(_, [], []).
|
|
remove_adjacent_dups(ComparePred, [X | Xs], FilteredXs) :-
|
|
remove_adjacent_dups_loop(ComparePred, X, Xs, FilteredXs).
|
|
|
|
:- pred remove_adjacent_dups_loop(comparison_pred(T)::in(comparison_pred),
|
|
T::in, list(T)::in, list(T)::out) is det.
|
|
|
|
remove_adjacent_dups_loop(_, X, [], [X]).
|
|
remove_adjacent_dups_loop(ComparePred, X0, [X1 | Xs], FilteredXs) :-
|
|
( if ComparePred(X0, X1, (=)) then
|
|
remove_adjacent_dups_loop(ComparePred, X0, Xs, FilteredXs)
|
|
else
|
|
remove_adjacent_dups_loop(ComparePred, X1, Xs, FilteredXsTail),
|
|
FilteredXs = [X0 | FilteredXsTail]
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
merge(As, Bs) = Cs :-
|
|
list.merge(As, Bs, Cs).
|
|
|
|
merge([], [], []).
|
|
merge([], [B | Bs], [B | Bs]).
|
|
merge([A | As], [], [A | As]).
|
|
merge([A | As], [B | Bs], Cs) :-
|
|
% This code *is* tail recursive with --optimize-constructor-last-call.
|
|
( if compare(>, A, B) then
|
|
list.merge([A | As], Bs, Cs0),
|
|
Cs = [B | Cs0]
|
|
else
|
|
% If compare((=), A, B), take A first.
|
|
list.merge(As, [B | Bs], Cs0),
|
|
Cs = [A | Cs0]
|
|
).
|
|
|
|
merge(CompareFunc, As, Bs) = Cs :-
|
|
ComparePred =
|
|
( pred(A::in, B::in, Res::out) is det :- Res = CompareFunc(A, B) ),
|
|
list.merge(ComparePred, As, Bs, Cs).
|
|
|
|
merge(_ComparePred, [], [], []).
|
|
merge(_ComparePred, [], [Y | Ys], [Y | Ys]).
|
|
merge(_ComparePred, [A | As], [], [A | As]).
|
|
merge(ComparePred, [A | As], [Y | Ys], Cs) :-
|
|
% This code *is* tail recursive with --optimize-constructor-last-call.
|
|
( if ComparePred(A, Y, (>)) then
|
|
list.merge(ComparePred, [A | As], Ys, CsTail),
|
|
Cs = [Y | CsTail]
|
|
else
|
|
list.merge(ComparePred, As, [Y | Ys], CsTail),
|
|
Cs = [A | CsTail]
|
|
).
|
|
|
|
%---------------------%
|
|
|
|
merge_and_remove_dups(As, Bs) = Zs :-
|
|
list.merge_and_remove_dups(As, Bs, Zs).
|
|
|
|
merge_and_remove_dups([], [], []).
|
|
merge_and_remove_dups([], [B | Bs], [B | Bs]).
|
|
merge_and_remove_dups([A | As], [], [A | As]).
|
|
merge_and_remove_dups([A | As], [B | Bs], Cs) :-
|
|
% This code *is* tail recursive with --optimize-constructor-last-call.
|
|
compare(Res, A, B),
|
|
(
|
|
Res = (<),
|
|
merge_and_remove_dups(As, [B | Bs], CsTail),
|
|
Cs = [A | CsTail]
|
|
;
|
|
Res = (=),
|
|
merge_and_remove_dups(As, Bs, CsTail),
|
|
Cs = [A | CsTail]
|
|
;
|
|
Res = (>),
|
|
merge_and_remove_dups([A | As], Bs, CsTail),
|
|
Cs = [B | CsTail]
|
|
).
|
|
|
|
merge_and_remove_dups(CompareFunc, As, Bs) = Cs :-
|
|
ComparePred =
|
|
( pred(A::in, B::in, Res::out) is det :- Res = CompareFunc(A, B) ),
|
|
merge_and_remove_dups(ComparePred, As, Bs, Cs).
|
|
|
|
merge_and_remove_dups(_ComparePred, [], [], []).
|
|
merge_and_remove_dups(_ComparePred, [], [B | Bs], [B | Bs]).
|
|
merge_and_remove_dups(_ComparePred, [A | As], [], [A | As]).
|
|
merge_and_remove_dups(ComparePred, [A | As], [B | Bs], Cs) :-
|
|
% This code *is* tail recursive with --optimize-constructor-last-call.
|
|
ComparePred(A, B, Res),
|
|
(
|
|
Res = (<),
|
|
merge_and_remove_dups(ComparePred, As, [B | Bs], CsTail),
|
|
Cs = [A | CsTail]
|
|
;
|
|
Res = (=),
|
|
merge_and_remove_dups(ComparePred, As, Bs, CsTail),
|
|
Cs = [A | CsTail]
|
|
;
|
|
Res = (>),
|
|
merge_and_remove_dups(ComparePred, [A | As], Bs, CsTail),
|
|
Cs = [B | CsTail]
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
merge_lists(Lists) = MergedList :-
|
|
merge_lists(Lists, MergedList).
|
|
|
|
merge_lists(Lists, MergedList) :-
|
|
(
|
|
Lists = [],
|
|
MergedList = []
|
|
;
|
|
Lists = [List1],
|
|
MergedList = List1
|
|
;
|
|
Lists = [List1, List2],
|
|
merge(List1, List2, MergedList)
|
|
;
|
|
Lists = [List1, List2, List3],
|
|
merge(List1, List2, List12),
|
|
merge(List12, List3, MergedList)
|
|
;
|
|
Lists = [_, _, _, _ | _],
|
|
merge_lists_fixpoint(Lists, MergedList)
|
|
).
|
|
|
|
:- pred merge_lists_fixpoint(list(list(T))::in, list(T)::out) is det.
|
|
|
|
merge_lists_fixpoint(Lists, MergedList) :-
|
|
merge_lists_pass(Lists, [], RevMergedLists),
|
|
% This reverse is not actually required; MergedLists = RevMergedLists
|
|
% should also work.
|
|
list.reverse(RevMergedLists, MergedLists),
|
|
(
|
|
MergedLists = [],
|
|
unexpected($pred, "MergedLists is empty")
|
|
;
|
|
MergedLists = [MergedList]
|
|
;
|
|
MergedLists = [_, _ | _],
|
|
merge_lists_fixpoint(MergedLists, MergedList)
|
|
).
|
|
|
|
:- pred merge_lists_pass(list(list(T))::in,
|
|
list(list(T))::in, list(list(T))::out) is det.
|
|
|
|
merge_lists_pass(Lists, !RevMergedLists) :-
|
|
(
|
|
Lists = []
|
|
;
|
|
Lists = [List1],
|
|
!:RevMergedLists = [List1 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2],
|
|
merge(List1, List2, List12),
|
|
!:RevMergedLists = [List12 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2, List3],
|
|
merge(List1, List2, List12),
|
|
merge(List12, List3, List123),
|
|
!:RevMergedLists = [List123 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2, List3, List4 | MoreLists],
|
|
merge(List1, List2, List12),
|
|
merge(List3, List4, List34),
|
|
merge(List12, List34, List1234),
|
|
!:RevMergedLists = [List1234 | !.RevMergedLists],
|
|
merge_lists_pass(MoreLists, !RevMergedLists)
|
|
).
|
|
|
|
%---------------------%
|
|
|
|
merge_lists(CompareFunc, Lists) = MergedList :-
|
|
ComparePred =
|
|
( pred(A::in, B::in, Res::out) is det :- Res = CompareFunc(A, B) ),
|
|
merge_lists(ComparePred, Lists, MergedList).
|
|
|
|
merge_lists(ComparePred, Lists, MergedList) :-
|
|
(
|
|
Lists = [],
|
|
MergedList = []
|
|
;
|
|
Lists = [List1],
|
|
MergedList = List1
|
|
;
|
|
Lists = [List1, List2],
|
|
merge(ComparePred, List1, List2, MergedList)
|
|
;
|
|
Lists = [List1, List2, List3],
|
|
merge(ComparePred, List1, List2, List12),
|
|
merge(ComparePred, List12, List3, MergedList)
|
|
;
|
|
Lists = [_, _, _, _ | _],
|
|
merge_lists_fixpoint(ComparePred, Lists, MergedList)
|
|
).
|
|
|
|
:- pred merge_lists_fixpoint(comparison_pred(T)::in(comparison_pred),
|
|
list(list(T))::in, list(T)::out) is det.
|
|
|
|
merge_lists_fixpoint(ComparePred, Lists, MergedList) :-
|
|
merge_lists_pass(ComparePred, Lists, [], RevMergedLists),
|
|
% This reverse is required to ensure that for any items that occur
|
|
% in more than one list, we pick the item that occurs in the first one.
|
|
list.reverse(RevMergedLists, MergedLists),
|
|
(
|
|
MergedLists = [],
|
|
unexpected($pred, "MergedLists is empty")
|
|
;
|
|
MergedLists = [MergedList]
|
|
;
|
|
MergedLists = [_, _ | _],
|
|
merge_lists_fixpoint(ComparePred, MergedLists, MergedList)
|
|
).
|
|
|
|
:- pred merge_lists_pass(comparison_pred(T)::in(comparison_pred),
|
|
list(list(T))::in, list(list(T))::in, list(list(T))::out) is det.
|
|
|
|
merge_lists_pass(ComparePred, Lists, !RevMergedLists) :-
|
|
(
|
|
Lists = []
|
|
;
|
|
Lists = [List1],
|
|
!:RevMergedLists = [List1 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2],
|
|
merge(ComparePred, List1, List2, List12),
|
|
!:RevMergedLists = [List12 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2, List3],
|
|
merge(ComparePred, List1, List2, List12),
|
|
merge(ComparePred, List12, List3, List123),
|
|
!:RevMergedLists = [List123 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2, List3, List4 | MoreLists],
|
|
merge(ComparePred, List1, List2, List12),
|
|
merge(ComparePred, List3, List4, List34),
|
|
merge(ComparePred, List12, List34, List1234),
|
|
!:RevMergedLists = [List1234 | !.RevMergedLists],
|
|
merge_lists_pass(ComparePred, MoreLists, !RevMergedLists)
|
|
).
|
|
|
|
%---------------------%
|
|
|
|
merge_lists_and_remove_dups(Lists) = MergedList :-
|
|
merge_lists_and_remove_dups(Lists, MergedList).
|
|
|
|
merge_lists_and_remove_dups(Lists, MergedList) :-
|
|
(
|
|
Lists = [],
|
|
MergedList = []
|
|
;
|
|
Lists = [List1],
|
|
MergedList = List1
|
|
;
|
|
Lists = [List1, List2],
|
|
merge_and_remove_dups(List1, List2, MergedList)
|
|
;
|
|
Lists = [List1, List2, List3],
|
|
merge_and_remove_dups(List1, List2, List12),
|
|
merge_and_remove_dups(List12, List3, MergedList)
|
|
;
|
|
Lists = [_, _, _, _ | _],
|
|
merge_lists_and_remove_dups_fixpoint(Lists, MergedList)
|
|
).
|
|
|
|
:- pred merge_lists_and_remove_dups_fixpoint(list(list(T))::in, list(T)::out)
|
|
is det.
|
|
|
|
merge_lists_and_remove_dups_fixpoint(Lists, MergedList) :-
|
|
merge_lists_and_remove_dups_pass(Lists, [], RevMergedLists),
|
|
% This reverse is not actually required; MergedLists = RevMergedLists
|
|
% should also work.
|
|
list.reverse(RevMergedLists, MergedLists),
|
|
(
|
|
MergedLists = [],
|
|
unexpected($pred, "MergedLists is empty")
|
|
;
|
|
MergedLists = [MergedList]
|
|
;
|
|
MergedLists = [_, _ | _],
|
|
merge_lists_and_remove_dups_fixpoint(MergedLists, MergedList)
|
|
).
|
|
|
|
:- pred merge_lists_and_remove_dups_pass(
|
|
list(list(T))::in, list(list(T))::in, list(list(T))::out) is det.
|
|
|
|
merge_lists_and_remove_dups_pass(Lists, !RevMergedLists) :-
|
|
(
|
|
Lists = []
|
|
;
|
|
Lists = [List1],
|
|
!:RevMergedLists = [List1 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2],
|
|
merge_and_remove_dups(List1, List2, List12),
|
|
!:RevMergedLists = [List12 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2, List3],
|
|
merge_and_remove_dups(List1, List2, List12),
|
|
merge_and_remove_dups(List12, List3, List123),
|
|
!:RevMergedLists = [List123 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2, List3, List4 | MoreLists],
|
|
merge_and_remove_dups(List1, List2, List12),
|
|
merge_and_remove_dups(List3, List4, List34),
|
|
merge_and_remove_dups(List12, List34, List1234),
|
|
!:RevMergedLists = [List1234 | !.RevMergedLists],
|
|
merge_lists_and_remove_dups_pass(MoreLists, !RevMergedLists)
|
|
).
|
|
|
|
%---------------------%
|
|
|
|
merge_lists_and_remove_dups(CompareFunc, Lists) = MergedList :-
|
|
ComparePred =
|
|
( pred(A::in, B::in, Res::out) is det :- Res = CompareFunc(A, B) ),
|
|
merge_lists_and_remove_dups(ComparePred, Lists, MergedList).
|
|
|
|
merge_lists_and_remove_dups(ComparePred, Lists, MergedList) :-
|
|
(
|
|
Lists = [],
|
|
MergedList = []
|
|
;
|
|
Lists = [List1],
|
|
MergedList = List1
|
|
;
|
|
Lists = [List1, List2],
|
|
merge_and_remove_dups(ComparePred, List1, List2, MergedList)
|
|
;
|
|
Lists = [List1, List2, List3],
|
|
merge_and_remove_dups(ComparePred, List1, List2, List12),
|
|
merge_and_remove_dups(ComparePred, List12, List3, MergedList)
|
|
;
|
|
Lists = [_, _, _, _ | _],
|
|
merge_lists_and_remove_dups_fixpoint(ComparePred, Lists, MergedList)
|
|
).
|
|
|
|
:- pred merge_lists_and_remove_dups_fixpoint(
|
|
comparison_pred(T)::in(comparison_pred),
|
|
list(list(T))::in, list(T)::out) is det.
|
|
|
|
merge_lists_and_remove_dups_fixpoint(ComparePred, Lists, MergedList) :-
|
|
merge_lists_and_remove_dups_pass(ComparePred, Lists, [], RevMergedLists),
|
|
% This reverse is required to ensure that for any items that occur
|
|
% in more than one list, we pick the item that occurs in the first one.
|
|
list.reverse(RevMergedLists, MergedLists),
|
|
(
|
|
MergedLists = [],
|
|
unexpected($pred, "MergedLists is empty")
|
|
;
|
|
MergedLists = [MergedList]
|
|
;
|
|
MergedLists = [_, _ | _],
|
|
merge_lists_and_remove_dups_fixpoint(ComparePred,
|
|
MergedLists, MergedList)
|
|
).
|
|
|
|
:- pred merge_lists_and_remove_dups_pass(
|
|
comparison_pred(T)::in(comparison_pred),
|
|
list(list(T))::in, list(list(T))::in, list(list(T))::out) is det.
|
|
|
|
merge_lists_and_remove_dups_pass(ComparePred, Lists, !RevMergedLists) :-
|
|
(
|
|
Lists = []
|
|
;
|
|
Lists = [List1],
|
|
!:RevMergedLists = [List1 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2],
|
|
merge_and_remove_dups(ComparePred, List1, List2, List12),
|
|
!:RevMergedLists = [List12 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2, List3],
|
|
merge_and_remove_dups(ComparePred, List1, List2, List12),
|
|
merge_and_remove_dups(ComparePred, List12, List3, List123),
|
|
!:RevMergedLists = [List123 | !.RevMergedLists]
|
|
;
|
|
Lists = [List1, List2, List3, List4 | MoreLists],
|
|
merge_and_remove_dups(ComparePred, List1, List2, List12),
|
|
merge_and_remove_dups(ComparePred, List3, List4, List34),
|
|
merge_and_remove_dups(ComparePred, List12, List34, List1234),
|
|
!:RevMergedLists = [List1234 | !.RevMergedLists],
|
|
merge_lists_and_remove_dups_pass(ComparePred, MoreLists,
|
|
!RevMergedLists)
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
intersect(ListA, ListB) = IntersectList :-
|
|
intersect(ListA, ListB, IntersectList).
|
|
|
|
intersect([], _, []).
|
|
intersect([_ | _], [], []).
|
|
intersect([X | Xs], [Y | Ys], IntersectList) :-
|
|
compare(R, X, Y),
|
|
(
|
|
R = (<),
|
|
intersect(Xs, [Y | Ys], IntersectList)
|
|
;
|
|
R = (=),
|
|
intersect(Xs, Ys, IntersectList0),
|
|
IntersectList = [X | IntersectList0]
|
|
;
|
|
R = (>),
|
|
intersect([X | Xs], Ys, IntersectList)
|
|
).
|
|
|
|
intersect_lists(Lists) = IntersectList :-
|
|
intersect_lists(Lists, IntersectList).
|
|
|
|
intersect_lists(Lists, IntersectList) :-
|
|
(
|
|
Lists = [],
|
|
IntersectList = []
|
|
;
|
|
Lists = [List1],
|
|
IntersectList = List1
|
|
;
|
|
Lists = [List1, List2],
|
|
intersect(List1, List2, IntersectList)
|
|
;
|
|
Lists = [List1, List2, List3],
|
|
intersect(List1, List2, List12),
|
|
intersect(List12, List3, IntersectList)
|
|
;
|
|
Lists = [_, _, _, _ | _],
|
|
intersect_lists_fixpoint(Lists, IntersectList)
|
|
).
|
|
|
|
:- pred intersect_lists_fixpoint(list(list(T))::in, list(T)::out) is det.
|
|
|
|
intersect_lists_fixpoint(Lists, IntersectList) :-
|
|
intersect_lists_pass(Lists, [], RevIntersectLists),
|
|
% The order does not matter.
|
|
IntersectLists = RevIntersectLists,
|
|
(
|
|
IntersectLists = [],
|
|
unexpected($pred, "IntersectLists is empty")
|
|
;
|
|
IntersectLists = [IntersectList]
|
|
;
|
|
IntersectLists = [_, _ | _],
|
|
intersect_lists_fixpoint(IntersectLists, IntersectList)
|
|
).
|
|
|
|
:- pred intersect_lists_pass(list(list(T))::in,
|
|
list(list(T))::in, list(list(T))::out) is det.
|
|
|
|
intersect_lists_pass(Lists, !RevIntersectLists) :-
|
|
(
|
|
Lists = []
|
|
;
|
|
Lists = [List1],
|
|
!:RevIntersectLists = [List1 | !.RevIntersectLists]
|
|
;
|
|
Lists = [List1, List2],
|
|
intersect(List1, List2, List12),
|
|
!:RevIntersectLists = [List12 | !.RevIntersectLists]
|
|
;
|
|
Lists = [List1, List2, List3],
|
|
intersect(List1, List2, List12),
|
|
intersect(List12, List3, List123),
|
|
!:RevIntersectLists = [List123 | !.RevIntersectLists]
|
|
;
|
|
Lists = [List1, List2, List3, List4 | MoreLists],
|
|
intersect(List1, List2, List12),
|
|
intersect(List3, List4, List34),
|
|
intersect(List12, List34, List1234),
|
|
!:RevIntersectLists = [List1234 | !.RevIntersectLists],
|
|
intersect_lists_pass(MoreLists, !RevIntersectLists)
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
sort(List) = SortedList :-
|
|
sort(List, SortedList).
|
|
|
|
sort(List, SortedList) :-
|
|
merge_sort(list.length(List), List, SortedList).
|
|
|
|
sort_and_remove_dups(List) = SortedList :-
|
|
sort_and_remove_dups(List, SortedList).
|
|
|
|
sort_and_remove_dups(List, SortedList) :-
|
|
merge_sort_and_remove_dups(list.length(List), List, SortedList).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
:- pred merge_sort(int::in, list(T)::in, list(T)::out) is det.
|
|
:- pragma type_spec(list.merge_sort(in, in, out), T = var(_)).
|
|
|
|
merge_sort(Length, List, SortedList) :-
|
|
( if Length > 1 then
|
|
HalfLength = Length // 2,
|
|
det_split_list(HalfLength, List, Front, Back),
|
|
merge_sort(HalfLength, Front, SortedFront),
|
|
merge_sort(Length - HalfLength, Back, SortedBack),
|
|
merge(SortedFront, SortedBack, SortedList)
|
|
else
|
|
SortedList = List
|
|
).
|
|
|
|
:- pred merge_sort_and_remove_dups(int::in, list(T)::in, list(T)::out)
|
|
is det.
|
|
:- pragma type_spec(merge_sort_and_remove_dups(in, in, out), T = var(_)).
|
|
|
|
merge_sort_and_remove_dups(Length, List, SortedList) :-
|
|
( if Length > 1 then
|
|
HalfLength = Length // 2,
|
|
det_split_list(HalfLength, List, Front, Back),
|
|
merge_sort_and_remove_dups(HalfLength, Front, SortedFront),
|
|
merge_sort_and_remove_dups(Length - HalfLength, Back, SortedBack),
|
|
merge_and_remove_dups(SortedFront, SortedBack, SortedList)
|
|
else
|
|
SortedList = List
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
sort(CompareFunc, Xs) = Ys :-
|
|
ComparePred =
|
|
( pred(X::in, Y::in, Res::out) is det :-
|
|
Res = CompareFunc(X, Y)
|
|
),
|
|
sort(ComparePred, Xs, Ys).
|
|
|
|
sort(ComparePred, List, SortedList) :-
|
|
list.length(List, N),
|
|
( if N = 0 then
|
|
SortedList = []
|
|
else
|
|
( if
|
|
hosort(ComparePred, N, List, SortedListPrime, LeftOver),
|
|
LeftOver = []
|
|
then
|
|
SortedList = SortedListPrime
|
|
else
|
|
unexpected($pred, "hosort failed")
|
|
)
|
|
).
|
|
|
|
sort_and_remove_dups(ComparePred, L0, L) :-
|
|
sort(ComparePred, L0, L1),
|
|
remove_adjacent_dups(ComparePred, L1, L).
|
|
|
|
% list.hosort is a Mercury implementation of the mergesort described
|
|
% in The Craft of Prolog.
|
|
%
|
|
% N denotes the length of the part of L0 that this call is sorting.
|
|
% (require((length(L0, M), M >= N)))
|
|
% Since we have redundant information about the list (N, and the length
|
|
% implicit in the list itself), we get a semidet unification when we
|
|
% deconstruct the list. list.hosort is therefore actually det but the
|
|
% compiler can't confirm it.
|
|
%
|
|
:- pred hosort(comparison_pred(X)::in(comparison_pred), int::in,
|
|
list(X)::in, list(X)::out, list(X)::out) is semidet.
|
|
|
|
hosort(ComparePred, N, List, SortedInitialN, LeftOver) :-
|
|
( if N = 1 then
|
|
List = [X | LeftOver],
|
|
SortedInitialN = [X]
|
|
else if N = 2 then
|
|
List = [X, Y | LeftOver],
|
|
ComparePred(X, Y, Res),
|
|
(
|
|
Res = (<),
|
|
SortedInitialN = [X, Y]
|
|
;
|
|
Res = (=),
|
|
SortedInitialN = [X, Y]
|
|
;
|
|
Res = (>),
|
|
SortedInitialN = [Y, X]
|
|
)
|
|
else
|
|
N1 = N // 2,
|
|
N2 = N - N1,
|
|
hosort(ComparePred, N1, List, SortedInitialN1, Middle),
|
|
hosort(ComparePred, N2, Middle, SortedNextN2, LeftOver),
|
|
merge(ComparePred, SortedInitialN1, SortedNextN2, SortedInitialN)
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
split_list(N, List, Start, End) :-
|
|
( if N > 0 then
|
|
List = [Head | Tail],
|
|
list.split_list(N - 1, Tail, StartTail, End),
|
|
Start = [Head | StartTail]
|
|
else
|
|
N = 0,
|
|
Start = [],
|
|
End = List
|
|
).
|
|
|
|
det_split_list(N, List, Start, End) :-
|
|
( if N > 0 then
|
|
(
|
|
List = [Head | Tail],
|
|
list.det_split_list(N - 1, Tail, StartTail, End),
|
|
Start = [Head | StartTail]
|
|
;
|
|
List = [],
|
|
unexpected($pred, "index out of range")
|
|
)
|
|
else if N = 0 then
|
|
Start = [],
|
|
End = List
|
|
else
|
|
unexpected($pred, "index out of range")
|
|
).
|
|
|
|
split_upto(N, List, Start, End) :-
|
|
( if N < 0 then
|
|
unexpected($file, $pred, "index is negative")
|
|
else
|
|
do_split_upto(N, List, Start, End)
|
|
).
|
|
|
|
:- pred do_split_upto(int::in, list(T)::in, list(T)::out, list(T)::out)
|
|
is det.
|
|
|
|
do_split_upto(N, List, Start, End) :-
|
|
( if
|
|
N > 0,
|
|
List = [Head | Tail]
|
|
then
|
|
do_split_upto(N - 1, Tail, StartTail, End),
|
|
Start = [Head | StartTail]
|
|
else
|
|
Start = [],
|
|
End = List
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
last([H | T], Last) :-
|
|
(
|
|
T = [],
|
|
Last = H
|
|
;
|
|
T = [_ | _],
|
|
list.last(T, Last)
|
|
).
|
|
|
|
det_last(List) = Last :-
|
|
list.det_last(List, Last).
|
|
|
|
det_last([], _) :-
|
|
unexpected($pred, "empty list").
|
|
det_last([H | T], Last) :-
|
|
list.det_last_loop(H, T, Last).
|
|
|
|
:- pred det_last_loop(T::in, list(T)::in, T::out) is det.
|
|
|
|
det_last_loop(H, T, Last) :-
|
|
(
|
|
T = [],
|
|
Last = H
|
|
;
|
|
T = [TH | TT],
|
|
list.det_last_loop(TH, TT, Last)
|
|
).
|
|
|
|
split_last([H | T], AllButLast, Last) :-
|
|
(
|
|
T = [],
|
|
AllButLast = [],
|
|
Last = H
|
|
;
|
|
T = [TH | TT],
|
|
list.det_split_last_loop(TH, TT, AllButLastTail, Last),
|
|
AllButLast = [H | AllButLastTail]
|
|
).
|
|
|
|
det_split_last([], _, _) :-
|
|
unexpected($pred, "empty list").
|
|
det_split_last([H | T], AllButLast, Last) :-
|
|
(
|
|
T = [],
|
|
AllButLast = [],
|
|
Last = H
|
|
;
|
|
T = [TH | TT],
|
|
list.det_split_last_loop(TH, TT, AllButLastTail, Last),
|
|
AllButLast = [H | AllButLastTail]
|
|
).
|
|
|
|
:- pred det_split_last_loop(T::in, list(T)::in, list(T)::out, T::out) is det.
|
|
|
|
det_split_last_loop(H, T, AllButLast, Last) :-
|
|
(
|
|
T = [],
|
|
AllButLast = [],
|
|
Last = H
|
|
;
|
|
T = [TH | TT],
|
|
list.det_split_last_loop(TH, TT, AllButLastTail, Last),
|
|
AllButLast = [H | AllButLastTail]
|
|
).
|
|
|
|
intersperse(_Sep, [], []).
|
|
intersperse(Sep, [Head | Tail], ListWithSep) :-
|
|
intersperse_loop(Sep, Head, Tail, ListWithSep).
|
|
|
|
:- pred intersperse_loop(T::in, T::in, list(T)::in, list(T)::out) is det.
|
|
|
|
intersperse_loop(Sep, Head, Tail, ListWithSep) :-
|
|
(
|
|
Tail = [],
|
|
ListWithSep = [Head]
|
|
;
|
|
Tail = [HeadTail | TailTail],
|
|
intersperse_loop(Sep, HeadTail, TailTail, TailListWithSep),
|
|
ListWithSep = [Head, Sep | TailListWithSep]
|
|
).
|
|
|
|
intersperse_list(_Seps, [], []).
|
|
intersperse_list(Seps, [Head | Tail], ListWithSeps) :-
|
|
intersperse_list_loop(Seps, Head, Tail, ListWithSeps).
|
|
|
|
:- pred intersperse_list_loop(list(T)::in, T::in, list(T)::in, list(T)::out)
|
|
is det.
|
|
|
|
intersperse_list_loop(Seps, Head, Tail, ListWithSeps) :-
|
|
(
|
|
Tail = [],
|
|
ListWithSeps = [Head]
|
|
;
|
|
Tail = [HeadTail | TailTail],
|
|
intersperse_list_loop(Seps, HeadTail, TailTail, TailListWithSeps),
|
|
ListWithSeps = [Head | Seps] ++ TailListWithSeps
|
|
).
|
|
|
|
intersperse_list_last(_NonLastSeps, _LastSeps, [], []).
|
|
intersperse_list_last(_NonLastSeps, _LastSeps, [Elt1], ListWithSeps) :-
|
|
ListWithSeps = [Elt1].
|
|
intersperse_list_last(NonLastSeps, LastSeps, [Elt1, Elt2 | Elt3plus],
|
|
ListWithSeps) :-
|
|
intersperse_list_last_loop(NonLastSeps, LastSeps, Elt1, Elt2, Elt3plus,
|
|
ListWithSeps).
|
|
|
|
:- pred intersperse_list_last_loop(list(T)::in, list(T)::in,
|
|
T::in, T::in, list(T)::in, list(T)::out) is det.
|
|
|
|
intersperse_list_last_loop(NonLastSeps, LastSeps, Elt1, Elt2, Elt3plus,
|
|
ListWithSeps) :-
|
|
(
|
|
Elt3plus = [],
|
|
ListWithSeps = [Elt1 | LastSeps] ++ [Elt2]
|
|
;
|
|
Elt3plus = [Elt3 | Elt4plus],
|
|
intersperse_list_last_loop(NonLastSeps, LastSeps, Elt2, Elt3, Elt4plus,
|
|
TailListWithSeps),
|
|
ListWithSeps = [Elt1 | NonLastSeps] ++ TailListWithSeps
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
take(N, Xs, InitialXs) :-
|
|
( if N > 0 then
|
|
Xs = [HeadX | TailXs],
|
|
list.take(N - 1, TailXs, InitialXsTail),
|
|
InitialXs = [HeadX | InitialXsTail]
|
|
else
|
|
N = 0,
|
|
InitialXs = []
|
|
).
|
|
|
|
det_take(N, Xs, InitialXs) :-
|
|
( if list.take(N, Xs, InitialXsPrime) then
|
|
InitialXs = InitialXsPrime
|
|
else
|
|
unexpected($file, $pred, "index out of range")
|
|
).
|
|
|
|
take_upto(N, Xs) = InitialXs :-
|
|
list.take_upto(N, Xs, InitialXs).
|
|
|
|
take_upto(N, Xs, InitialXs) :-
|
|
( if N < 0 then
|
|
unexpected($file, $pred, "index is negative")
|
|
else
|
|
do_take_upto(N, Xs, InitialXs)
|
|
).
|
|
|
|
:- pred do_take_upto(int::in, list(T)::in, list(T)::out) is det.
|
|
|
|
do_take_upto(N, Xs, InitialXs) :-
|
|
( if list.take(N, Xs, InitialXsPrime) then
|
|
InitialXs = InitialXsPrime
|
|
else
|
|
InitialXs = Xs
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
drop(N, Xs, FinalXs) :-
|
|
( if N > 0 then
|
|
Xs = [_ | Tail],
|
|
list.drop(N - 1, Tail, FinalXs)
|
|
else
|
|
N = 0,
|
|
FinalXs = Xs
|
|
).
|
|
|
|
det_drop(N, Xs, FinalXs) :-
|
|
( if list.drop(N, Xs, FinalXsPrime) then
|
|
FinalXs = FinalXsPrime
|
|
else
|
|
unexpected($file, $pred, "index out of range")
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
take_while(_, [], [], []).
|
|
take_while(P, AllXs @ [X | Xs], Ins, Outs) :-
|
|
( if P(X) then
|
|
take_while(P, Xs, Ins0, Outs),
|
|
Ins = [X | Ins0]
|
|
else
|
|
Ins = [],
|
|
Outs = AllXs
|
|
).
|
|
|
|
take_while_not(_, [], [], []).
|
|
take_while_not(P, AllXs @ [X | Xs], Ins, Outs) :-
|
|
( if P(X) then
|
|
Ins = [],
|
|
Outs = AllXs
|
|
else
|
|
take_while_not(P, Xs, Ins0, Outs),
|
|
Ins = [X | Ins0]
|
|
).
|
|
|
|
take_while(P, Xs) = In :-
|
|
take_while(P, Xs, In).
|
|
|
|
take_while(_, [], []).
|
|
take_while(P, [X | Xs], In) :-
|
|
( if P(X) then
|
|
take_while(P, Xs, In0),
|
|
In = [X | In0]
|
|
else
|
|
In = []
|
|
).
|
|
|
|
take_while_not(P, Xs) = In :-
|
|
take_while_not(P, Xs, In).
|
|
|
|
take_while_not(_, [], []).
|
|
take_while_not(P, [X | Xs], In) :-
|
|
( if P(X) then
|
|
In = []
|
|
else
|
|
take_while_not(P, Xs, In0),
|
|
In = [X | In0]
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
drop_while(P, Xs) = End :-
|
|
drop_while(P, Xs, End).
|
|
|
|
drop_while(_, [], []).
|
|
drop_while(P, [X | Xs], End) :-
|
|
( if P(X) then
|
|
drop_while(P, Xs, End)
|
|
else
|
|
End = [X | Xs]
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
duplicate(N, X) = Xs :-
|
|
accumulate_n_copies(N, X, [], Xs).
|
|
|
|
duplicate(N, X, Xs) :-
|
|
accumulate_n_copies(N, X, [], Xs).
|
|
|
|
:- pred accumulate_n_copies(int::in, T::in, list(T)::in, list(T)::out) is det.
|
|
|
|
accumulate_n_copies(N, X, !Xs) :-
|
|
( if N > 0 then
|
|
!:Xs = [X | !.Xs],
|
|
accumulate_n_copies(N - 1, X, !Xs)
|
|
else
|
|
true
|
|
).
|
|
|
|
all_same([]).
|
|
all_same([H | T]) :-
|
|
all_same_as(H, T).
|
|
|
|
:- pred all_same_as(T::in, list(T)::in) is semidet.
|
|
|
|
all_same_as(_, []).
|
|
all_same_as(SameAs, [H | T]) :-
|
|
H = SameAs,
|
|
all_same_as(SameAs, T).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
condense(Xss) = Ys :-
|
|
list.condense(Xss, Ys).
|
|
|
|
condense(Xss, Ys) :-
|
|
reverse(Xss, RevXss),
|
|
condense_acc(RevXss, [], Ys).
|
|
|
|
:- pred condense_acc(list(list(T))::in, list(T)::in, list(T)::out) is det.
|
|
|
|
condense_acc([], !Ys).
|
|
condense_acc([L | Ls], !Ys) :-
|
|
append(L, !Ys),
|
|
condense_acc(Ls, !Ys).
|
|
|
|
chunk(Xs, N) = Ys :-
|
|
chunk(Xs, N, Ys).
|
|
|
|
chunk(List, ChunkSize, ListOfSmallLists) :-
|
|
chunk_loop(List, ChunkSize, [], ChunkSize, ListOfSmallLists).
|
|
|
|
:- pred chunk_loop(list(T)::in, int::in, list(T)::in, int::in,
|
|
list(list(T))::out) is det.
|
|
|
|
chunk_loop([], _ChunkSize, List0, _N, Lists) :-
|
|
(
|
|
List0 = [],
|
|
Lists = []
|
|
;
|
|
List0 = [_ | _],
|
|
reverse(List0, List),
|
|
Lists = [List]
|
|
).
|
|
chunk_loop([X | Xs], ChunkSize, List0, N, Lists) :-
|
|
( if N > 1 then
|
|
chunk_loop(Xs, ChunkSize, [X | List0], N - 1, Lists)
|
|
else
|
|
reverse([X | List0], List),
|
|
chunk_loop(Xs, ChunkSize, [], ChunkSize, ListsTail),
|
|
Lists = [List | ListsTail]
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
zip(Xs, Ys) = Zs :-
|
|
zip(Xs, Ys, Zs).
|
|
|
|
zip([], Bs, Bs).
|
|
zip([A | As], Bs, [A | Cs]) :-
|
|
zip_2(As, Bs, Cs).
|
|
|
|
:- pred zip_2(list(T)::in, list(T)::in, list(T)::out) is det.
|
|
|
|
zip_2(As, [], As).
|
|
zip_2(As, [B | Bs], [B | Cs]) :-
|
|
zip(As, Bs, Cs).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
perm([], []).
|
|
perm([X | Xs], Ys) :-
|
|
perm(Xs, Ys0),
|
|
insert(X, Ys0, Ys).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
list_to_doc(L) = pretty_printer.list_to_doc(L).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%---------------------------------------------------------------------------%
|
|
|
|
find_first_match(P, [H | T], FirstMatch) :-
|
|
( if P(H) then
|
|
FirstMatch = H
|
|
else
|
|
find_first_match(P, T, FirstMatch)
|
|
).
|
|
|
|
any_true(P, L) :-
|
|
not all_false(P, L).
|
|
|
|
any_false(P, L) :-
|
|
not all_true(P, L).
|
|
|
|
all_true(_P, []).
|
|
all_true(P, [X | Xs]) :-
|
|
P(X),
|
|
all_true(P, Xs).
|
|
|
|
all_false(_P, []).
|
|
all_false(P, [X | Xs]) :-
|
|
not P(X),
|
|
all_false(P, Xs).
|
|
|
|
all_true_corresponding(_P, [], []).
|
|
all_true_corresponding(_P, [], [_ | _]) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
all_true_corresponding(_P, [_ | _], []) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
all_true_corresponding(P, [X | Xs], [Y | Ys]) :-
|
|
P(X, Y),
|
|
all_true_corresponding(P, Xs, Ys).
|
|
|
|
all_false_corresponding(_P, [], []).
|
|
all_false_corresponding(_P, [], [_ | _]) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
all_false_corresponding(_P, [_ | _], []) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
all_false_corresponding(P, [X | Xs], [Y | Ys]) :-
|
|
not P(X, Y),
|
|
all_false_corresponding(P, Xs, Ys).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
filter(P, Xs) = Trues :-
|
|
filter(P, Xs, Trues).
|
|
|
|
filter(_, [], []).
|
|
filter(P, [H | T], True) :-
|
|
( if P(H) then
|
|
filter(P, T, TrueTail),
|
|
True = [H | TrueTail]
|
|
else
|
|
filter(P, T, True)
|
|
).
|
|
|
|
filter(_, [], [], []).
|
|
filter(P, [H | T], True, False) :-
|
|
( if P(H) then
|
|
filter(P, T, TrueTail, False),
|
|
True = [H | TrueTail]
|
|
else
|
|
filter(P, T, True, FalseTail),
|
|
False = [H | FalseTail]
|
|
).
|
|
|
|
negated_filter(P, Xs) = Falses :-
|
|
negated_filter(P, Xs, Falses).
|
|
|
|
negated_filter(_, [], []).
|
|
negated_filter(P, [H | T], False) :-
|
|
( if P(H) then
|
|
negated_filter(P, T, False)
|
|
else
|
|
negated_filter(P, T, FalseTail),
|
|
False = [H | FalseTail]
|
|
).
|
|
|
|
filter_map(F, Xs) = Ys :-
|
|
P = ( pred(X::in, Y::out) is semidet :- Y = F(X) ),
|
|
filter_map(P, Xs, Ys).
|
|
|
|
filter_map(_, [], []).
|
|
filter_map(P, [H0 | T0], True) :-
|
|
( if P(H0, H) then
|
|
filter_map(P, T0, TrueTail),
|
|
True = [H | TrueTail]
|
|
else
|
|
filter_map(P, T0, True)
|
|
).
|
|
|
|
filter_map(_, [], [], []).
|
|
filter_map(P, [H0 | T0], True, False) :-
|
|
( if P(H0, H) then
|
|
filter_map(P, T0, TrueTail, False),
|
|
True = [H | TrueTail]
|
|
else
|
|
filter_map(P, T0, True, FalseTail),
|
|
False = [H0 | FalseTail]
|
|
).
|
|
|
|
find_first_map(P, [X | Xs], A) :-
|
|
( if P(X, A0) then
|
|
A = A0
|
|
else
|
|
find_first_map(P, Xs, A)
|
|
).
|
|
|
|
find_first_map2(P, [X | Xs], A, B) :-
|
|
( if P(X, A0, B0) then
|
|
A = A0,
|
|
B = B0
|
|
else
|
|
find_first_map2(P, Xs, A, B)
|
|
).
|
|
|
|
find_first_map3(P, [X | Xs], A, B, C) :-
|
|
( if P(X, A0, B0, C0) then
|
|
A = A0,
|
|
B = B0,
|
|
C = C0
|
|
else
|
|
find_first_map3(P, Xs, A, B, C)
|
|
).
|
|
|
|
find_index_of_match(Match, [X | Xs], Index0, Index) :-
|
|
( if Match(X) then
|
|
Index = Index0
|
|
else
|
|
find_index_of_match(Match, Xs, Index0 + 1, Index)
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
map(_F, []) = [].
|
|
map(F, [H | T]) = [F(H) | list.map(F, T)].
|
|
|
|
map(_, [], []).
|
|
map(P, [H0 | T0], [H | T]) :-
|
|
P(H0, H),
|
|
list.map(P, T0, T).
|
|
|
|
map2(_, [], [], []).
|
|
map2(P, [H0 | T0], [H1 | T1], [H2 | T2]) :-
|
|
P(H0, H1, H2),
|
|
list.map2(P, T0, T1, T2).
|
|
|
|
map3(_, [], [], [], []).
|
|
map3(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3]) :-
|
|
P(H0, H1, H2, H3),
|
|
list.map3(P, T0, T1, T2, T3).
|
|
|
|
map4(_, [], [], [], [], []).
|
|
map4(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4]) :-
|
|
P(H0, H1, H2, H3, H4),
|
|
list.map4(P, T0, T1, T2, T3, T4).
|
|
|
|
map5(_, [], [], [], [], [], []).
|
|
map5(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4], [H5 | T5])
|
|
:-
|
|
P(H0, H1, H2, H3, H4, H5),
|
|
list.map5(P, T0, T1, T2, T3, T4, T5).
|
|
|
|
map6(_, [], [], [], [], [], [], []).
|
|
map6(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4], [H5 | T5],
|
|
[H6 | T6]) :-
|
|
P(H0, H1, H2, H3, H4, H5, H6),
|
|
list.map6(P, T0, T1, T2, T3, T4, T5, T6).
|
|
|
|
map7(_, [], [], [], [], [], [], [], []).
|
|
map7(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4], [H5 | T5],
|
|
[H6 | T6], [H7 | T7]) :-
|
|
P(H0, H1, H2, H3, H4, H5, H6, H7),
|
|
list.map7(P, T0, T1, T2, T3, T4, T5, T6, T7).
|
|
|
|
map8(_, [], [], [], [], [], [], [], [], []).
|
|
map8(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4], [H5 | T5],
|
|
[H6 | T6], [H7 | T7], [H8 | T8]) :-
|
|
P(H0, H1, H2, H3, H4, H5, H6, H7, H8),
|
|
list.map8(P, T0, T1, T2, T3, T4, T5, T6, T7, T8).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
map_corresponding(_, [], []) = [].
|
|
map_corresponding(_, [], [_ | _]) =
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding(_, [_ | _], []) =
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding(F, [HA | TAs], [HB | TBs]) =
|
|
[F(HA, HB) | list.map_corresponding(F, TAs, TBs)].
|
|
|
|
map_corresponding(_, [], [], []).
|
|
map_corresponding(_, [], [_ | _], _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding(_, [_ | _], [], _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding(P, [HA | TAs], [HB | TBs], [HR | TRs]) :-
|
|
P(HA, HB, HR),
|
|
list.map_corresponding(P, TAs, TBs, TRs).
|
|
|
|
map_corresponding3(F, A, B, C) =
|
|
( if
|
|
A = [AH | AT],
|
|
B = [BH | BT],
|
|
C = [CH | CT]
|
|
then
|
|
[F(AH, BH, CH) | list.map_corresponding3(F, AT, BT, CT)]
|
|
else if
|
|
A = [],
|
|
B = [],
|
|
C = []
|
|
then
|
|
[]
|
|
else
|
|
unexpected($pred, "mismatched list lengths")
|
|
).
|
|
|
|
map_corresponding3(P, A, B, C, R) :-
|
|
( if
|
|
A = [AH | AT],
|
|
B = [BH | BT],
|
|
C = [CH | CT]
|
|
then
|
|
P(AH, BH, CH, RH),
|
|
list.map_corresponding3(P, AT, BT, CT, RT),
|
|
R = [RH | RT]
|
|
else if
|
|
A = [],
|
|
B = [],
|
|
C = []
|
|
then
|
|
R = []
|
|
else
|
|
unexpected($pred, "mismatched list lengths")
|
|
).
|
|
|
|
map_corresponding4(F, A, B, C, D) =
|
|
( if
|
|
A = [AH | AT],
|
|
B = [BH | BT],
|
|
C = [CH | CT],
|
|
D = [DH | DT]
|
|
then
|
|
[F(AH, BH, CH, DH) | list.map_corresponding4(F, AT, BT, CT, DT)]
|
|
else if
|
|
A = [],
|
|
B = [],
|
|
C = [],
|
|
D = []
|
|
then
|
|
[]
|
|
else
|
|
unexpected($pred, "mismatched list lengths")
|
|
).
|
|
|
|
map_corresponding4(P, A, B, C, D, R) :-
|
|
( if
|
|
A = [AH | AT],
|
|
B = [BH | BT],
|
|
C = [CH | CT],
|
|
D = [DH | DT]
|
|
then
|
|
P(AH, BH, CH, DH, RH),
|
|
list.map_corresponding4(P, AT, BT, CT, DT, RT),
|
|
R = [RH | RT]
|
|
else if
|
|
A = [],
|
|
B = [],
|
|
C = [],
|
|
D = []
|
|
then
|
|
R = []
|
|
else
|
|
unexpected($pred, "mismatched list lengths")
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
filter_map_corresponding(_, [], []) = [].
|
|
filter_map_corresponding(_, [], [_ | _]) =
|
|
unexpected($pred, "mismatched list lengths").
|
|
filter_map_corresponding(_, [_ | _], []) =
|
|
unexpected($pred, "mismatched list lengths").
|
|
filter_map_corresponding(F, [HA | TAs], [HB | TBs]) =
|
|
( if F(HA, HB) = HR then
|
|
[HR | list.filter_map_corresponding(F, TAs, TBs)]
|
|
else
|
|
list.filter_map_corresponding(F, TAs, TBs)
|
|
).
|
|
|
|
filter_map_corresponding(_, [], [], []).
|
|
filter_map_corresponding(_, [], [_ | _], _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
filter_map_corresponding(_, [_ | _], [], _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
filter_map_corresponding(P, [HA | TAs], [HB | TBs], Rs) :-
|
|
( if P(HA, HB, HR) then
|
|
list.filter_map_corresponding(P, TAs, TBs, TRs),
|
|
Rs = [HR | TRs]
|
|
else
|
|
list.filter_map_corresponding(P, TAs, TBs, Rs)
|
|
).
|
|
|
|
filter_map_corresponding3(F, As, Bs, Cs) =
|
|
( if
|
|
As = [HA | TAs],
|
|
Bs = [HB | TBs],
|
|
Cs = [HC | TCs]
|
|
then
|
|
( if F(HA, HB, HC) = HR then
|
|
[HR | list.filter_map_corresponding3(F, TAs, TBs, TCs)]
|
|
else
|
|
list.filter_map_corresponding3(F, TAs, TBs, TCs)
|
|
)
|
|
else if
|
|
As = [],
|
|
Bs = [],
|
|
Cs = []
|
|
then
|
|
[]
|
|
else
|
|
unexpected($pred, "mismatched list lengths")
|
|
).
|
|
|
|
filter_map_corresponding3(P, As, Bs, Cs, Rs) :-
|
|
( if
|
|
As = [HA | TAs],
|
|
Bs = [HB | TBs],
|
|
Cs = [HC | TCs]
|
|
then
|
|
( if P(HA, HB, HC, HR) then
|
|
list.filter_map_corresponding3(P, TAs, TBs, TCs, TRs),
|
|
Rs = [HR | TRs]
|
|
else
|
|
list.filter_map_corresponding3(P, TAs, TBs, TCs, Rs)
|
|
)
|
|
else if
|
|
As = [],
|
|
Bs = [],
|
|
Cs = []
|
|
then
|
|
Rs = []
|
|
else
|
|
unexpected($pred, "mismatched list lengths")
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
foldl(_, [], !.A) = !:A.
|
|
foldl(F, [H | T], !.A) = !:A :-
|
|
!:A = F(H, !.A),
|
|
!:A = list.foldl(F, T, !.A).
|
|
|
|
foldl(_, [], !A).
|
|
foldl(P, [H | T], !A) :-
|
|
P(H, !A),
|
|
list.foldl(P, T, !A).
|
|
|
|
foldl2(_, [], !A, !B).
|
|
foldl2(P, [H | T], !A, !B) :-
|
|
P(H, !A, !B),
|
|
list.foldl2(P, T, !A, !B).
|
|
|
|
foldl3(_, [], !A, !B, !C).
|
|
foldl3(P, [H | T], !A, !B, !C) :-
|
|
P(H, !A, !B, !C),
|
|
list.foldl3(P, T, !A, !B, !C).
|
|
|
|
foldl4(_, [], !A, !B, !C, !D).
|
|
foldl4(P, [H | T], !A, !B, !C, !D) :-
|
|
P(H, !A, !B, !C, !D),
|
|
list.foldl4(P, T, !A, !B, !C, !D).
|
|
|
|
foldl5(_, [], !A, !B, !C, !D, !E).
|
|
foldl5(P, [H | T], !A, !B, !C, !D, !E) :-
|
|
P(H, !A, !B, !C, !D, !E),
|
|
list.foldl5(P, T, !A, !B, !C, !D, !E).
|
|
|
|
foldl6(_, [], !A, !B, !C, !D, !E, !F).
|
|
foldl6(P, [H | T], !A, !B, !C, !D, !E, !F) :-
|
|
P(H, !A, !B, !C, !D, !E, !F),
|
|
list.foldl6(P, T, !A, !B, !C, !D, !E, !F).
|
|
|
|
foldl7(_, [], !A, !B, !C, !D, !E, !F, !G).
|
|
foldl7(P, [H | T], !A, !B, !C, !D, !E, !F, !G) :-
|
|
P(H, !A, !B, !C, !D, !E, !F, !G),
|
|
list.foldl7(P, T, !A, !B, !C, !D, !E, !F, !G).
|
|
|
|
foldl8(_, [], !A, !B, !C, !D, !E, !F, !G, !H).
|
|
foldl8(P, [H | T], !A, !B, !C, !D, !E, !F, !G, !H) :-
|
|
P(H, !A, !B, !C, !D, !E, !F, !G, !H),
|
|
list.foldl8(P, T, !A, !B, !C, !D, !E, !F, !G, !H).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
gap_foldl(_ProcessPred, _GapPred, [], !A).
|
|
gap_foldl(ProcessPred, GapPred, [H | T], !A) :-
|
|
gap_foldl_lag(ProcessPred, GapPred, H, T, !A).
|
|
|
|
:- pred gap_foldl_lag(pred(L, A, A), pred(A, A), L, list(L), A, A).
|
|
:- mode gap_foldl_lag(in(pred(in, di, uo) is det), in(pred(di, uo) is det),
|
|
in, in, di, uo) is det.
|
|
:- mode gap_foldl_lag(in(pred(in, in, out) is det), in(pred(in, out) is det),
|
|
in, in, in, out) is det.
|
|
|
|
gap_foldl_lag(ProcessPred, GapPred, H, T, !A) :-
|
|
ProcessPred(H, !A),
|
|
(
|
|
T = []
|
|
;
|
|
T = [HT | TT],
|
|
GapPred(!A),
|
|
gap_foldl_lag(ProcessPred, GapPred, HT, TT, !A)
|
|
).
|
|
|
|
last_gap_foldl(ProcessPred, GapPred, LastGapPred, List, !A) :-
|
|
(
|
|
List = []
|
|
;
|
|
List = [E1],
|
|
ProcessPred(E1, !A)
|
|
;
|
|
List = [E1, E2 | E3plus],
|
|
last_gap_foldl_lag(ProcessPred, GapPred, LastGapPred,
|
|
E1, E2, E3plus, !A)
|
|
).
|
|
|
|
:- pred last_gap_foldl_lag(pred(L, A, A), pred(A, A), pred(A, A),
|
|
L, L, list(L), A, A).
|
|
:- mode last_gap_foldl_lag(in(pred(in, di, uo) is det),
|
|
in(pred(di, uo) is det), in(pred(di, uo) is det),
|
|
in, in, in, di, uo) is det.
|
|
:- mode last_gap_foldl_lag(in(pred(in, in, out) is det),
|
|
in(pred(in, out) is det), in(pred(in, out) is det),
|
|
in, in, in, in, out) is det.
|
|
|
|
last_gap_foldl_lag(ProcessPred, GapPred, LastGapPred, E1, E2, E3plus, !A) :-
|
|
ProcessPred(E1, !A),
|
|
(
|
|
E3plus = [],
|
|
LastGapPred(!A),
|
|
ProcessPred(E2, !A)
|
|
;
|
|
E3plus = [E3 | E4plus],
|
|
GapPred(!A),
|
|
last_gap_foldl_lag(ProcessPred, GapPred, LastGapPred,
|
|
E2, E3, E4plus, !A)
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
chunk_foldl(_, _, [], !A).
|
|
chunk_foldl(ChunkSize, P, List @ [_H | _T], !A) :-
|
|
chunk_foldl_inner(ChunkSize, P, List, LeftOver, !A),
|
|
chunk_foldl(ChunkSize, P, LeftOver, !A).
|
|
|
|
:- pred chunk_foldl_inner(int, pred(L, A, A), list(L), list(L), A, A).
|
|
:- mode chunk_foldl_inner(in, in(pred(in, di, uo) is det),
|
|
in, out, di, uo) is det.
|
|
:- mode chunk_foldl_inner(in, in(pred(in, in, out) is det),
|
|
in, out, in, out) is det.
|
|
|
|
chunk_foldl_inner(_, _, [], [], !A).
|
|
chunk_foldl_inner(Left, P, List @ [H | T], LeftOver, !A) :-
|
|
( if Left > 0 then
|
|
P(H, !A),
|
|
chunk_foldl_inner(Left - 1, P, T, LeftOver, !A)
|
|
else
|
|
LeftOver = List
|
|
).
|
|
|
|
%---------------------%
|
|
|
|
chunk_foldl2(_, _, [], !A, !B).
|
|
chunk_foldl2(ChunkSize, P, List @ [_H | _T], !A, !B) :-
|
|
chunk_foldl2_inner(ChunkSize, P, List, LeftOver, !A, !B),
|
|
chunk_foldl2(ChunkSize, P, LeftOver, !A, !B).
|
|
|
|
:- pred chunk_foldl2_inner(int, pred(L, A, A, B, B),
|
|
list(L), list(L), A, A, B, B).
|
|
:- mode chunk_foldl2_inner(in, in(pred(in, di, uo, di, uo) is det),
|
|
in, out, di, uo, di, uo) is det.
|
|
:- mode chunk_foldl2_inner(in, in(pred(in, in, out, di, uo) is det),
|
|
in, out, in, out, di, uo) is det.
|
|
:- mode chunk_foldl2_inner(in, in(pred(in, in, out, in, out) is det),
|
|
in, out, in, out, in, out) is det.
|
|
|
|
chunk_foldl2_inner(_, _, [], [], !A, !B).
|
|
chunk_foldl2_inner(Left, P, List @ [H | T], LeftOver, !A, !B) :-
|
|
( if Left > 0 then
|
|
P(H, !A, !B),
|
|
chunk_foldl2_inner(Left - 1, P, T, LeftOver, !A, !B)
|
|
else
|
|
LeftOver = List
|
|
).
|
|
|
|
%---------------------%
|
|
|
|
chunk_foldl3(_, _, [], !A, !B, !C).
|
|
chunk_foldl3(ChunkSize, P, List @ [_H | _T], !A, !B, !C) :-
|
|
chunk_foldl3_inner(ChunkSize, P, List, LeftOver, !A, !B, !C),
|
|
chunk_foldl3(ChunkSize, P, LeftOver, !A, !B, !C).
|
|
|
|
:- pred chunk_foldl3_inner(int, pred(L, A, A, B, B, C, C),
|
|
list(L), list(L), A, A, B, B, C, C).
|
|
:- mode chunk_foldl3_inner(in, in(pred(in, in, out, di, uo, di, uo) is det),
|
|
in, out, in, out, di, uo, di, uo) is det.
|
|
:- mode chunk_foldl3_inner(in, in(pred(in, in, out, in, out, di, uo) is det),
|
|
in, out, in, out, in, out, di, uo) is det.
|
|
:- mode chunk_foldl3_inner(in, in(pred(in, in, out, in, out, in, out) is det),
|
|
in, out, in, out, in, out, in, out) is det.
|
|
|
|
chunk_foldl3_inner(_, _, [], [], !A, !B, !C).
|
|
chunk_foldl3_inner(Left, P, List @ [H | T], LeftOver, !A, !B, !C) :-
|
|
( if Left > 0 then
|
|
P(H, !A, !B, !C),
|
|
chunk_foldl3_inner(Left - 1, P, T, LeftOver, !A, !B, !C)
|
|
else
|
|
LeftOver = List
|
|
).
|
|
|
|
%---------------------%
|
|
|
|
chunk_foldl4(_, _, [], !A, !B, !C, !D).
|
|
chunk_foldl4(ChunkSize, P, List @ [_H | _T], !A, !B, !C, !D) :-
|
|
chunk_foldl4_inner(ChunkSize, P, List, LeftOver, !A, !B, !C, !D),
|
|
chunk_foldl4(ChunkSize, P, LeftOver, !A, !B, !C, !D).
|
|
|
|
:- pred chunk_foldl4_inner(int,
|
|
pred(L, A, A, B, B, C, C, D, D),
|
|
list(L), list(L), A, A, B, B, C, C, D, D).
|
|
:- mode chunk_foldl4_inner(in,
|
|
in(pred(in, in, out, in, out, di, uo, di, uo) is det),
|
|
in, out, in, out, in, out, di, uo, di, uo) is det.
|
|
:- mode chunk_foldl4_inner(in,
|
|
in(pred(in, in, out, in, out, in, out, di, uo) is det),
|
|
in, out, in, out, in, out, in, out, di, uo) is det.
|
|
:- mode chunk_foldl4_inner(in,
|
|
in(pred(in, in, out, in, out, in, out, in, out) is det),
|
|
in, out, in, out, in, out, in, out, in, out) is det.
|
|
|
|
chunk_foldl4_inner(_, _, [], [], !A, !B, !C, !D).
|
|
chunk_foldl4_inner(Left, P, List @ [H | T], LeftOver, !A, !B, !C, !D) :-
|
|
( if Left > 0 then
|
|
P(H, !A, !B, !C, !D),
|
|
chunk_foldl4_inner(Left - 1, P, T, LeftOver, !A, !B, !C, !D)
|
|
else
|
|
LeftOver = List
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
foldr(_, [], !.A) = !:A .
|
|
foldr(F, [H | T], !.A) = !:A :-
|
|
!:A = list.foldr(F, T, !.A),
|
|
!:A = F(H, !.A).
|
|
|
|
foldr(_, [], !A).
|
|
foldr(P, [H | T], !A) :-
|
|
list.foldr(P, T, !A),
|
|
P(H, !A).
|
|
|
|
foldr2(_, [], !A, !B).
|
|
foldr2(P, [H | T], !A, !B) :-
|
|
list.foldr2(P, T, !A, !B),
|
|
P(H, !A, !B).
|
|
|
|
foldr3(_, [], !A, !B, !C).
|
|
foldr3(P, [H | T], !A, !B, !C) :-
|
|
list.foldr3(P, T, !A, !B, !C),
|
|
P(H, !A, !B, !C).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
foldl_corresponding(_, [], [], !Acc).
|
|
foldl_corresponding(_, [], [_ | _], _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl_corresponding(_, [_ | _], [], _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl_corresponding(P, [A | As], [B | Bs], !Acc) :-
|
|
P(A, B, !Acc),
|
|
list.foldl_corresponding(P, As, Bs, !Acc).
|
|
|
|
foldl_corresponding(_, [], [], Acc) = Acc.
|
|
foldl_corresponding(_, [], [_ | _], _) = _ :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl_corresponding(_, [_ | _], [], _) = _ :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl_corresponding(F, [A | As], [B | Bs], !.Acc) = !:Acc :-
|
|
!:Acc = F(A, B, !.Acc),
|
|
!:Acc = list.foldl_corresponding(F, As, Bs, !.Acc).
|
|
|
|
foldl2_corresponding(_, [], [], !Acc1, !Acc2).
|
|
foldl2_corresponding(_, [], [_ | _], _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl2_corresponding(_, [_ | _], [], _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl2_corresponding(P, [A | As], [B | Bs], !Acc1, !Acc2) :-
|
|
P(A, B, !Acc1, !Acc2),
|
|
list.foldl2_corresponding(P, As, Bs, !Acc1, !Acc2).
|
|
|
|
foldl3_corresponding(_, [], [], !Acc1, !Acc2, !Acc3).
|
|
foldl3_corresponding(_, [], [_ | _], _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl3_corresponding(_, [_ | _], [], _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl3_corresponding(P, [A | As], [B | Bs], !Acc1, !Acc2, !Acc3) :-
|
|
P(A, B, !Acc1, !Acc2, !Acc3),
|
|
list.foldl3_corresponding(P, As, Bs, !Acc1, !Acc2, !Acc3).
|
|
|
|
foldl4_corresponding(_, [], [], !Acc1, !Acc2, !Acc3, !Acc4).
|
|
foldl4_corresponding(_, [], [_ | _], _, _, _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl4_corresponding(_, [_ | _], [], _, _, _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl4_corresponding(P, [A | As], [B | Bs], !Acc1, !Acc2, !Acc3, !Acc4) :-
|
|
P(A, B, !Acc1, !Acc2, !Acc3, !Acc4),
|
|
list.foldl4_corresponding(P, As, Bs, !Acc1, !Acc2, !Acc3, !Acc4).
|
|
|
|
foldl_corresponding3(_, [], [], [], !Acc).
|
|
foldl_corresponding3(_, [_ | _], [], [], _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl_corresponding3(_, [], [_ | _], [], _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl_corresponding3(_, [], [], [_ | _], _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl_corresponding3(_, [], [_ | _], [_ | _], _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl_corresponding3(_, [_ | _], [], [_ | _], _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl_corresponding3(_, [_ | _], [_ | _], [], _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl_corresponding3(P, [ A | As ], [ B | Bs ], [ C | Cs], !Acc) :-
|
|
P(A, B, C, !Acc),
|
|
list.foldl_corresponding3(P, As, Bs, Cs, !Acc).
|
|
|
|
foldl2_corresponding3(_, [], [], [], !Acc1, !Acc2).
|
|
foldl2_corresponding3(_, [_ | _], [], [], _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl2_corresponding3(_, [], [_ | _], [], _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl2_corresponding3(_, [], [], [_ | _], _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl2_corresponding3(_, [], [_ | _], [_ | _], _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl2_corresponding3(_, [_ | _], [], [_ | _], _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl2_corresponding3(_, [_ | _], [_ | _], [], _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl2_corresponding3(P, [ A | As ], [ B | Bs ], [ C | Cs],
|
|
!Acc1, !Acc2) :-
|
|
P(A, B, C, !Acc1, !Acc2),
|
|
list.foldl2_corresponding3(P, As, Bs, Cs, !Acc1, !Acc2).
|
|
|
|
foldl3_corresponding3(_, [], [], [], !Acc1, !Acc2, !Acc3).
|
|
foldl3_corresponding3(_, [_ | _], [], [], _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl3_corresponding3(_, [], [_ | _], [], _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl3_corresponding3(_, [], [], [_ | _], _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl3_corresponding3(_, [], [_ | _], [_ | _], _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl3_corresponding3(_, [_ | _], [], [_ | _], _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl3_corresponding3(_, [_ | _], [_ | _], [], _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl3_corresponding3(P, [ A | As ], [ B | Bs ], [ C | Cs],
|
|
!Acc1, !Acc2, !Acc3) :-
|
|
P(A, B, C, !Acc1, !Acc2, !Acc3),
|
|
list.foldl3_corresponding3(P, As, Bs, Cs, !Acc1, !Acc2, !Acc3).
|
|
|
|
foldl4_corresponding3(_, [], [], [], !Acc1, !Acc2, !Acc3, !Acc4).
|
|
foldl4_corresponding3(_, [_ | _], [], [], _, _, _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl4_corresponding3(_, [], [_ | _], [], _, _, _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl4_corresponding3(_, [], [], [_ | _], _, _, _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl4_corresponding3(_, [], [_ | _], [_ | _], _, _, _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl4_corresponding3(_, [_ | _], [], [_ | _], _, _, _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl4_corresponding3(_, [_ | _], [_ | _], [], _, _, _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
foldl4_corresponding3(P, [ A | As ], [ B | Bs ], [ C | Cs],
|
|
!Acc1, !Acc2, !Acc3, !Acc4) :-
|
|
P(A, B, C, !Acc1, !Acc2, !Acc3, !Acc4),
|
|
list.foldl4_corresponding3(P, As, Bs, Cs, !Acc1, !Acc2, !Acc3, !Acc4).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
map_foldl(_, [], [], !A).
|
|
map_foldl(P, [H0 | T0], [H | T], !A) :-
|
|
P(H0, H, !A),
|
|
list.map_foldl(P, T0, T, !A).
|
|
|
|
map_foldl2(_, [], [], !A, !B).
|
|
map_foldl2(P, [H0 | T0], [H | T], !A, !B) :-
|
|
P(H0, H, !A, !B),
|
|
list.map_foldl2(P, T0, T, !A, !B).
|
|
|
|
map_foldl3(_, [], [], !A, !B, !C).
|
|
map_foldl3(P, [H0 | T0], [H | T], !A, !B, !C) :-
|
|
P(H0, H, !A, !B, !C),
|
|
list.map_foldl3(P, T0, T, !A, !B, !C).
|
|
|
|
map_foldl4(_, [], [], !A, !B, !C, !D).
|
|
map_foldl4(P, [H0 | T0], [H | T], !A, !B, !C, !D) :-
|
|
P(H0, H, !A, !B, !C, !D),
|
|
list.map_foldl4(P, T0, T, !A, !B, !C, !D).
|
|
|
|
map_foldl5(_, [], [], !A, !B, !C, !D, !E).
|
|
map_foldl5(P, [H0 | T0], [H | T], !A, !B, !C, !D, !E) :-
|
|
P(H0, H, !A, !B, !C, !D, !E),
|
|
list.map_foldl5(P, T0, T, !A, !B, !C, !D, !E).
|
|
|
|
map_foldl6(_, [], [], !A, !B, !C, !D, !E, !F).
|
|
map_foldl6(P, [H0 | T0], [H | T], !A, !B, !C, !D, !E, !F) :-
|
|
P(H0, H, !A, !B, !C, !D, !E, !F),
|
|
list.map_foldl6(P, T0, T, !A, !B, !C, !D, !E, !F).
|
|
|
|
map2_foldl(_, [], [], [], !A).
|
|
map2_foldl(P, [H0 | T0], [H1 | T1], [H2 | T2], !A) :-
|
|
P(H0, H1, H2, !A),
|
|
list.map2_foldl(P, T0, T1, T2, !A).
|
|
|
|
map2_foldl2(_, [], [], [], !A, !B).
|
|
map2_foldl2(P, [H0 | T0], [H1 | T1], [H2 | T2], !A, !B) :-
|
|
P(H0, H1, H2, !A, !B),
|
|
list.map2_foldl2(P, T0, T1, T2, !A, !B).
|
|
|
|
map2_foldl3(_, [], [], [], !A, !B, !C).
|
|
map2_foldl3(P, [H0 | T0], [H1 | T1], [H2 | T2], !A, !B, !C) :-
|
|
P(H0, H1, H2, !A, !B, !C),
|
|
list.map2_foldl3(P, T0, T1, T2, !A, !B, !C).
|
|
|
|
map2_foldl4(_, [], [], [], !A, !B, !C, !D).
|
|
map2_foldl4(P, [H0 | T0], [H1 | T1], [H2 | T2], !A, !B, !C, !D) :-
|
|
P(H0, H1, H2, !A, !B, !C, !D),
|
|
list.map2_foldl4(P, T0, T1, T2, !A, !B, !C, !D).
|
|
|
|
map3_foldl(_, [], [], [], [], !A).
|
|
map3_foldl(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], !A) :-
|
|
P(H0, H1, H2, H3, !A),
|
|
list.map3_foldl(P, T0, T1, T2, T3, !A).
|
|
|
|
map3_foldl2(_, [], [], [], [], !A, !B).
|
|
map3_foldl2(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], !A, !B) :-
|
|
P(H0, H1, H2, H3, !A, !B),
|
|
list.map3_foldl2(P, T0, T1, T2, T3, !A, !B).
|
|
|
|
map4_foldl(_, [], [], [], [], [], !A).
|
|
map4_foldl(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4], !A) :-
|
|
P(H0, H1, H2, H3, H4, !A),
|
|
list.map4_foldl(P, T0, T1, T2, T3, T4, !A).
|
|
|
|
map_foldr(_, [], [], !A).
|
|
map_foldr(P, [H0 | T0], [H | T], !A) :-
|
|
list.map_foldr(P, T0, T, !A),
|
|
P(H0, H, !A).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
map_corresponding_foldl(_, [], [], [], !Acc).
|
|
map_corresponding_foldl(_, [], [_ | _], _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding_foldl(_, [_ | _], [], _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding_foldl(P, [A | As], [B | Bs], [C | Cs], !Acc) :-
|
|
P(A, B, C, !Acc),
|
|
list.map_corresponding_foldl(P, As, Bs, Cs, !Acc).
|
|
|
|
map_corresponding_foldl2(_, [], [], [], !Acc1, !Acc2).
|
|
map_corresponding_foldl2(_, [], [_ | _], _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding_foldl2(_, [_ | _], [], _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding_foldl2(P, [A | As], [B | Bs], [C | Cs], !Acc1, !Acc2) :-
|
|
P(A, B, C, !Acc1, !Acc2),
|
|
list.map_corresponding_foldl2(P, As, Bs, Cs, !Acc1, !Acc2).
|
|
|
|
map_corresponding_foldl3(_, [], [], [], !Acc1, !Acc2, !Acc3).
|
|
map_corresponding_foldl3(_, [], [_ | _], _, _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding_foldl3(_, [_ | _], [], _, _, _, _, _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding_foldl3(P, [A | As], [B | Bs], [C | Cs], !Acc1,
|
|
!Acc2, !Acc3) :-
|
|
P(A, B, C, !Acc1, !Acc2, !Acc3),
|
|
list.map_corresponding_foldl3(P, As, Bs, Cs, !Acc1, !Acc2, !Acc3).
|
|
|
|
map_corresponding3_foldl(_, [], [], [], [], !Acc).
|
|
map_corresponding3_foldl(_, [], [_ | _], [_ | _], _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding3_foldl(_, [_ | _], [], [_ | _], _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding3_foldl(_, [_ | _], [_ | _], [], _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding3_foldl(_, [], [], [_ | _], _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding3_foldl(_, [], [_ | _], [], _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding3_foldl(_, [_ | _], [], [], _, _, _) :-
|
|
unexpected($pred, "mismatched list lengths").
|
|
map_corresponding3_foldl(P, [A | As], [B | Bs], [C | Cs], [D | Ds],
|
|
!Acc) :-
|
|
P(A, B, C, D, !Acc),
|
|
list.map_corresponding3_foldl(P, As, Bs, Cs, Ds, !Acc).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
filter_map_foldl(_, [], [], !A).
|
|
filter_map_foldl(P, [X | Xs], True, !A) :-
|
|
( if P(X, Y, !A) then
|
|
list.filter_map_foldl(P, Xs, TrueTail, !A),
|
|
True = [Y | TrueTail]
|
|
else
|
|
list.filter_map_foldl(P, Xs, True, !A)
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
inst_preserving_append([], L) = L.
|
|
inst_preserving_append([H | T], L) = [H | NT] :-
|
|
inst_preserving_append(T, L) = NT.
|
|
|
|
inst_preserving_condense(Xss) = Ys :-
|
|
RevXss = inst_preserving_reverse(Xss),
|
|
inst_preserving_condense_acc(RevXss, [], Ys).
|
|
|
|
:- pred inst_preserving_condense_acc(
|
|
list(list(T))::in(list_skel(list_skel(I =< ground))),
|
|
list(T)::in(list_skel(I =< ground)), list(T)::out(list_skel(I =< ground)))
|
|
is det.
|
|
|
|
inst_preserving_condense_acc([], Ys, Ys).
|
|
inst_preserving_condense_acc([L | Ls], Ys0, Ys) :-
|
|
Ys1 = inst_preserving_append(L, Ys0),
|
|
inst_preserving_condense_acc(Ls, Ys1, Ys).
|
|
|
|
inst_preserving_reverse(Xs) = Ys :-
|
|
inst_preserving_reverse_prepend(Xs, [], Ys).
|
|
|
|
:- pred inst_preserving_reverse_prepend(list(T)::in(list_skel(I =< ground)),
|
|
list(T)::in(list_skel(I =< ground)), list(T)::out(list_skel(I =< ground)))
|
|
is det.
|
|
|
|
inst_preserving_reverse_prepend([], L, L).
|
|
inst_preserving_reverse_prepend([X | Xs], L0, L) :-
|
|
inst_preserving_reverse_prepend(Xs, [X | L0], L).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%---------------------------------------------------------------------------%
|
|
|
|
:- pragma foreign_code("Java", "
|
|
|
|
// We don't use `:- pragma foreign_export' to generate these methods,
|
|
// because the interfaces would expect type_info arguments.
|
|
|
|
// If you need to specify the type parameter, you must use the qualified
|
|
// method name, e.g. list.<Integer>empty_list()
|
|
|
|
public static <E>
|
|
List_1<E> empty_list()
|
|
{
|
|
return new List_1.F_nil_0<E>();
|
|
}
|
|
|
|
public static <E, F extends E>
|
|
List_1<E> cons(F head, List_1<E> tail)
|
|
{
|
|
return new List_1.F_cons_2<E>(head, tail);
|
|
}
|
|
|
|
public static <E>
|
|
boolean is_empty(List_1<E> lst)
|
|
{
|
|
return (lst instanceof List_1.F_nil_0);
|
|
}
|
|
|
|
public static <E>
|
|
E det_head(List_1<E> lst)
|
|
{
|
|
return ((List_1.F_cons_2<E>) lst).F1;
|
|
}
|
|
|
|
public static <E>
|
|
List_1<E> det_tail(List_1<E> lst)
|
|
{
|
|
return ((List_1.F_cons_2<E>) lst).F2;
|
|
}
|
|
|
|
// A wrapper class to allow for-each syntax.
|
|
// You must use a new instance of this class for each loop!
|
|
|
|
public static class ListIterator<E>
|
|
implements java.lang.Iterable<E>, java.util.Iterator<E>
|
|
{
|
|
private List_1<E> lst;
|
|
|
|
public ListIterator(List_1<E> lst)
|
|
{
|
|
this.lst = lst;
|
|
}
|
|
|
|
public java.util.Iterator<E> iterator()
|
|
{
|
|
return this;
|
|
}
|
|
|
|
public boolean hasNext()
|
|
{
|
|
return !is_empty(lst);
|
|
}
|
|
|
|
public E next()
|
|
{
|
|
if (!is_empty(lst)) {
|
|
E head = det_head(lst);
|
|
lst = det_tail(lst);
|
|
return head;
|
|
} else {
|
|
throw new java.util.NoSuchElementException();
|
|
}
|
|
}
|
|
|
|
public void remove()
|
|
{
|
|
throw new java.lang.UnsupportedOperationException();
|
|
}
|
|
}
|
|
").
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
:- pragma foreign_code("C#", "
|
|
public static List_1 empty_list()
|
|
{
|
|
return new List_1.F_nil_0();
|
|
}
|
|
|
|
public static List_1 cons(object head, List_1 tail)
|
|
{
|
|
return new List_1.F_cons_2(head, tail);
|
|
}
|
|
|
|
public static bool is_empty(List_1 lst)
|
|
{
|
|
return (lst is List_1.F_nil_0);
|
|
}
|
|
|
|
public static object det_head(List_1 lst)
|
|
{
|
|
return ((List_1.F_cons_2) lst).F1;
|
|
}
|
|
|
|
public static List_1 det_tail(List_1 lst)
|
|
{
|
|
return ((List_1.F_cons_2) lst).F2;
|
|
}
|
|
").
|
|
|
|
%---------------------------------------------------------------------------%
|
|
:- end_module list.
|
|
%---------------------------------------------------------------------------%
|