Eliminate consecutive duplicates

Question

Eliminate consecutive duplicates of list elements.

My solution for this is:

compress([X,X|Xs], Q) :-
   compress([X|Xs], Q).
compress([X,Y|Xs], Q) :-
   X \= Y,
   compress([Y|Xs], QR),
   append([X], QR, Q).
compress([X|[]], Q) :-
   compress([], QR),
   append([X], QR, Q).
compress([], []).

And, because of the fact I am beginner and I have no experience in a logic paradigm I ask you for say what I can improve and why my solution is not good as it can be.

For example, X \= Y doesn't look pretty to me.

score 5 · Accepted Answer · answered May 22 '16 at 15:38

We start with the name of the predicate.

Why do you use an imperative to denote a relation? A good Prolog program is usable in all directions, whereas an imperative always suggests a particular direction or mode of use. Therefore, choose a declarative name and aim for generality and logical-purity.

Next, what about the most general query:

?- compress(Ls, Cs).
ERROR: Out of local stack

Not very nice! We expect this to yield at least a few answers.

What if we use iterative deepening:

?- length(Ls, _), compress(Ls, Cs).
Ls = Cs, Cs = [] ;
Ls = Cs, Cs = [_G841] ;
Ls = [_G841, _G841],
Cs = [_G841] ;
Ls = [_G841, _G841, _G841],
Cs = [_G841] .

Hm! Quite a few answers are missing! What about the case where the elements are different? As you already intuitively expect, it is the use of impure predicates that leads to such effects.

Therefore, use prolog-dif, i.e., dif/2, to denote that two terms are different. It's usable in all directions!

Moreover, DCGs (dcg) are often useful when describing lists.

So, in total, what about this:

compression([])     --> [].
compression([L|Ls]) --> [L], compression_(Ls, L).

compression_([], _) --> [].
compression_([X|Xs], L) -->
        (   { X = L },
            compression_(Xs, L)
        ;   { dif(X, L) },
            [X],
            compression_(Xs, X)
        ).

We use the interface predicate phrase/2 to work with the DCG.

Usage examples:

?- phrase(compression(Ls), Cs).
Ls = Cs, Cs = [] ;
Ls = Cs, Cs = [_G815] ;
Ls = [_G815, _G815],
Cs = [_G815] .

?- length(Ls, _), phrase(compression(Ls), Cs).
Ls = Cs, Cs = [] ;
Ls = Cs, Cs = [_G865] ;
Ls = [_G865, _G865],
Cs = [_G865] ;
Ls = Cs, Cs = [_G1111, _G1114],
dif(_G1114, _G1111) .

Take it from here! Improve determinism, find an even better name etc.

You messed up in my head! But it is a very good information becasue it means a progress! :) . Let's try to understand: "Therefore, use prolog-dif, i.e., dif/2, to denote that two terms are different. It's usable in all directions!" I don't understand why I should `dif/2 ` instead of `\=` ? Especially, you highlight *directions*. What do you mean exactly because I can't get it. — Gilgamesz, May 22 '16 at 16:21
`"length(Ls, _), compress(Ls, Cs). Ls = Cs, Cs = [] ; Ls = Cs, Cs = [_G841] ; Ls = [_G841, _G841], Cs = [_G841] ; Ls = [_G841, _G841, _G841], Cs = [_G841] ."`. What did you want to show me in that code? :) — Gilgamesz, May 22 '16 at 16:22
"Not very nice! We expect this to yield at least a few answers." Ideed, you right. But what is an expected behaviour here? After all, in `compress(Ls, Cs)` `Ls` is not a list so it should be something like undefined behaviour ( yes, I am programming in C++ ;) ) — Gilgamesz, May 22 '16 at 16:24
We are defining *relations*, and we expect to be able to use them in all modes: All arguments instantiated: Check them. No argument instantiated: Generate some solutions or answers. Arguments partially instantiated: Fill in missing details. Your initial predicate falls short in one or more of these aspects: It loops, omits answers, succeeds wrongly etc. Try it in different usage modes, not only if one list is fully instantiated! Try variables, partially instantiated lists and so on. — mat, May 22 '16 at 17:32

score 4 · Answer 2 · edited May 23 '17 at 12:31

Building on the answer by @mat (+1), why not improve determinacy for cases like this one:

?- phrase(compression([a,a,b,b,b,c,c,c,c,d]), Xs).
Xs = [a, b, c, d] ;
false.

With ; false the SWI prolog-toplevel indicates that the goal did not succeed deterministically.

We can improve compression_//2 by using if_//3—the dcg analogue of if_/3:

compression_([], _) --> [].
compression_([X|Xs], L) -->
   if_(X = L,                           % is this item equal to previous one?
       compression_(Xs, L),             %   yes: old "run" goes on
       ([X], compression_(Xs, X))).     %    no: new "run" starts

Sample query:

?- phrase(compression([a,a,b,b,b,c,c,c,c,d]), Xs).
Xs = [a, b, c, d].                            % succeeds deterministically

Eliminate consecutive duplicates

2 Answers2