Collect all the "minimal" solutions from the predicate

Question

Given the following facts in the database:

foo(a, 3). foo(b, 2). foo(c, 4). foo(d, 3). foo(e, 2). foo(f, 6). foo(g, 3). foo(h, 2). 

I want to collect all the first arguments that have the smallest second argument, plus the value of the second argument. First try:

 find_min_1(Min, As) :- setof(BA, foo(A, B), [Min-_|_]), findall(A, foo(A, Min), As). ?- find_min_1(Min, As). Min = 2, As = [b, e, h]. 

Instead of setof/3 I could use aggregate/3 :

 find_min_2(Min, As) :- aggregate(min(B), A^foo(A, B), Min), findall(A, foo(A, Min), As). ?- find_min_2(Min, As). Min = 2, As = [b, e, h]. 

NB

This only gives the same results if I am looking for a minimum number . If an arithmetic expression is involved, the results may be different. If not a number is involved, aggregate(min(...), ...) will throw an error!

Or instead, I can use a complete list sorted by key:

 find_min_3(Min, As) :- setof(BA, foo(A, B), [Min-First|Rest]), min_prefix([Min-First|Rest], Min, As). min_prefix([Min-First|Rest], Min, [First|As]) :- !, min_prefix(Rest, Min, As). min_prefix(_, _, []). ?- find_min_3(Min, As). Min = 2, As = [b, e, h]. 

Finally, to the question (s):

• Can I do this directly using the library (aggregate)? Looks like it should be possible ....

• Or is there a predicate like std::partition_point from the C ++ standard library?

• Or is there an easier way to do this?

EDIT:

To be more visual. Say there was a predicate (library) partition_point/4 :

 partition_point(Pred_1, List, Before, After) :- partition_point_1(List, Pred_1, Before, After). partition_point_1([], _, [], []). partition_point_1([H|T], Pred_1, Before, After) :- ( call(Pred_1, H) -> Before = [H|B], partition_point_1(T, Pred_1, B, After) ; Before = [], After = [H|T] ). 

(I don't like the name, but we can live with it for now)

Then:

 find_min_4(Min, As) :- setof(BA, foo(A, B), [Min-X|Rest]), partition_point(is_min(Min), [Min-X|Rest], Min_pairs, _), pairs_values(Min_pairs, As). is_min(Min, Min-_). ?- find_min_4(Min, As). Min = 2, As = [b, e, h]. 

Answer 1

Using library(pairs) and [ sort/4 ], this can simply be written as:

 ?- bagof(BA, foo(A, B), Ps), sort(1, @=<, Ps, Ss), % or keysort(Ps, Ss) group_pairs_by_key(Ss, [Min-As|_]). Min = 2, As = [b, e, h]. 

This call to sort/4 can be replaced with keysort/2 , but with sort/4 you can also find, for example, the first arguments associated with the largest second argument: just use @>= as the second argument.

This solution is probably not as efficient as time and space than others, but it may be easier to run grok.

But there is another way to do this:

 ?- bagof(A, ( foo(A, Min), \+ ( foo(_, Y), Y @< Min ) ), As). Min = 2, As = [b, e, h]. 

Answer 2

What is an idiomatic approach to this class of problems?

Is there a way to simplify the problem?

Many of the following comments can be added to many programs here on SO.

Imperative names

Each time you write an imperative name for something that is an attitude, you will decrease your understanding of relationships. A little bit. Many common Prolog idioms, such as append/3 , do not set a good example. Think of append(As,As,AsAs) . The first argument to find_min(Min, As) is the minimum. Therefore, minimum_with_nodes/2 may be the best name.

findall/3

Do not use findall/3 if usage is strictly verified, essentially everything should be grounded. In your case it works. But as soon as you generalize foo/2 little, you lose. And this is often a problem: you are writing a tiny program; and it seems to work. Once you move to larger ones, the same approach no longer works. findall/3 (compared to setof/3 ), like a bull in a porcelain shop breaking up the thin fabric of common variables and quantifying. Another problem is that accidental failure does not cause findall/3 to crash, which often leads to strange, it is difficult to imagine angular cases.

Difficult, too specific program

Another problem is somewhat related to findall/3 . Your program is so specific that it is highly unlikely that you will ever test it. And marginal changes will nullify your tests. Thus, you will soon give up testing. Let's see what exactly: first of all, the ratio foo/2 . Yes, just an example. Think about how to set up a test configuration where foo/2 might change. After each change (writing a new file) you will have to restart the program. It's so complicated, most likely you will never do it. I assume you do not have a test harness. Plunit for one, does not apply to such testing. As a rule of thumb: if you cannot check the predicate at the top level, you will never Consider instead

minimum_with(Rel_2, Min, Els)

With this ratio, you can now get generalized xfoo/3 with an additional parameter, for example:

 xfoo(o, A,B) :- foo(A,B). xfoo(n, A,B) :- newfoo(A,B). 

and you will naturally get two answers for minimum_with(xfoo(X), Min, Els) . You would use findall/3 instead of setof/3 , you would already have serious problems. Or simply in general: minmum_with(\A^B^member(AB, [x-10,y-20]), Min, Els) . Thus, you can play at the top level and create many interesting test cases.

Unverified Boundary Cases

Your version 3 is obviously my preferred approach, however there are some parts that can be improved. In particular, if there are answers containing at least variables. They must be checked.

And of course, also setof/3 has its limits. And ideally, you would test them. Responses should not contain restrictions, in particular, not in the corresponding variables. This shows how setof/3 has certain limits. After the pioneering phase, SICStus issued many errors for restrictions in such cases (in the mid-1990s), and then changed to, therefore, ignore restrictions in the built-in modules that cannot handle them. SWI, on the other hand, makes it completely undefined here. Sometimes things are copied, sometimes not. As an example, take: setof(A, ( A in 1..3 ; A in 3..5 ), _) and setof(t, ( A in 1..3 ; A in 3.. 5 ), _) .

By wrapping the target, this can be avoided.

 call_unconstrained(Goal_0) :- call_residue_vars(Goal_0, Vs), ( Vs = [] -> true ; throw(error(representation_error(constraint),_)) ). 

Beware, however, that the SWI has false limitations:

 ?- call_residue_vars(all_different([]), Xs). Xs = [_G1130]. 

It is unclear whether this is in the meantime. He has been there since the introduction of call_residue_vars/2 about 5 years ago.

Answer 3

I do not think the library (collection) covers your use case. aggregate (min) allows one witness:

min (Expr, Witness) The term min (Min, Witness), where Min is the minimum version of Expr for all solutions, and Witness is any other template that applies to solutions that produce Min. If multiple solutions provide the same minimum, Witness matches the first solution.

Some time ago, I wrote a small “library”, lag.pl , with predicates for aggregation with little overhead - that’s where the name comes from (LAG = linear AGgregate). I added a snippet that handles your use case:

 integrate(min_list_associated, Goal, Min-Ws) :- State = term(_, [], _), forall(call(Goal, V, W), % W stands for witness ( arg(1, State, C), % C is current min arg(2, State, CW), % CW are current min witnesses ( ( var(C) ; V @< C ) -> U = V, Ws = [W] ; U = C, ( C == V -> Ws = [W|CW] ; Ws = CW ) ), nb_setarg(1, State, U), nb_setarg(2, State, Ws) )), arg(1, State, Min), arg(2, State, Ws). 

This is a simple mental extension of the integration (min) ... The comparison method is undoubtedly doubtful (it uses a less general operator for equality), it may be worthwhile to use a regular call like the one accepted for predsort / 3 instead . Efficiency, all the better, would be to code the comparison method as an option in the "function selector" (min_list_associated in this case)

edit thanks @false and @Boris to fix the error regarding the state view. Calling nb_setarg(2, State, Ws) actually changes the term "form" when State = (_,[],_) . The github repo will be updated accordingly ...