`var (A)` and execution order

Question

Exercise 09 on this page http://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/ asks you to create a predicate that contains duplicate elements in the lists.

Simple solution is simple

pack([], []). pack([H|T], [I|U]) :- split(H, T, I, P), pack(P, U). 

where split split(Head, Tail, HeadGroup, Rest) is defined as

 split(A, [], [A], []). split(A, [B|T], [A], [B|T]) :- A \= B. split(A, [A|T], [A|U], B) :- split(A, T, U, B). 

which works great and pretty much matches the example solution presented on the aforementioned web page.

If this solution fails, these are requests of type pack(X, [[a], [b, b]]). . The correspondence between the two sets of solutions is bijective (for each A in pack(A, B) there is one and only one B ), therefore there should be a better solution.

One way to solve it is to change the evaluation order, helping the prolog to select a non-infinite branch depending on the type of argument, for example, the following

 pack([], []). pack(A, B) :- ( var(A) -> A = [H|T], B = [I|U], pack(P, U), split(H, T, I, P) ; A = [H|T], B = [I|U], split(H, T, I, P), pack(P, U) ). 

Two questions in this regard.

Firstly, it is incredibly ugly, so maybe the best way to choose the order of rules depending on the type of argument?

Secondly, perhaps a much more complex question is, is there a way to rewrite the solution without var(A) , and if not why?

Answer 1

From a declarative point of view, nonmonotonic constructions such as var/1 and (\=)/2 are very problematic .

Why? Check it:

 ?- var(A), A=a. A = a. ?- A=a, var(A). false. 

So, this breaks the connection with switching , which is one of the main properties that we rely on when we really talk about logical programs.

What about (\=)/2 , which in your opinion expresses that the two terms are different? Check it:

  ? - X \ = Y.
 false

There are no two different terms , right? It seems a little strange for me, to put it mildly, therefore, apparently, the predicate really means something else.

Fortunately, in your case the solution is very simple. Just use the pure dif/2 constraint to indicate that the two members are distinct. See prolog-dif for more information. You only need to change one line of code to make your solution much more general. Instead:

 split(A, [B|T], [A], [B|T]) :- A \= B. 

just use dif/2 :

  split (A, [B | T], [A], [B | T]): - dif (A, B) .

With this change, your example works fully as expected:

 ?- pack(X, [[a], [b, b]]). X = [a, b, b] ; false. 

Note that the existing Prolog literature is obsolete , and most such solution sets come from the time when dif/2 not even available on most Prolog systems, of course, not in free ones.