Previous: , Up: Top   [Contents]


8 All-solutions predicates.

Prolog’s various different all-solutions predicates (findall/3, bagof/3, and setof/3) all have semantic problems. Mercury has a different set of all-solutions predicates (solutions/2, solutions_set/2, and unsorted_solutions/2 — all defined in the library module ‘solutions’) that address the problems of the Prolog versions. To avoid the variable scoping problems of the Prolog versions, rather than taking both a goal to execute and an aliased term holding the resulting value to collect, Mercury’s all-solutions predicates take as input a single higher-order predicate term. The Mercury equivalent to

intersect(List1, List2, Intersection) :-
	setof(X, (member(X, List1), member(X, List2)), Intersection).

is

intersect(List1, List2, Intersection) :-
	solutions((pred(X::out) is nondet :-
	    (list.member(X, List1), list.member(X, List2))), Intersection).

Alternately, this could also be written as

intersect(List1, List2, Intersection) :-
	solutions(member_of_both(List1, List2), Intersection).

:- pred member_of_both(list(T)::in, list(T)::in, T::out) is nondet.
member_of_both(List1, List2, X) :-
	list.member(X, List1), list.member(X, List2).

and in fact that’s exactly how the Mercury compiler implements lambda expressions.

The current implementation of solutions/2 is a “zero-copy” implementation, so the cost of solutions/2 is proportional the number of solutions, but independent of the size of the solutions. (This may change in future implementations.)