64 solutions
%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%--------------------------------------------------%
% Copyright (C) 1994-2007 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% 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(pred(out) is multi, out(non_empty_list)) is det.
:- mode solutions(pred(out) is nondet, out) is det.
:- func solutions(pred(T)) = list(T).
:- mode solutions(pred(out) is multi) = out(non_empty_list) is det.
:- mode solutions(pred(out) is nondet) = out is det.
:- func solutions_set(pred(T)) = set(T).
:- mode solutions_set(pred(out) is multi) = out is det.
:- mode solutions_set(pred(out) is nondet) = out is det.
:- pred solutions_set(pred(T), set(T)).
:- mode solutions_set(pred(out) is multi, out) is det.
:- mode solutions_set(pred(out) is nondet, out) is det.
:- pred unsorted_solutions(pred(T), list(T)).
:- mode unsorted_solutions(pred(out) is multi, out(non_empty_list))
is cc_multi.
:- mode unsorted_solutions(pred(out) is nondet, out) is cc_multi.
:- func aggregate(pred(T), func(T, U) = U, U) = U.
:- mode aggregate(pred(out) is multi, func(in, in) = out is det, in)
= out is det.
:- mode aggregate(pred(out) is nondet, 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, Accumulator, Acc0, Acc) <=>
% solutions(Generator, Solutions),
% list.foldl(Accumulator, Solutions, Acc0, Acc).
%
:- pred aggregate(pred(T), pred(T, U, U), U, U).
:- mode aggregate(pred(out) is multi, pred(in, in, out) is det,
in, out) is det.
:- mode aggregate(pred(out) is multi, pred(in, di, uo) is det,
di, uo) is det.
:- mode aggregate(pred(out) is nondet, pred(in, di, uo) is det,
di, uo) is det.
:- mode aggregate(pred(out) is nondet, 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, Accumulator, AccA0, AccA, AccB0, AccB) <=>
% solutions(Generator, Solutions),
% list.foldl2(Accumulator, Solutions, AccA0, AccA, AccB0, AccB).
%
:- pred aggregate2(pred(T), pred(T, U, U, V, V), U, U, V, V).
:- mode aggregate2(pred(out) is multi, pred(in, in, out, in, out) is det,
in, out, in, out) is det.
:- mode aggregate2(pred(out) is multi, pred(in, in, out, di, uo) is det,
in, out, di, uo) is det.
:- mode aggregate2(pred(out) is nondet, pred(in, in, out, di, uo) is det,
in, out, di, uo) is det.
:- mode aggregate2(pred(out) is nondet, 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, Accumulator, Acc0, Acc) <=>
% unsorted_solutions(Generator, Solutions),
% list.foldl(Accumulator, Solutions, Acc0, Acc).
%
% Operationally, however, unsorted_aggregate/4 will call the
% Accumulator 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(pred(out) is multi, pred(in, in, out) is det,
in, out) is cc_multi.
:- mode unsorted_aggregate(pred(out) is multi, pred(in, in, out) is cc_multi,
in, out) is cc_multi.
:- mode unsorted_aggregate(pred(out) is multi, pred(in, di, uo) is det,
di, uo) is cc_multi.
:- mode unsorted_aggregate(pred(out) is multi, pred(in, di, uo) is cc_multi,
di, uo) is cc_multi.
:- mode unsorted_aggregate(pred(muo) is multi, pred(mdi, di, uo) is det,
di, uo) is cc_multi.
:- mode unsorted_aggregate(pred(out) is nondet, pred(in, di, uo) is det,
di, uo) is cc_multi.
:- mode unsorted_aggregate(pred(out) is nondet, pred(in, di, uo) is cc_multi,
di, uo) is cc_multi.
:- mode unsorted_aggregate(pred(out) is nondet, pred(in, in, out) is det,
in, out) is cc_multi.
:- mode unsorted_aggregate(pred(out) is nondet, pred(in, in, out) is cc_multi,
in, out) is cc_multi.
:- mode unsorted_aggregate(pred(muo) is nondet, 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, Accumulator, !Acc1, !Acc2) <=>
% unsorted_solutions(Generator, Solutions),
% list.foldl2(Accumulator, Solutions, !Acc1, !Acc2).
%
% Operationally, however, unsorted_aggregate2/6 will call the
% Accumulator 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(pred(out) is multi,
pred(in, in, out, in, out) is det, in, out, in, out) is cc_multi.
:- mode unsorted_aggregate2(pred(out) is multi,
pred(in, in, out, in, out) is cc_multi, in, out, in, out) is cc_multi.
:- mode unsorted_aggregate2(pred(out) is multi,
pred(in, in, out, di, uo) is det, in, out, di, uo) is cc_multi.
:- mode unsorted_aggregate2(pred(out) is multi,
pred(in, in, out, di, uo) is cc_multi, in, out, di, uo) is cc_multi.
:- mode unsorted_aggregate2(pred(out) is nondet,
pred(in, in, out, in, out) is det, in, out, in, out) is cc_multi.
:- mode unsorted_aggregate2(pred(out) is nondet,
pred(in, in, out, in, out) is cc_multi, in, out, in, out) is cc_multi.
:- mode unsorted_aggregate2(pred(out) is nondet,
pred(in, in, out, di, uo) is det, in, out, di, uo) is cc_multi.
:- mode unsorted_aggregate2(pred(out) is nondet,
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)
% ;
% true
% ).
%
% 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(pred(out) is multi, pred(in, out, in, out) is det, in, out)
is cc_multi.
:- mode do_while(pred(out) is multi, pred(in, out, di, uo) is det, di, uo)
is cc_multi.
:- mode do_while(pred(out) is multi, pred(in, out, di, uo) is cc_multi, di, uo)
is cc_multi.
:- mode do_while(pred(out) is nondet, pred(in, out, in, out) is det, in, out)
is cc_multi.
:- mode do_while(pred(out) is nondet, pred(in, out, di, uo) is det, di, uo)
is cc_multi.
:- mode do_while(pred(out) is nondet, pred(in, out, di, uo) is cc_multi, di, uo)
is cc_multi.
%--------------------------------------------------%
%--------------------------------------------------%