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]
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]
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] ) .