Removing Contiguous sequence from two list in prolog

Question

I am new to prolog and came across this practice exercise that I need help with.

The question is asking to define a predicate removeContig(A,B) that asserts the list B is the same as list A except that instances of contiguous sequence of identical items are reduced to one instance.

Example:

removeContig ([a,a,b,b,b,c,c,c], [a,b,c]) -> true.
removeContig ([a,a,b,b,b,c,c,c], [a,b,c]) -> true.
removeContig ([a,a,b,b,b,c,c,c], [a,b,b,c]) -> false.
removeContig ([a,b,c,a,b,c], [a,b,c]) -> false. 
removeContig ([a,b,c,a,b,c], [a,b,c,a,b,c]) -> true.
removeContig([[a],[b,b],[b,b],[a,a],[a,a],[b]], [[a],[b,b],[a,a],[b]]) ->   true.

Any help on how I can approach this problem will be greatly helpful.

Answer 1

This is the exact same functionality as the command line tool uniq; in SWI-Prolog at least, it is available with group_pairs_by_key/2. It does more than you need, but it could be used like this:

uniq(L, U) :-
        pairs_keys_values(Ps, L, L),
        group_pairs_by_key(Ps, G),
        pairs_keys(G, U).

You could of course look at the implementation, use it as a starting point, and write your own (should be fairly straight-forward, you only need to remove a few things).

This only works if your first argument (the list with the repeats) is ground!

Answer 2

What about

removeContig([], []).

removeContig([A], [A]).

removeContig([Hi , Hi | Ti], Lo) :-
  removeContig([Hi | Ti], Lo).

removeContig([H1 , H2 | Ti], [H1 | To]) :-
  H1 \= H2,
  removeContig([H2 | Ti], To).

?

The trick is copy the head of the input list, as head of the output list, only if the following element is different.

Observe that it's neccessary the empty-list clause (removeContig([], []).) for the case the input list is empty.

--- Edit ---

As asked by OP, I try to improve the answer.

I have written four clauses for removeContig; the first two are terminal cases and I hope there isn't need of explanation.

removeContig([], []).

removeContig([A], [A]).

I point only the attention on the fact that the first one is needed only for the case you call removeContig with the input list empty.

Next... what we have to do?

The algorithm consist in copying the first element of the input list as first element of output list only and only if the second element of the input list is different.

So, excluded the terminal case (only one element in input list, so copy it in output list), we have two cases:

1) the first and the second element of the input list are equal, so delete (do not copy it) the first one

2) the first and the second element of the input list are different, so copy the fist one as first of the output list

The case (1) is managed by the following clause

removeContig([Hi , Hi | Ti], Lo) :-
  removeContig([Hi | Ti], Lo).

where [Hi, Hi | Ti] say that the first two element are equals; in this case is called removeContig with the same argument except the first element in the input list that is, in this way, ignored.

The case (2) is managed by the following clause

removeContig([H1 , H2 | Ti], [H1 | To]) :-
  H1 \= H2,
  removeContig([H2 | Ti], To).

where [H1, H2 | Ti] and H1 \= H2 ensure us that the first two elements in the input list are different; in this case, we have to copy the first element in the input list (H1) as first element of the output list; and this is obtained with [H1 | To] where To is obtained from the following call to removeContig/2.