Uniting consecutive and equal elements in the array in Prolog

Viewed 53

I'm trying to unite consecutive and equal elements in the array in Prolog such that a list such as

[1,1,1,a,b,b,3,3,3,3]

is transformed into

[1,a,b,3]
3 Answers

clumped/2 will turn them into pairs of the element and how often they repeat. Then remove the values from the pairs for the answer:

?- clumped([1,1,1,a,b,b,3,3,3,3], _Pairs),
   pairs_keys_values(_Pairs, Answer, _).

Answer = [1, a, b, 3]

As DCG:

% For eos
:- use_module(library(dcg/basics)).

list_consecutives(Lst, LstCons) :-
    phrase(consec, Lst, LstCons),
    % First is correct
    !.

consec, [C] --> [C], consec_same(C), consec.
consec --> eos.

% Greedily consume a succession of the same element
consec_same(C) --> [C], consec_same(C).
consec_same(_) --> [].

Result in swi-prolog:

?- time(list_consecutives([1,1,1,a,b,b,3,3,3,3], L)).
% 24 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 790175 Lips)
L = [1,a,b,3].

That's pretty easy.

You just need to decompose the problem a little.

  • First, consider the list as consisting of a sequence of runs, each consisting of 1 or more identical elements. To identify/collapse such a run, pop the head of the list, and discard the prefix of the list until we exhaust the list or find something different.

    % -----------------------------------------------------
    % a run consists of 1 or more identical elements.
    % So... pop the head of the list and discard things
    % from the tail until we encounter something different.
    %------------------------------------------------------
    run([X|Xs],X,R) :- discard(Xs,X,R) .
    
    discard( []     , _ , []     ) .
    discard( [X|Xs] , X , T      ) :- !, discard(Xs,X,T) .
    discard( [X|Xs] , _ , [X|Xs] ) .
    
  • Once you have that, it's just a matter of iteratively applying that until the list is exhausted:

    collapse_runs( []     , []     ) .  % there are no runs in the empty list
    collapse_runs( [X|Xs] , [X|Ys] ) :- % for a non-empty list...
      collapse_run(Xs, X, Xn ) ,        % discard everything but the first element in the run
      collapse_runs(Xn,Ys)              % and recurse down on whatever's left over
      .                                 % easy!
    
    

Put it all together and you get this:

https://swish.swi-prolog.org/p/XsOylobo.pl

collapse_runs( Xs , [Y|Ys] ) :- % for a non-empty list...
  run(Xs,Y,X1) ,                % identify the run, discarding the dupes
  collapse_runs(X1,Ys)          % and recurse down on whatever's left over
  .                             % easy!
collapse_runs( [] , []     ) .  % there are no runs in the empty list

% -----------------------------------------------------
% a run consists of 1 or more identical elements.
% So... pop the head of the list and discard things
% from the tail until we encounter something different.
%------------------------------------------------------
run([X|Xs],X,R) :- discard(Xs,X,R) .
    
discard( []     , _ , []     ) .
discard( [X|Xs] , X , T      ) :- !, discard(Xs,X,T) .
discard( [X|Xs] , _ , [X|Xs] ) .
Related