Prolog separating into two lists issue

Question

I have a prolog assignment.

I need to look at the first item in a list, see if its following items are the same until they are not and separate the lists by the first item and its duplicates. e.g if my list was a,a,a,b,c it would separate it into first: a,a,a. second: b,c.

My current solution works except that the final matching item comes into the second list, not the first. I can't seem to think of a way to get it to appear in the first list instead.

grab([],[],[]).
grab([A,A|L],[A|L2],Rest) :- grab([A|L],L2,Rest).
grab([A|L],Init,[A|L2]) :- grab(L,Init,L2).

Ragamuffin

Your problem statement is ill-defined. On the one hand you imply that grab([],Xs,Ys) should be true, on the other hand you state that you "need to look at the first item in a list" which implies that grab/3 will only succeed with a list containing at least one element. – Earhart

Yesterday, you asked a similar question - got an answer - and immediately deleted your question. Please note that in this manner you risk being banned from asking questions. – Earhart

The other question i asked had its answer removed, then had no answers and then i realised my question didnt even make sense, so re lodged it with changes from what i had worked out. – Ragamuffin

I answered it and I never remove my answers. But it seems your group has deleted many more questions answered by others. That's really not nice. – Earhart

I don't know what happened, but when i first looked there was a answer, when i reloaded there wasnt an answer. The question I asked made no sense anyway, the answer you gave me was just a direct answer to the solution, which I was not after. I don't know what you mean about my group? I don't delete questions, or answers i post? I have a healthy reputation I have slowly been building, built from questions and answers if you look at my profile. – Ragamuffin

By group I meant those other posters who ask the very same questions and also helped to clarify your question. See #24107015 – Earhart

Answer 1

When the first two elements are different you do not need a recursive goal.

grab([], [], []).
grab([A,A|Rest], [A|As], L2):- !, grab([A|Rest], As, L2).
grab([A|Tail], [A], Tail).

Laminated

@Nick: grab([a],Ys, Zs). succeeds with Ys = [a], Zs = []. – Earhart

Answer 2

grab(Xs, Ys, Zs) :-
   eqprefix(Xs, Ys, Zs).

eqprefix([],[],[]).
eqprefix([X],[],[X]).
eqprefix([X,Y|Xs], [], [X,Y|Xs]) :-
    dif(X,Y).
eqprefix([X,X|Xs], [X|Ys], Zs) :-
   eqprefix2([X|Xs], Ys, Zs).

eqprefix2([X], [X], []).
eqprefix2([X,Y|Xs], [X], [Y|Xs]) :-
    dif(X,Y).
eqprefix2([X,X|Xs], [X|Ys], Zs) :-
    eqprefix2([X|Xs], Ys, Zs).

?- eqprefix([a,a,a,b,c],Ys,Zs).
   Ys = [a, a, a], Zs = [b, c]
;  false.
?- eqprefix(Xs,[a,a,a],[b,c]).
   Xs = [a, a, a, b, c]
;  false.
?- eqprefix([A,B,C,D,E],[a|Ys],[b,c]).
   A = B, B = C, C = a, D = b, E = c,
   Ys = [a, a]
;  false.

In the definition you gave, you get many different answers:

?- grab([a,a,a,b,c],Ys,Zs).
   Ys = [a, a], Zs = [a,b,c]
;  Ys = [a],    Zs = [a,a,b,c]
;  Ys = [a],    Zs = [a,a,b,c]
;  Ys = [],     Zs = [a,a,a,b,c].

Earhart

Answer 3

Here is another solution that takes into account what @Sarah wrote. Given this use, grab/3 should never succeed for an empty list for the first or second argument.

grab([A], [A], []).
grab([A,B|Bs], [A], [B|Bs]) :-
   dif(A,B).
grab([A,A|Xs], [A|As], Bs) :-
   grab([A|Xs], As, Bs).

?- Xs = [A,B], grab(Xs,Ys,Zs).
   Xs = [A,B], Ys = [A],    Zs = [B], dif(A,B)
;  Xs = Ys,    Ys = [B,B], Zs = [],  A = B
;  false.

Earhart

Answer 4

Here is a solution using dcgs. Most interesting is here the usage of a non-terminal that is not context-free. I will start with an attempt that is too general:

grab_tentative(Xs, Ys, Zs) :-
   phrase((seq(Ys),seq(Zs)), Xs).

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

grab_tentative/3 ensures that Xs consists of Ys concatenated with Zs. That is way too general, but all intended solutions are already included.

?- Xs = [A,B,C], grab_tentative(Xs,Ys,Zs).
   Xs = Zs, Zs = [A, B, C], Ys = []
;  Xs = [A, B, C], Ys = [A], Zs = [B, C]
;  Xs = [A, B, C], Ys = [A, B], Zs = [C]
;  Xs = Ys, Ys = [A, B, C], Zs = []
;  false.

The first answer says that Ys = [], but (as has been clarified by @Sarah), Ys should always be a non-empty list, so we can restrict the answers to non-empty lists:

grab_tentative(Xs, Ys, Zs) :-
   Ys = [_|_],
   phrase((seq(Ys),seq(Zs)), Xs).

The answers Xs = [A, B, C], Ys = [A, B], Zs = [C] and Xs = Ys, Ys = [A, B, C], Zs = [] both permit that A and B are different. So we have to add that they are the same:

grab_tentative(Xs, Ys, Zs) :-
   Ys = [A|_],
   phrase((all_seq(=(A),Ys),seq(Zs)), Xs).

all_seq(_, []) --> [].
all_seq(C_1, [C|Cs]) -->
   [C],
   {call(C_1,C)},
   all_seq(C_1, Cs).

Now, the answers are already a bit better:

?- Xs = [A,B,C], grab_tentative(Xs,Ys,Zs).
   Xs = [A, B, C], Ys = [A], Zs = [B, C]
;  Xs = [B, B, C], A = B, Ys = [B, B], Zs = [C]
;  Xs = Ys, Ys = [C, C, C], A = B, B = C, Zs = []
;  false.

The first answer includes that A = B. So, it really should contain dif(A,B). To do so we need to introduce such a context. Here is way to do this. Note that or_end//1 is like []//0, except that it ensures some extra condition.

grab_final(Xs, Ys, Zs) :-
   Ys = [A|_],
   phrase((all_seq(=(A),Ys), or_end(dif(A)), seq(Zs)), Xs).

or_end(C_1) -->
  call(cond_or_end(C_1)). % interface to predicates

cond_or_end(_C_1, [], []).
cond_or_end(C_1, [E|Es], [E|Es]) :-

Now, the answers are as expected:

?- Xs = [A,B,C], grab_final(Xs, Ys, Zs).
   Xs = [A, B, C], Ys = [A], Zs = [B, C], dif(A, B)
;  Xs = [B, B, C], A = B, Ys = [B, B], Zs = [C], dif(B, C)
;  Xs = Ys, Ys = [C, C, C], A = B, B = C, Zs = []
;  false.

Earhart