Pack consecutive duplicates of list elements into sublists

Question

I need some help. I searched through the database and I found one question already asked about this example, but the answers didn't really help me, so I thought to post my own question.

The task is to pack consecutive duplicates of list elements into sublists:

% ?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
% X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]].

Here is what I got:

pack([], []).
pack([X], [[X]]).
pack(Liste, Ergebnis):-
   Liste = [H, T|TS],
   H \= T,
   pack([T|TS], Ergebnis1),
   append([[H]], Ergebnis1, Ergebnis).
pack([H, H|HS], Ergebnis):-
   pack([H|HS], Ergebnis1),
   append([H|HS], Ergebnis1, Ergebnis).

The first case works really well (case where H \= T). The second one doesn't, and I really don't know why. Could someone please help me and explain the problem according my solution?

Thanks

Answer 1

Your forth clause tries to append [H|HS] to the result, which is incorrect, because [H|HS] is the tail of the original list. You can make it a lot simpler -

pack([H, H|HS], [[H|TFR]|TR]):-
    pack([H|HS], [TFR|TR]).

Essentially, it says that when the first two entries are the same in the input, the first entry (i.e. H) needs to be pre-pended to the first entry of the output list produced by recursive invocation of the pack rule.

Note that the third clause can be simplified as well by replacing the Liste parameter which you "crack" right away with the "cracked" version "inlined" into the header of the clause, and doing the same to the output variable Ergebnis1. The final version should look like this:

pack([H, T|TS], [[H]|TR]):-
    H \= T,
    pack([T|TS], TR).

Here is a demo on ideone.

Answer 2

The first two clauses are trivial cases and look good.

The third clause seems reasonable. It says that if I pack [H,T|TS] and H \= T, then the result would be [H] prepended to the result of [T|TS] being packed.

The forth clause is the problem:

pack([H, H|HS], Ergebnis):-
    pack([H|HS], Ergebnis1),
    append([H|HS], Ergebnis1, Ergebnis).

It says that the result of packing [H,H|HS] is the same as packing [H|HS] and then prepending all of [H|HS]. That doesn't seem logical. What's going to happen when you pack [H|HS] is you're going to get something that looks like: [[H,...,H]|X] and now you want to put another H into the head of the first sublist. So you should have:

pack([H, H|HS], Ergebnis):-
    pack([H|HS], [HH|T]),
    Ergebnis = [[H|HH]|T].

You can make these predicates a little more compact:

pack([], []).
pack([X], [[X]]).
pack([H,T|TS], [[H]|PTS]):-
   H \= T,
   pack([T|TS], PTS).
pack([H, H|HS], [[H|HH]|T]):-
   pack([H|HS], [HH|T]).

Testing...

| ?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).

X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]] ? a

no
| ?-

Answer 3

Every of the other implementations given in answers to this question is logically impure. They are not monotone and thus easily become logically unsound when used with non-ground terms.

The implementation suggested here is logically pure. It uses the meta-predicate splitlistIfAdj/3, which is based on if_/3, as proposed by @false in an answer on reification.

So let's use splitlistIfAdj/3 in tandem with dif/3 which is a reified variant of dif/2:

?- splitlistIfAdj(dif,[a,a,a,a,b,c,c,a,a,d,e,e,e,e],Lists).
Lists = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]]. % succeeds deterministically

As we stay monotone here, we get meaningful answers even if we use non-ground terms:

?- splitlistIfAdj(dif,[A,B,C],Lists).
A = B,    B = C,    Lists = [[C, C, C]]    ;
A = B,    dif(B,C), Lists = [[B, B], [C]]  ;
dif(A,C), B = C,    Lists = [[A], [C, C]]  ;
dif(A,B), dif(B,C), Lists = [[A], [B], [C]].

Answer 4

I would approach the problem a little differently and decompose the problem into two simpler tasks.

We first need to be able to partition the list into a prefix consisting of the list of consecutive elements at the head of the list and its suffix (everything else):

partition( []      , []    , []     ) .
partition( [X]     , [X]   , []     ) .
partition( [X,Y|Z] , [X]   , [Y|Z]  ) :- X \= Y .
partition( [X,Y|Z] , [X|P] , S      ) :- X  = Y , partition([Y|Z],P,S) .

Once we have that, the rest is easy:

pack([],[]) .               % packing an empty list yields the empty list
pack([X|Xs],[P,Ps]) :-      % packing a non-empty list consists of
  partition([X|Xs],P,T) ,   % - partitioning it into its prefix and suffix, and
  pack(T,Ps)                % - packing the suffix
  .                         %

Answer 5

To avoid append, you can use dcg:

pack(L, LP) :-                  % pack/2
    phrase(pack(L), LP).

pack([]) --> [].                % pack//1
pack([X]) --> [[X]].
pack([H, H1 | T]) -->
     {H \= H1},
     [[H]],
     pack([H1 | T]).
pack([H, H | T]) -->
    pack([H | T], [H]).

pack([H, H | T], P) -->         % pack//2
    pack([H | T], [H|P]).
pack([H, H1 | T], P) -->
    {H \= H1},
    [[H | P]],
    pack([H1 | T]).
pack([H, H], P) -->
    [[H,H|P]].