Search code examples
prologminmember

Find smallest list under conditions

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?

Solution

  • Both your code and the code in the answer of @TessellatingHacker lose 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 .

    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 .

    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!