Sunday, April 30, 2017

(SWI)Prolog: Order of sub-goals

By Hường Hana 4:00 PM Leave a Comment

I have two, slightly different, implementations of a predicate, unique_element/2, in Prolog. The predicate succeeds when given an element X and a list L, the element X appears only once in the list. Below are the implementations and the results:

Implementation 1: 

%%% unique_element/2 unique_element(Elem, [Elem|T]) :-     not(member(Elem, T)).  unique_element(Elem, [H|T]) :-     member(Elem, T),      H\==Elem,      unique_element(Elem, T),      !.

Results: 

?- unique_element(X, [a, a, b, c, c, b]).  false.  ?- unique_element(X, [a, b, c, c, b, d]). X = a ; X = d.

Implementation 2:

%%% unique_element/2 unique_element(Elem, [Elem|T]) :-      not(member(Elem, T)).  unique_element(Elem, [H|T]) :-     H\==Elem,      member(Elem, T),      unique_element(Elem, T),      !.

In case you didn't notice at first sight: "H\==Elem" and "member(Elem, T)" are flipped on the 2nd impl, rule 2.

Results: 

?- unique_element(X, [a, a, b, c, c, b]). X = a.  ?- unique_element(X, [a, b, c, c, b, d]). X = a ; X = d.

Question: How does the order, in this case, affect the result? I realize that the order of the rules/facts/etc matters. The two specific rules that are flipped though, don't seem to be "connected" or affect each other somehow (e.g. a "cut" predicate in the wrong place/order).

Note: We are talking about SWI-Prolog here.

Note 2: I am aware of, probably different and better implementations. My question here is about the order of sub-goals being changed.

4 Answers

Answers 1

TL;DR: Read the documentation and figure out why:

?- X = a, X \== a. false.  ?- X \== a, X = a. X = a.

I wonder why you stop so close from figuring it out yourself ;-)

There are too many ways to compare things in Prolog. At the very least, you have unification, which sometimes can compare, and sometimes does more; than you have equvalence, and its negation, the one you are using. So what does it do:

?- a \== b. % two different ground terms true.  ?- a \== a. % the same ground term false.

Now it gets interesting:

?- X \== a. % a free variable and a ground term true.  ?- X \== X. % the same free variable false.  ?- X \== Y. % two different free variables true.

I would suggest that you do the following: figure out how member/2 does its thing (does it use unification? equivalence? something else?) then replace whatever member/2 is using in all the examples above and see if the results are any different.

And since you are trying to make sure that things are different, try out what dif/2 does. As in:

?- dif(a, b).

or

?- dif(X, X).

or

?- dif(X, a).

and so on.

See also this question and answers: I think the answers are relevant to your question.

Hope that helps.

Answers 2

H\==Elem is testing for syntactic inequality at the point in time when the goal is executed. But later unification might make variables identical:

?- H\==Elem, H = Elem. H = Elem.  ?- H\==Elem, H = Elem, H\==Elem. false.

So here we test if they are (syntactically) different, and then they are unified nevertheless and thus are no longer different. It is thus just a temporary test.

The goal member(Elem, T) on the other hand is true if that Elem is actually an element of T. Consider:

 ?- member(Elem, [X]).  Elem = X.

Which can be read as

(When) does it hold that Elem is an element of the list [X]?

and the answer is

It holds under certain circumstances, namely when Elem = X.

If you now mix those different kinds of goals in your programs you get odd results that can only explained by inspecting your program in detail.

As a beginner, it is best to stick to the pure parts of Prolog only. In your case:

  • use dif/2 in place of \==

  • do not use cuts - in your case it limits the number of answers to two. As in unique_element(X, [a,b,c])

  • do not use not/1 nor (\+)/1. It produces even more incorrectness. Consider unique_element(a,[a,X]),X=b. which incorrectly fails while X=b,unique_element(a,[a,X]) correctly succeeds.

Here is a directly purified version of your program. There is still room for improvement!

non_member(_X, []). non_member(X, [E|Es]) :-    dif(X, E),    non_member(X, Es).  unique_element(Elem, [Elem|T]) :-      non_member(Elem, T).  unique_element(Elem, [H|T]) :-     dif(H,Elem),       % member(Elem, T),          % makes unique_element(a,[b,a,a|Xs]) loop     unique_element(Elem, T).  ?- unique_element(a,[a,X]).    dif(X, a) ;  false.              % superfluous  ?- unique_element(X,[E1,E2,E3]).    X = E1,    dif(E1, E3),    dif(E1, E2) ;  X = E2,    dif(E2, E3),    dif(E1, E2) ;  X = E3,    dif(E2, E3),    dif(E1, E3) ;  false.

Note how the last query reads?

When is X a unique element of (any) list [E1,E2,E3]?

The answer is threefold. Considering one element after the other:

X is E1 but only if it is different to E2 and E3

etc.

Answers 3

Can you not define unique_element like tcount Prolog - count repetitions in list

unique_element(X, List):- tcount(=(X),List,1).

Answers 4

Here is another possibility do define unique_element/2 using if_/3 and maplist/2:

:- use_module(library(apply)).  unique_element(Y,[X|Xs]) :-    if_(Y=X,maplist(dif(Y),Xs),unique_element(Y,Xs)).

In contrast to @user27815's very elegant solution (+s(0)) this version does not build on clpfd (used by tcount/3). The example queries given by the OP work as expected:

   ?- unique_element(a,[a, a, b, c, c, b]). no    ?- unique_element(X,[a, b, c, c, b, d]). X = a ? ; X = d ? ; no

The example provided by @false now succeeds without leaving a superfluous choicepoint:

   ?- unique_element(a,[a,X]). dif(a,X)

The other more general query yields the same results:

   ?- unique_element(X,[E1,E2,E3]). E1 = X, dif(X,E3), dif(X,E2) ? ; E2 = X, dif(X,E3), dif(X,E1) ? ; E3 = X, dif(X,E2), dif(X,E1) ? ; no
If You Enjoyed This, Take 5 Seconds To Share It

0 comments:

Post a Comment