CODEWITHSUNDEEP
listprologprolog-dif
Krishna Kalyan
Krishna Kalyan

Reputation: 1702

Splitting list in prolog based on condition

I have a list

[a,a,a,a,b,b]

My objective is to split it into

[[a,a,a,a],[b,b]]

the predicate i have implemented so far

split1([],[]).
split1([A1|T],[[H1,H2]|B]):-
A1=[H1,H2],
H1=H2,
split(T,B).

split1([],[]).
split1([A1|T],[[H1,H2]|B]):-
A1=[H1,H2],
H1\=H2,
split(T,B).

Sorry for the noob question learning prolog.

Upvotes: 0

Views: 758

Answers (4)

lurker
lurker

Reputation: 58284

This can be approached very similarly to your other problem. Here are the related ideas.

You're going to need to keep a running list of repeated elements since your results have counters. So consider an auxiliary predicate that includes the current running list of repeats. This kind of "running list" is commonly used in Prolog and referred to as an accumulator.

split(L, C) :-
    split(L, [], C).   % Start repeat list accumulator at []

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

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

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

split([H], A, [[H|A]]).           % This is an easy one!

This one says if I gather a list of one element and my current running repeat list is A, then the result is [[H|A]].

split([H, H|T], A, TC) :-
    ...

This is the case where I have a running repeat list, A, 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? The recursive call to split1 which will be needed in this clause will have a new accumulator list. What does it look like?.

split([H1, H2|T], A, [[H1|A]|TC]) :-
    dif(H1, H2),
    ...

This is the case where I have a running repeat list, A, and the repeating stops at H1. Since the repeating of the current cycle ends with H1, we know the result looks like [[H1|A]|TC] because the repeat cycle has finished with H1, and the entire repeating list is H1 with tail A (which just prepends H1 to A, and they're all the same element). 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:

split([], []).
split([H], [[H]]).
split([H1,H2|T], [[H1]|R]) :-
    dif(H1, H2),
    split(...).                 % left as an exercise
split([H,H|T], [[H|TH]|R]) :-
    split(...).                 % left as an exercise

Upvotes: 3

CapelliC
CapelliC

Reputation: 60034

an easy definition:

groups([X|Xs],[G|Gs]) :- take(X,Xs,G,Rs), groups(Rs, Gs).
groups([],[]).

take(X,[X|R],[X|G],S) :- !, take(X,R,G,S).
take(X,R,[X],R).

take/4 consumes and stores matching elements, leaving the remainder to group

Upvotes: 1

user1812457
user1812457

Reputation:

You should take a look at the SWI-Prolog implementation of group_pairs_by_key/2. It does a bit more than what you need, but I guess it is easy to leave out the unnecessary parts.

With the predicate as it is at the moment, you can do:

?- L = [a,a,b,b,a,b,b],
   keys_values_pairs(L, L, P),
   group_pairs_by_key(P, G),
   keys_values_pairs(_, Result, G).
L = [a, a, b, b, a, b, b],
P = [a-a, a-a, b-b, b-b, a-a, b-b, b-b],
G = [a-[a, a], b-[b, b], a-[a], b-[b, b]],
Result = [[a, a], [b, b], [a], [b, b]].

So you just need to figure out what to leave out to get a predicate that does not need a pair of a key and a value, but only a single value. Since this is obviously homework and since you didn't even put enough effort in the answer, I will leave this as an exercise.

Upvotes: 1

repeat
repeat

Reputation: 18726

All you need is splitlistIfAdj/3 and dif/3. Sample use:

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

Upvotes: 2

Related Questions