Assignment that implements a list in compact form

Question

I have a question in a course assignment.

Consider repetitive lists of the form [a,a,a,b,b,c,a,a,a,a] and their compact form, defined as lists of couples, [[a,3],[b,2],[c,1],[a,4]].

Define the predicate compress/2 such that compress(+L1, ?L2) is satisfied if, given a list L1, L2 is its compact form.

So far, I have come up with the code below:

compress(X,[[X,1]]).
compress([H1,H2|T1],[[H1,C]|T2]):-
   H1 = H2,
   compress(T1,T2),
   C is R + 1.

I am not sure if I am doing it right. Could someone please point to the right direction.

Answer 1

Here are some ideas to get you started.

You're going to need to keep a running count of repeated elements since your results have counters. So right off, consider an auxiliary predicate that includes the counter, which is a typical way of handling it in Prolog. This use of a counter is commonly referred to as an accumulator.

compress(L, C) :-
    compress(L, 1, C).   % Start counter at 1

Now you'll need to consider a few different cases:

compress([], _, []).                 % This is an easy one!

This says that if I compress an empty list, I get an empty list.

compress([H], Count, [[H,Count]]).   % This is an easy one!

This one says if I compress a list of one element and my current running count is Count, then the result is [[H, Count]].

compress([H, H|T], Count, TC) :-
    ...

This is the case where I have a running count and the element is still repeating. The result is going to be a list TC but I don't know what it looks like yet since we're still in a repeating cycle and it will need to be determined through recursion. What should this predicate look like? In your example, you included a count in the result when the first two elements were the same, which is not the right time to include the count (see the clause below).

compress([H1, H2|T], Count, [[H1,Count]|TC]) :-
    dif(H1, H2),
    ...

This is the case where I have a running count and the repeating stops at H1. Since the repeating of the current cycle ends with H1, we know the result looks like [[H1, Count]|TC] because H1 has repeated Count times. We just have yet to determine the rest of the list TC through recursion. What should this predicate implementation look like?

There are other ways of doing the above logic (e.g., with -> and ; construct, etc), but this will keep it simple.

Try to think of these as rules where the head of the predicate clause is the assertion which will be true if the following elements of the clause are true. And think recursively.

---

As an afterthought, this could be done without a separate accumulator by using the result to carry the accumulator:

compress([], []).
compress([H], [[H,1]]).
compress([H1,H2|T], [[H1,1]|R]) :-
    dif(H1, H2),
    compress(...).                 % left as an exercise
compress([H,H|T], [[H,N]|R]) :-
    N #= N1 + 1,
    compress(...).                 % left as an exercise

Answer 2

I chose to do it this way:

?- compress([a,a,a,b,b,c,a,a,a,a],L), write(L), nl, fail.

compress(X,R) :-
    enumerate(X,Y),
    collapse(Y,R).

enumerate([],[]).
enumerate([H|T],[[H,1]|R]) :- enumerate(T,R).

collapse([],[]).
collapse([X],[X]).
collapse([[X,N1],[X,N2]|T],R) :- N is N1 + N2, collapse([[X,N]|T],R).
collapse([[X,N1],[Y,N2]|T],[[X,N1]|R]) :- X \= Y, collapse([[Y,N2]|T],R).

The enumerate predicate simply maps [a, a, a, b, b, c, a, a, a, a] to [[a, 1], [a, 1], [a, 1], [b, 1], [b, 1], [c, 1], [a, 1], [a, 1], [a, 1], [a, 1]].

Then I collapse this list down by matching the first two heads of the list - if they unify add the values and try to collapse again. If they don't unify then pop one element off of the list and collapse again. Otherwise there are two base cases - an empty list and a list with one element.

The result is: [[a, 3], [b, 2], [c, 1], [a, 4]].

Answer 3

Here's how you could do it using splitlistIfAdj/3 in combination with dif/3.

First, determine the runs of equal adjacent list items:

?- splitlistIfAdj(dif, [a,a,a,b,b,c,a,a,a,a], Xss).
Xss = [[a,a,a],[b,b],[c],[a,a,a,a]].

Then, map each run to its length using maplist/3 and length/2:

?- maplist(length, [[a,a,a],[b,b],[c],[a,a,a,a]], Ls).
Ls = [3,2,1,4].

Almost done! Let's put it all together using Prolog lambdas:

:- use_module(library(lambda)).

list_compressed(Xs, Yss) :-
   splitlistIfAdj(dif, Xs, Xss),
   maplist(\Es^(E-N)^(Es=[E|_],length(Es,N)), Xss, Yss).

Sample query:

?- list_compressed([a,a,a,b,b,c,a,a,a,a], Xss).
Xss = [a-3,b-2,c-1,a-4].