0

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).
false
  • 10,264
  • 13
  • 101
  • 209
Cyassin
  • 1,437
  • 1
  • 15
  • 31
  • 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. – false Jun 08 '14 at 10:10
  • 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. – false Jun 08 '14 at 12:59
  • 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. – Cyassin Jun 09 '14 at 18:22
  • 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. – false Jun 09 '14 at 18:56
  • 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. – Cyassin Jun 11 '14 at 07:58
  • By group I meant those other posters who ask the very same questions and also helped to clarify your question. See http://stackoverflow.com/questions/24106515/consecutive-elements-in-a-list/24106558#comment37186539_24106558 – false Jun 11 '14 at 10:43

4 Answers4

4

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).
Tudor Berariu
  • 4,910
  • 2
  • 18
  • 29
3
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].
false
  • 10,264
  • 13
  • 101
  • 209
2

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.
false
  • 10,264
  • 13
  • 101
  • 209
2

Here is a solution using s. 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.
Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209