%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1994-2007 The University of Melbourne.
% Copyright (C) 2014-2021, 2024-2025 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: solutions.m.
% Main author: fjh.
% Stability: high.
%
% This module provides operations that compute the set of solutions
% of a predicate that can return more than one solution.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module solutions.
:- interface.

:- import_module bool.
:- import_module list.
:- import_module set.

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

    % solutions/2 collects all the solutions to a predicate and returns
    % them as a list in sorted order, with duplicates removed.
    %
    % solutions_set/2 returns them as a set.
    %
    % unsorted_solutions/2 returns them as an unsorted list with
    % possible duplicates. Since there are an infinite number of such lists,
    % this must be called from a context in which only a single solution
    % is required.
    %
:- pred solutions(pred(T), list(T)).
:- mode solutions(in(pred(out) is multi), out(non_empty_list)) is det.
:- mode solutions(in(pred(out) is nondet), out) is det.

:- func solutions(pred(T)) = list(T).
:- mode solutions(in(pred(out) is multi)) = out(non_empty_list) is det.
:- mode solutions(in(pred(out) is nondet)) = out is det.

:- func solutions_set(pred(T)) = set(T).
:- mode solutions_set(in(pred(out) is multi)) = out is det.
:- mode solutions_set(in(pred(out) is nondet)) = out is det.

:- pred solutions_set(pred(T), set(T)).
:- mode solutions_set(in(pred(out) is multi), out) is det.
:- mode solutions_set(in(pred(out) is nondet), out) is det.

:- pred unsorted_solutions(pred(T), list(T)).
:- mode unsorted_solutions(in(pred(out) is multi), out(non_empty_list))
    is cc_multi.
:- mode unsorted_solutions(in(pred(out) is nondet), out)
    is cc_multi.

:- func aggregate(pred(T), func(T, A) = A, A) = A.
:- mode aggregate(in(pred(out) is multi), in(func(in, in) = out is det), in)
    = out is det.
:- mode aggregate(in(pred(out) is nondet), in(func(in, in) = out is det), in)
    = out is det.

    % aggregate/4 generates all the solutions to a predicate,
    % sorts them and removes duplicates, then applies an accumulator
    % predicate to each solution in turn:
    %
    % aggregate(Generator, AccumulatorPred, Acc0, Acc) <=>
    %   solutions(Generator, Solutions),
    %   list.foldl(AccumulatorPred, Solutions, Acc0, Acc).
    %
:- pred aggregate(pred(T), pred(T, A, A), A, A).
:- mode aggregate(in(pred(out) is multi),
    in(pred(in, in, out) is det), in, out) is det.
:- mode aggregate(in(pred(out) is multi),
    in(pred(in, di, uo) is det), di, uo) is det.
:- mode aggregate(in(pred(out) is nondet),
    in(pred(in, di, uo) is det), di, uo) is det.
:- mode aggregate(in(pred(out) is nondet),
    in(pred(in, in, out) is det), in, out) is det.

    % aggregate2/6 generates all the solutions to a predicate,
    % sorts them and removes duplicates, then applies an accumulator
    % predicate to each solution in turn:
    %
    % aggregate2(Generator, AccumulatorPred, AccA0, AccA, AccB0, AccB) <=>
    %   solutions(Generator, Solutions),
    %   list.foldl2(AccumulatorPred, Solutions, AccA0, AccA, AccB0, AccB).
    %
:- pred aggregate2(pred(T), pred(T, A, A, B, B), A, A, B, B).
:- mode aggregate2(in(pred(out) is multi),
    in(pred(in, in, out, in, out) is det), in, out, in, out) is det.
:- mode aggregate2(in(pred(out) is multi),
    in(pred(in, in, out, di, uo) is det), in, out, di, uo) is det.
:- mode aggregate2(in(pred(out) is nondet),
    in(pred(in, in, out, di, uo) is det), in, out, di, uo) is det.
:- mode aggregate2(in(pred(out) is nondet),
    in(pred(in, in, out, in, out) is det), in, out, in, out) is det.

    % unsorted_aggregate/4 generates all the solutions to a predicate
    % and applies an accumulator predicate to each solution in turn.
    % Declaratively, the specification is as follows:
    %
    % unsorted_aggregate(Generator, AccumulatorPred, Acc0, Acc) <=>
    %   unsorted_solutions(Generator, Solutions),
    %   list.foldl(AccumulatorPred, Solutions, Acc0, Acc).
    %
    % Operationally, however, unsorted_aggregate/4 will call the
    % AccumulatorPred for each solution as it is obtained, rather than
    % first building a list of all the solutions.
    %
:- pred unsorted_aggregate(pred(T), pred(T, A, A), A, A).
:- mode unsorted_aggregate(in(pred(out) is multi),
    in(pred(in, in, out) is det), in, out) is cc_multi.
:- mode unsorted_aggregate(in(pred(out) is multi),
    in(pred(in, in, out) is cc_multi), in, out) is cc_multi.
:- mode unsorted_aggregate(in(pred(out) is multi),
    in(pred(in, di, uo) is det), di, uo) is cc_multi.
:- mode unsorted_aggregate(in(pred(out) is multi),
    in(pred(in, di, uo) is cc_multi), di, uo) is cc_multi.
:- mode unsorted_aggregate(in(pred(muo) is multi),
    in(pred(mdi, di, uo) is det), di, uo) is cc_multi.
:- mode unsorted_aggregate(in(pred(out) is nondet),
    in(pred(in, di, uo) is det), di, uo) is cc_multi.
:- mode unsorted_aggregate(in(pred(out) is nondet),
    in(pred(in, di, uo) is cc_multi), di, uo) is cc_multi.
:- mode unsorted_aggregate(in(pred(out) is nondet),
    in(pred(in, in, out) is det), in, out) is cc_multi.
:- mode unsorted_aggregate(in(pred(out) is nondet),
    in(pred(in, in, out) is cc_multi), in, out) is cc_multi.
:- mode unsorted_aggregate(in(pred(muo) is nondet),
    in(pred(mdi, di, uo) is det), di, uo) is cc_multi.

    % unsorted_aggregate2/6 generates all the solutions to a predicate
    % and applies an accumulator predicate to each solution in turn.
    % Declaratively, the specification is as follows:
    %
    % unsorted_aggregate2(Generator, AccumulatorPred, !Acc1, !Acc2) <=>
    %   unsorted_solutions(Generator, Solutions),
    %   list.foldl2(AccumulatorPred, Solutions, !Acc1, !Acc2).
    %
    % Operationally, however, unsorted_aggregate2/6 will call the
    % AccumulatorPred for each solution as it is obtained, rather than
    % first building a list of all the solutions.
    %
:- pred unsorted_aggregate2(pred(T), pred(T, A, A, B, B), A, A, B, B).
:- mode unsorted_aggregate2(in(pred(out) is multi),
    in(pred(in, in, out, in, out) is det), in, out, in, out) is cc_multi.
:- mode unsorted_aggregate2(in(pred(out) is multi),
    in(pred(in, in, out, in, out) is cc_multi), in, out, in, out) is cc_multi.
:- mode unsorted_aggregate2(in(pred(out) is multi),
    in(pred(in, in, out, di, uo) is det), in, out, di, uo) is cc_multi.
:- mode unsorted_aggregate2(in(pred(out) is multi),
    in(pred(in, in, out, di, uo) is cc_multi), in, out, di, uo) is cc_multi.
:- mode unsorted_aggregate2(in(pred(out) is nondet),
    in(pred(in, in, out, in, out) is det), in, out, in, out) is cc_multi.
:- mode unsorted_aggregate2(in(pred(out) is nondet),
    in(pred(in, in, out, in, out) is cc_multi), in, out, in, out) is cc_multi.
:- mode unsorted_aggregate2(in(pred(out) is nondet),
    in(pred(in, in, out, di, uo) is det), in, out, di, uo) is cc_multi.
:- mode unsorted_aggregate2(in(pred(out) is nondet),
    in(pred(in, in, out, di, uo) is cc_multi), in, out, di, uo) is cc_multi.

    % This is a generalization of unsorted_aggregate which allows the
    % iteration to stop before all solutions have been found.
    % Declaratively, the specification is as follows:
    %
    %   do_while(Generator, Filter, !Acc) :-
    %       unsorted_solutions(Generator, Solutions),
    %       do_while_2(Solutions, Filter, !Acc).
    %
    %   do_while_2([], _, !Acc).
    %   do_while_2([X | Xs], Filter, !Acc) :-
    %       Filter(X, More, !Acc),
    %       (
    %           More = yes,
    %           do_while_2(Xs, Filter, !Acc)
    %       ;
    %           More = no
    %       ).
    %
    % Operationally, however, do_while/4 will call the Filter
    % predicate for each solution as it is obtained, rather than
    % first building a list of all the solutions.
    %
:- pred do_while(pred(T), pred(T, bool, T2, T2), T2, T2).
:- mode do_while(in(pred(out) is multi),
    in(pred(in, out, in, out) is det), in, out) is cc_multi.
:- mode do_while(in(pred(out) is multi),
    in(pred(in, out, di, uo) is det), di, uo) is cc_multi.
:- mode do_while(in(pred(out) is multi),
    in(pred(in, out, di, uo) is cc_multi), di, uo) is cc_multi.
:- mode do_while(in(pred(out) is nondet),
    in(pred(in, out, in, out) is det), in, out) is cc_multi.
:- mode do_while(in(pred(out) is nondet),
    in(pred(in, out, di, uo) is det), di, uo) is cc_multi.
:- mode do_while(in(pred(out) is nondet),
    in(pred(in, out, di, uo) is cc_multi), di, uo) is cc_multi.

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