Prolog compressing list

Question

I have a strange problem that I do not know how to solve.

I have written a predicate that compresses lists by removing repeating items. So if the input is [a,a,a,a,b,c,c,a,a], output should be [a,b,c,a]. My first code worked, but the item order was wrong. So I add a append/3 goal and it stopped working altogether.

Can't figure out why. I tried to trace and debug but don't know what is wrong.

Here is my code which works but gets the item order wrong:

p08([Z], X, [Z|X]).
p08([H1,H2|T], O, X) :-
    H1 \= H2,
    p08([H2|T], [H1|O], X).
p08([H1,H1|T], O, X) :-
    p08([H1|T], O, X).

Here's the newer version, but it does not work at all:

p08([Z], X, [Z|X]).
p08([H1,H2|T], O, X) :-
    H1 \= H2,
    append(H1, O, N),
    p08([H2|T], N, X).
p08([H1,H1|T], O, X) :-
    p08([H1|T], O, X).

Answer 1

H1 is not a list, that's why append(H1, O, N) fails. And if you change H1 to [H1] you actually get a solution identical to your first one. In order to really reverse the list in the accumulator you should change the order of the first two arguments: append(O, [H1], N). Also, you should change the first rule with one that matches the empty list p08([], X, X) (without it, the goal p08([], [], Out) fails).

Now, to solve your problem, here is the simplest solution (which is already tail recursive, as @false stated in the comments to this answer, so there is no need for an accumulator)

p([], []).                    % Rule for empty list
p([Head, Head|Rest], Out):-   % Ignore the Head if it unifies with the 2nd element
    !,                        
    p([Head|Rest], Out).
p([Head|Tail], [Head|Out]):-  % otherwise, Head must be part of the second list
    p(Tail, Out).

and if you want one similar to yours (using an accumulator):

p08(List, Out):-p08(List, [], Out).

p08([], Acc, Acc).
p08([Head, Head|Rest], Acc, Out):-
    !,
    p08([Head|Rest], Acc, Out).
p08([Head|Tail], Acc, Out):-
    append(Acc, [Head], Acc2),
    p08(Tail, Acc2, Out).

Answer 2

Pure and simple:

list_withoutAdjacentDuplicates([],[]).
list_withoutAdjacentDuplicates([X],[X]).
list_withoutAdjacentDuplicates([X,X|Xs],Ys) :-
   list_withoutAdjacentDuplicates([X|Xs],Ys).
list_withoutAdjacentDuplicates([X1,X2|Xs],[X1|Ys]) :-
   dif(X1,X2),
   list_withoutAdjacentDuplicates([X2|Xs],Ys).

Sample query:

?- list_withoutAdjacentDuplicates([a,a,a,a,b,c,c,a,a],Xs).
Xs = [a,b,c,a] ;         % succeeds, but leaves useless choicepoint(s) behind
false

---

Edit 2015-06-03

The following code is based on if_/3 and reified term equality (=)/3 by @false, which---in combination with first argument indexing---helps us avoid above creation of useless choicepoints.

list_without_adjacent_duplicates([],[]).
list_without_adjacent_duplicates([X|Xs],Ys) :-
   list_prev_wo_adj_dups(Xs,X,Ys).

list_prev_wo_adj_dups([],X,[X]).
list_prev_wo_adj_dups([X1|Xs],X0,Ys1) :-
   if_(X0 = X1, Ys1 = Ys0, Ys1 = [X0|Ys0]),
   list_prev_wo_adj_dups(Xs,X1,Ys0).

Let's see it in action!

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

Answer 3

In this answer we use meta-predicate foldl/4 and Prolog lambdas.

:- use_module(library(apply)).
:- use_module(library(lambda)).

We define the logically pure predicatelist_adj_dif/2 based on if_/3 and (=)/3:

list_adj_dif([],[]).
list_adj_dif([X|Xs],Ys) :-
   foldl(\E^(E0-Es0)^(E-Es)^if_(E=E0,Es0=Es,Es0=[E0|Es]),Xs,X-Ys,E1-[E1]).

Let's run the query given by the OP!

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

How about a more general query? Do we get all solutions we expect?

?- list_adj_dif([A,B,C],Xs).
      A=B ,     B=C , Xs = [C]
;     A=B , dif(B,C), Xs = [B,C]
; dif(A,B),     B=C , Xs = [A,C]
; dif(A,B), dif(B,C), Xs = [A,B,C].

Yes, we do! So... the bottom line is?

Like many times before, the monotone if-then-else construct if_/3 enables us to ...

• ..., preserve logical-purity, ...
• ..., prevent the creation of useless choicepoints (in many cases), ...
• ..., and remain monotone—lest we lose solutions in the name of efficiency.

Answer 4

More easily:

compress([X],[X]).

compress([X,Y|Zs],Ls):-
       X = Y,
       compress([Y|Zs],Ls).

compress([X,Y|Zs],[X|Ls]):-
       X \= Y,
       compress([Y|Zs],Ls).

The code works recursevely and it goes deep to the base case, where the list include only one element, and then it comes up, if the found element is equal to the one on his right , such element is not added to the 'Ls' list (list of no duplicates ), otherwise it is.

Answer 5

compr([X1,X1|L1],[X1|L2]) :-
   compr([X1|L1],[X1|L2]),
   !.
compr([X1|L1],[X1|L2]) :-
   compr(L1,L2).
compr([],[]).