Find smallest list under conditions

Question

In SWI-Prolog I want to establish the list L from two lists L1 and L2 with the smallest count of elements under the condition, that 1 ∈ L1 and 1 ∈ L2. If 1 ∉ L1 and 1 ∈ L2, then L = L1. If 1 ∈ L1 and 1 ∉ L2, then L = L2. If 1 ∉ L1 and 1 ∉ L2, then the predicate returns false.

I could evaluate this in Prolog with the following conditions:

minset_one(D1, D2, T) :- ((member(1, D1), not(member(1, D2))) -> T=D1).
minset_one(D1, D2, T) :- ((not(member(1, D1)), member(1, D2)) -> T=D2).
minset_one(D1, D2, T) :- (member(1, D1), member(1, D2), length(D1,L1), length(D2,L2), L1 >= L2) -> T=D2.
minset_one(D1, D2, T) :- (member(1, D1), member(1, D2), length(D1,L1), length(D2,L2), L2 > L1) -> T=D1.

My problem with that function is, the member function is called very often. Is their a way to reduce the complexity of that predicate in that way, the functions

• member(1, D1)
• member(1, D2)
• length(D1, L1)
• length(D2, L2)

are called only one time?

Answer 1

Both your code and the code in the answer of @TessellatingHacker lose logical-purity when the arguments of minset_one/3 are not sufficiently instantiated:

?- D1 = [X,Y,Z], D2 = [U,V], minset_one(D1,D2,T).
   D1 = [1,Y,Z], D2 = [1,V], T = D2
;  false.                           % no more solutions!

This is clearly incomplete. There are other solutions. We lost logical-purity.

So, what can we do about this? Basically, we have two options:

1. check D1, D2 and T upfront and throw an instantiation_error when the instantiation is not sufficient.
2. use building blocks that are better suited for code that preserves logical-purity.

---

In this answer I want to show how to realise option number two.

The code is based on if_/3 which is the core of library(reif). In short, we reify the truth values of relations and use Prolog indexing on these values.

Using SWI-Prolog 8.4.2:

?- use_module(library(reif)).

First, shorter_than_t(Xs,Ys,T) reifies "list Xs is shorter than Ys" into T:

shorter_than_t([],Ys,T) :-
   aux_nil_shorter_than(Ys,T).
shorter_than_t([_|Xs],Ys,T) :-
   aux_cons_shorter_than_t(Ys,Xs,T).

aux_nil_shorter_than_t([],false).
aux_nil_shorter_than_t([_|_],true).

aux_cons_shorter_than_t([],_,false).
aux_cons_shorter_than_t([_|Ys],Xs,T) :-
   shorter_than_t(Xs,Ys,T).

Based on shorter_than_t/3 we define minset_one/3:

minset_one(D1,D2,T) :-
   if_(shorter_than_t(D1,D2),
       if_(memberd_t(1,D1), D1=T, (memberd_t(1,D2,true),D2=T)),
       if_(memberd_t(1,D2), D2=T, (memberd_t(1,D1,true),D1=T))).

Now let's run above query again:

?- D1 = [X,Y,Z], D2 = [U,V], minset_one(D1,D2,T).
   D1 = [X,Y,Z], D2 = [1,V], T = D2
;  D1 = [X,Y,Z], D2 = [U,1], T = D2, dif(U,1)
;  D1 = [1,Y,Z], D2 = [U,V], T = D1, dif(U,1), dif(V,1)
;  D1 = [X,1,Z], D2 = [U,V], T = D1, dif(U,1), dif(V,1), dif(X,1)
;  D1 = [X,Y,1], D2 = [U,V], T = D1, dif(U,1), dif(V,1), dif(X,1), dif(Y,1)
;  false.

At last, minset_one/3 has become complete!

Answer 2

I think you could do it with a wrapper / helper predicate which does those checks once, and then does a lookup of some fixed answers:

% minset_one(1 in D1, 1 in D2, D1, D2, D1Len, D2Len, T).
minset_one_(true,  false, D1, _,  _,     _,     D1).
minset_one_(false, true,  _,  D2, _,     _,     D2).
minset_one_(true,  true,  _,  D2, D1Len, D2Len, D2) :- D1Len >= D2Len.
minset_one_(true,  true,  D1, _,  D1Len, D2Len, D1) :- D1Len < D2Len.

minset_one(D1, D2, T) :-
    (member(1, D1) -> D1check = true ; D1check = false),
    (member(1, D2) -> D2check = true ; D2check = false),
    length(D1, D1Len),
    length(D2, D2Len),
    
    minset_one_(D1check, D2check, D1, D2, D1Len, D2Len, T).