Prolog: removing all consecutive integer sublists

Question

So I ran into this Prolog problem:

Given a linear numerical list remove all sequences of consecutive values.

E.g. remove([1, 2, 4, 6, 7, 8, 10], L) will produce L=[4, 10].

I managed to write this code:

consecutive(N,P):-
    N is P-1.

removeS([],[]).
removeS([H],[H]).

removeS([H1,H2],[]):-
    consecutive(H1,H2).
removeS([H1,H2|T],[H1|L]):-
    not(consecutive(H1,H2)),
    removeS([H2|T],L).
removeS([H1,H2,H3|T],L):-
    consecutive(H1,H2),
    not(consecutive(H2,H3)),
    removeS([H3|T],L).
removeS([H1,H2,H3|T],L):-
    consecutive(H1,H2),
    consecutive(H2,H3),
    removeS([H3|T],L).

It almost works on some cases like:

removeS([1,2,3,4,5,2,3,4,5,6,7,9,11],R). -->  R = [5, 9, 11];
Here only 9 and 11 should be displayed

removeS([3,2,1,2,3,4,5,2,3,4,5,6,7,9,11],R). --> R = [3, 2, 5, 9, 11];
Here only 3,2,9,11 should appear in R

It's that it takes the last number of an increasing sequence into consideration when it computes the next step.

What I am doing wrong here?

This is a very good attempt! The reason it doesn't give the answer you want is the last line of the last clause. If `consecutive(H2,H3)` succeeds, then you don't want `removeS([H3|T], L)` since you don't want to count `H3`. You just want `removeS(T, L).` — lurker, Nov 18 '15 at 19:00
@lurker: after applying your 'correction', I get (as expected) `?- removeS([1,2,3,4],L). L = [4]`. Do you have different results ? I insist that what is missing is generalization... — CapelliC, Nov 18 '15 at 23:15
@CapelliC I didn't test that case. The "correction" I gave is necessary, but not sufficient. The predicate obviously needs more to make it right. I didn't claim it was a complete solution. It was just something I spotted. I think your answer is an improvement in the direction of refactoring. I was looking for just a patch (answering the question, partially, of "What's wrong with what I have?"). :) — lurker, Nov 18 '15 at 23:17
@lurker: the approach is *logically* flawed: dropping N consecutive elements removes the 'lookahead' required to check following elements! I avoided to post the full code (5 lines !) in hope that Eugen (I agree his is a good attempt) could be interested in discovery the appropriate solution — CapelliC, Nov 18 '15 at 23:45

score 1 · Answer 1 · edited May 23 '17 at 12:15

In this answer we use Prolog lambdas in combination with two meta-predicates.

:- use_module(library(lambda)).

Based on append/2, split_if_adj/3, tfilter/3, (=)/3, and z_nonsucc_t/3 we define:

consecutives_removed(Xss, Zs) :-
   split_if_adj(z_nonsucc_t, Xss, Yss),
   tfilter(\[_|Xs]^(Xs=[]), Yss, Zss),
   append(Zss, Zs).

Sample queries (as given by the OP):

?- consecutives_removed([1,2,4,6,7,8,10], Xs).
Xs = [4,10].

?- consecutives_removed([1,2,3,4,5,2,3,4,5,6,7,9,11], Xs).
Xs = [9,11].

?- consecutives_removed([3,2,1,2,3,4,5,2,3,4,5,6,7,9,11], Xs).
Xs = [3,2,9,11].

CapelliC · Answer 2 · 2015-11-19T12:30:36.800

you are doing less general (and of consequence, more complex) than needed.

?- removeS([1,2,3],R).
R = [3] ;
false.

I have introduced a service predicate, that 'eats' all consecutives, and simplified the logic to start it only when two consecutives appear, and I have:

?- removeS([3,2,1,2,3,4,5,2,3,4,5,6,7,9,11],L).
L = [3, 2, 9, 11].

edit

Here is my definition. The cut can be removed, negating the alternative as you have done, but IMHO this only clutter the whole. Or, simply, drop it and wrap removeS/2 top call with once/1.

removeS([],[]).
removeS([A,B|T],L):- succ(A,B), eat(A,[B|T],R), !, removeS(R, L).
removeS([A|B],[A|L]) :- removeS(B,L).

eat(A,[B|T],R) :- succ(A,B), eat(B,T,R).
eat(_,T,T).

Although the OP's original approach isn't *totally* logically flawed (I came up with a similar, working solution), your solution is much cleaner and more compact (+1). — lurker, Nov 20 '15 at 13:49

Prolog: removing all consecutive integer sublists

2 Answers2