Next: , Previous: set_unordlist, Up: Top   [Contents]

## 84 solutions

```%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1994-2007 The University of Melbourne.
% Copyright (C) 2014-2021 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: solutions.m.
% Main author: fjh.
% Stability: medium.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- 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, U) = U, U) = U.
:- 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, U, U), U, U).
:- 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, U, U, V, V), U, U, V, V).
:- 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, U, U), U, U).
:- 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, U, U, V, V), U, U, V, V).
:- 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.

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

```

Next: , Previous: set_unordlist, Up: Top   [Contents]