9 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 is 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 independent of the size of the solutions, though it is proportional to the number of solutions.