`var(A)` and order of execution

Question

Exercise 09 on this page http://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/ asks to create a predicate that packs repeated elements into sublists.

A straightforward solution is straightforward

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

where split is 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 fine and is pretty much in line with the example solution provided on the above-mentioned webpage.

Where this solution fails are the queries like pack(X, [[a], [b, b]]).. The correspondence between two solution sets is bijective (for every A in pack(A, B) there is one and only one B), so there must be a better solution.

One way to resolve it is to change the order of evaluation, helping prolog to pick non infinite branch depending on type of the argument like 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, this is unbelievably ugly, so is there maybe a better way to pick order of rules depending on argument type?

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

Industrials

Answer 1

From a declarative point of view, non-monotonic constructs like var/1 and (\=)/2 are very problematic.

Why? Check it out:

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

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

So, this breaks commutativity of conjunction, which is one of the core properties we rely on when actually reasoning about logic programs.

What about (\=)/2, which you thought would express that two terms are different? Check it out:

?- X \= Y.
false.

No two terms that are different exist, yes? Seems a bit strange to me, to say the least, so apparently the predicate really means something else.

Luckily, in your case, the solution is very easy. Simply use the pure constraint dif/2 to denote that two terms are different. See prolog-dif for more information. You only have to change a single line of code to make your solution much more general. Instead of:

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

simply use dif/2:

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

With this change, your example works completely as expected:

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

Note that the existing Prolog literature is way outdated, and most such sets of solutions come from a time where dif/2 was not even available in most Prolog systems, certainly not in free ones.

Quarles

Pure genius! With dif it now can even solve the crazy stuff like pack(A, [X, [b]]).. – Industrials

Gonna revisit all my previous solutions. – Industrials

Yes, it is. dif/2 was available even in the very first Prolog system, then by and large ignored by implementors, and now is getting increasingly common in implementations again. Reasoning in all directions is, after all, one of the major attractions of relational programming, so use dif/2 to express term disequality in a sound and general way. – Quarles