2

I would like to remove more than one repetition from a previously ordered list in prolog. I would like the output to look like this:

Example 1.

?- remove_dups ([1,1,2,2,3,4,5,5,6], List).
List = [3,4,6]

As you can see, it would remove not a repetition of the same element, but all of it.

I used the following algorithm, I made some modifications but without success. Here is the algorithm I used:

    remove_dups([], []).
    remove_dups([X], [X]).

    remove_dups([X,X|T], [X|R]) :-
        remove_dups([X|T], [X|R]).

    remove_dups([X,Y|T], [X|R]) :-
        X \== Y,
        remove_dups([Y|T], R).

    remove_dups([X,Y|T], [X|R]) :-
        (   X == Y
        ->  remove_dups([Y|T], [X|R])
        ;   remove_dups([Y|T], R)
        ).

However the output I have with this algorithm is this.

?- remove_dups([1,1,2,2,3,4,5,5,6], List).

List = [1,2,3,4,5,6]

But I would like it to be as in example 1, any tips?

false
  • 10,264
  • 13
  • 101
  • 209
Chance
  • 1,497
  • 2
  • 15
  • 25

2 Answers2

3

This is quite similar to Include non-unique elements only, and can be solved quite analoguously.

I am again using if_//3 to retain generality of the relation: Please not that a useful Prolog predicate can typically be used in multiple directions, and so an imperative name like remove_dups/2 is not suitable to express other directions and more general use cases.

Instead, I shall call the relation list_singulars/2, and define it like this:

list_singulars(Ls0, Ls) :-
        phrase(list_singulars(Ls0, []), Ls).

list_singulars([], _) --> [].
list_singulars([L|Ls], Ls0) -->
        if_((memberd_t(L, Ls);memberd_t(L, Ls0)),
            [],
            [L]),
        list_singulars(Ls, [L|Ls0]).

Here is a simple test case:

?- list_singulars([a,a,b], List).
List = [b].

And the example you posted:

?- list_singulars([1,1,2,2,3,4,5,5,6], List).
List = [3, 4, 6].

Moreover, we can also generate answers, using a more general query:

?- list_singulars([a,X], List).
X = a,
List = [] ;
List = [a, X],
dif(X, a).

Note the use of dif/2, which is a true relation. See for more information.

Here is the most general query:

?- list_singulars(Ls0, Ls).
Ls0 = Ls, Ls = [] ;
Ls0 = Ls, Ls = [_6826] ;
Ls0 = [_6826, _6826],
Ls = [] ;
Ls0 = [_6826, _6826, _6826],
Ls = [] ;
Ls0 = [_6826, _6826, _6826, _6826],
Ls = [] .

We can easily obtain fair enumeration by iterative deepening:

?- length(Ls0, _), list_singulars(Ls0, Ls).
Ls0 = Ls, Ls = [] ;
Ls0 = Ls, Ls = [_7798] ;
Ls0 = [_7798, _7798],
Ls = [] ;
Ls0 = Ls, Ls = [_8436, _8442],
dif(_8442, _8436) ;
Ls0 = [_7798, _7798, _7798],
Ls = [] ;
Ls0 = [_8494, _8494, _8506],
Ls = [_8506],
dif(_8506, _8494) .
Community
  • 1
  • 1
mat
  • 40,498
  • 3
  • 51
  • 78
0

When you detect a duplicate, i.e. unify with [X,X|T], remove the remaining Xs from the list:

remove_dups([], []).
remove_dups([X], [X]).
remove_dups([X,Y|T], [X|R]) :-
    X \= Y,
    remove_dups([Y|T], R).
remove_dups([X,X|T], R) :-
    skip(X, T, WithoutX),
    remove_dups(WithoutX, R).

As you can see, you are pretty close: the clauses 1, 2, and 3 of the remove_dups/2 rule came from your code. The only difference is in the last clause, which skips the remaining values of X before recursing down.

The skip/2 predicate can be implemented as follows:

skip(_,[],[]).
skip(X, [X|T], T).
skip(X, [Y|T], [Y|T]) :- X \= Y.

Demo.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523