Example: No consecutive duplicates

[triska]

Dear all,

today I came across a discussion where the task, declaratively speaking, is to describe the relation between a list and a version of the list without consecutive duplicates.

For instance:

:- use_module(library(reif)).

no_consecutive_duplicates([], []).
no_consecutive_duplicates([L|Ls], Rs) :-
        no_consecutive_duplicates_(Ls, L, Rs).

no_consecutive_duplicates_([], L, [L]).
no_consecutive_duplicates_([L|Ls], L0, Rs0) :-
        if_(L=L0, Rs0=Rs, Rs0=[L0|Rs]),
        no_consecutive_duplicates_(Ls, L, Rs).

Examples:

• most general query:

?- no_consecutive_duplicates(Ls, Rs).
   Ls = [], Rs = []
;  Ls = [_A], Rs = [_A]
;  Ls = [_A,_A], Rs = [_A]
;  Ls = [_A,_A,_A], Rs = [_A]
;  ... .

Note how it wouldn't capture the generality of the relation to say that the code "eliminates" duplicated list elements, because no lists are given at all in such cases, and no single element is known. Yet we can use the relation also in such cases, and it yields correct answers.

• fair enumeration, using iterative deepening:

?- length(Ls, _), no_consecutive_duplicates(Ls, Rs).
   Ls = [], Rs = []
;  Ls = [_A], Rs = [_A]
;  Ls = [_A,_A], Rs = [_A]
;  Ls = [_B,_A], Rs = [_B,_A], dif:dif(_A,_B)
;  Ls = [_A,_A,_A], Rs = [_A]
;  Ls = [_B,_B,_A], Rs = [_B,_A], dif:dif(_A,_B)
;  ... .

Notice an unexpected variable order in a few leaf answers, such as:

;  Ls = [_B,_A], Rs = [_B,_A], dif:dif(_A,_B)

where Scryer would better yield:

;  Ls = [_A,_B], Rs = [_A,_B], dif:dif(_A,_B)

• concrete fully known list:

?- no_consecutive_duplicates("aaaabcccdddd", Rs).
   Rs = "abcd".

A general, efficient and straight-forward to define relation that works in all usage modes and execution strategies.

All the best,
Markus

[triska]

The unexpected variable order is already filed as an issue: #1578.