Re: Help with lists.

Bart Demoen wrote:

My apologies for this impure program: I had no time to make it more
pure :-)


Here is a purer one nevertheless - with the right complexity I think.



remove_triplets(I,O) :-
        pair(I,I1,1),
        sort(I1,I1s),
        collect(I1s,[],Leave1),
        sort(Leave1,Leave),
        skim(Leave,I1,O).

skim([],_,[]).
skim([P|RP],[X-PX|RX],Out) :-
        (P == PX ->
            Out = [X|S],
            skim(RP,RX,S)
        ;
            skim([P|RP],RX,Out)
        ).

collect([],[]).
collect([X-PX|R],O) :-
        eat(R,X,R1,1,N),
        (N =\= 2 ->
            O = [PX|O1],
            collect(R1,O1)
        ;
            R = [_-P2|_],
            O = [PX,P2|O1],
            collect(R1,O1)
        ).

eat([],_,[],N,N).
eat([A|R],X,O,I,N) :-
        A = (AX-_),
        (AX == X ->
            I1 is I + 1,
            eat(R,X,O,I1,N)
        ;
            O = [A|R],
            N = I
        ).

pair([],[],_).
pair([X|R],[X-I|S],I) :-
        I1 is I + 1,
        pair(R,S,I1).


Cheers

Bart Demoen
.