[mercury-users] Equivalent of Prolog setof with free variable

[Jeff Thompson]

On 1/25/2012 7:53 AM, Julien Fischer wrote:
>
> Hi,
>
> On Tue, 24 Jan 2012, Jeff Thompson wrote:
>
>> Hello.  What is the preferred way in Mercury to implement the 
>> equivalent of setof with a free variable.  For example, Prolog:
>>
>> person(bob, accounting).
>> person(alice, accounting).
>> person(fred, sales).
>>
>> departmentMembers(Department, People) :-
>>  setof(Person, person(Person, Department), People).
>>
>> Calling departmentMembers returns multiple times with results for the 
>> free variable:
>> Department = accounting,
>> People = [alice, bob] ;
>>
>> Department = sales,
>> People = [fred].
>>
>> What is the preferred way to get this in Mercury?
>
> As Michael has mentioned, you will need to use the all-solutions
> predicates from the standard library's solutions module.
>
> A possible Mercury implementation of the above is:
>
>     :- module foo.
>     :- interface.
>     :- pred main(io::di, io::uo) is det.
>     :- implementation.
>
>     :- import_module list.
>     :- import_module set.
>     :- import_module solutions.
>     :- import_module string.
>
>     :- type person ---> alice ; bob ; fred.
>
>     :- type department ---> accounting ; sales.
>
>     :- pred departmentMembers({department, list(person)}::out) is multi.
>
>     departmentMembers({Department, People}) :-
>        person(_, Department),
>        solutions((pred(P::out) is multi :- person(P, Department)), 
> People).
>
>     :- pred person(person, department).
>     :- mode person(out, in) is multi.
>     :- mode person(out, out) is multi.
>
>     person(bob, accounting).
>     person(alice, accounting).
>     person(fred, sales).
>
> And since Mercury doesn't have an interactive top-level:
>
>     main(!IO) :-
>         solutions(departmentMembers, Solns),
>         io.write_list(Solns, "\n\n", output_soln, !IO),
>         io.nl(!IO).
>
>     :- pred output_soln({department, list(person)}::in, io::di, 
> io::uo) is det.
>
>     output_soln({Department, People}, !IO) :-
>         io.format("Department = %s,\nPeople = %s",
>         [s(string(Department)), s(string(People))], !IO).
>
> Julien.

I'm looking for a single-pass implementation, since departmentMembers 
above makes multiple passes through person. (While person is a simple 
lookup, imagine a more complicated predicate where multiple passes is 
expensive.)  I implemented a bagof predicate (see below) so that 
departmentMembers changes to:

departmentMembers({Department, People}):-
   bagof((pred(D - P ::out) is multi :- person(P, D)), Department, People).

Since I'm a newbie to Mercury, I wonder if there is a more efficient 
implementation supported by the compiler than my version below.

Thanks again,
- Jeff

:- pred bagof(pred(pair(K, V)), K, list(V)).
:- mode bagof(pred(out) is multi, out, out) is nondet.
bagof(Generator, Key, ValueList) :-
   promise_equivalent_solutions([Map], unsorted_aggregate(Generator, 
prependForKey, map.init, Map)),
   map.member(Map, Key, ValueList).

:- pred prependForKey(pair(K, V)::in, map(K, list(V))::in, map(K, 
list(V))::out) is det.
prependForKey(Key - Value, MapIn, MapOut) :-
   if ValueListIn = map.search(MapIn, Key) then
     MapOut = map.set(MapIn, Key, [Value|ValueListIn])
   else
     % MapIn doesn't have Key.
     MapOut = map.det_insert(MapIn, Key, [Value]).



--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------