Split a list in separate lists

Question

I have to define some more constraints for my list.

I want to split my list is separate lists.

Example:

List=[[1,1],[_,0],[_,0],[_,0],[3,1],[_,0],[9,1],[2,0],[4,0]]

I need three Lists which i get from the main list:

[[_,0],[_,0],[_,0]] and [[_,0]] and [[2,0],[4,0]]

SO I always need a group of lists between a term with [X,1].

It would be great if u could give me a tip. Don’t want the solution, only a tip how to solve this.

Jörg

score 3 · Answer 1 · edited May 23 '17 at 12:01

It is not clear what you mean by a "group of lists". In your example you start with [1,1] which fits your criterion of [_,1]. So shouldn't there be an empty list in the beginning? Or maybe you meant that it all starts with such a marker? And what if there are further markers around?

First you need to define the criterion for a marker element. This for both cases: When it applies and when it does not apply and thus this is an element in between.

marker([_,1]).

nonmarker([_,C]) :-
   dif(1, C).

Note that with these predicates we imply that every element has to be [_,_]. You did not state it, but it does make sense.

split(Xs, As, Bs, Cs) :-
   phrase(three_seqs(As, Bs, Cs), Xs).

marker -->
   [E],
   {marker(E)}.

three_seqs(As, Bs, Cs) -->
   marker,
   all_seq(nonmarker, As),
   marker,
   all_seq(nonmarker, Bs),
   marker,
   all_seq(nonmarker, Cs).

For a definition of all_seq//2 see this

In place of marker, one could write all_seq(marker,[_])

thank u very much fo the answer... yaer it start with such a marker and ends at such a marker.. and the predicate IS [_,_]. I will try to understand your answer. thank you very much — Hans, Feb 08 '15 at 21:12

score 3 · Accepted Answer · edited May 23 '17 at 12:13

This implementation tries to preserve logical-purity without restricting the list items to be [_,_], like @false's answer does. I can see that imposing above restriction does make a lot of sense... still I would like to lift it---and attack the more general problem.

The following is based on if_/3, splitlistIf/3 and reified predicate, marker_truth/2. marker_truth(M,T) reifies the "marker"-ness of M into the truth value T (true or false).

is_marker([_,1]).                      % non-reified

marker_truth([_,1],true).              % reified: variant #1
marker_truth(Xs,false) :-
   dif(Xs,[_,1]).

Easy enough! Let's try splitlistIf/3 and marker_truth/2 together in a query:

?- Ls=[[1,1],[_,0],[_,0],[_,0],[3,1],[_,0],[9,1],[2,0],[4,0]], 
   splitlistIf(marker_truth,Ls,Pss).
Ls  = [[1,1],[_A,0],[_B,0],[_C,0],[3,1],[_D,0],[9,1],[2,0],[4,0]],
Pss = [     [[_A,0],[_B,0],[_C,0]],    [[_D,0]],    [[2,0],[4,0]]] ? ; % OK
Ls  = [[1,1],[_A,0],[_B,0],[_C,0],[3,1],[_D,0],[9,1],[2,0],[4,0]],
Pss = [     [[_A,0],[_B,0],[_C,0]],    [[_D,0],[9,1],[2,0],[4,0]]],
prolog:dif([9,1],[_E,1])                                           ? ; % BAD
%% query aborted (6 other BAD answers omitted)

D'oh!

The second answer shown above is certainly not what we wanted. Clearly, splitlistIf/3 should have split Ls at that point, as the goal is_marker([9,1]) succeeds. It didn't. Instead, we got an answer with a frozen dif/2 goal that will never be woken up, because it is waiting for the instantiation of the anonymous variable _E.

Guess who's to blame! The second clause of marker_truth/2:

marker_truth(Xs,false) :- dif(Xs,[_,1]).       % BAD

What can we do about it? Use our own inequality predicate that doesn't freeze on a variable which will never be instantiated:

marker_truth(Xs,Truth) :-                      % variant #2
   freeze(Xs, marker_truth__1(Xs,Truth)).

marker_truth__1(Xs,Truth) :-
   (  Xs = [_|Xs0]
   -> freeze(Xs0, marker_truth__2(Xs0,Truth))
   ;  Truth = false
   ).

marker_truth__2(Xs,Truth) :-
   (  Xs = [X|Xs0]
   -> when((nonvar(X);nonvar(Xs0)), marker_truth__3(X,Xs0,Truth))
   ;  Truth = false
   ).

marker_truth__3(X,Xs0,Truth) :- % X or Xs0 have become nonvar
   (  nonvar(X)
   -> (  X == 1 
      -> freeze(Xs0,(Xs0 == [] -> Truth = true ; Truth = false))
      ;  Truth = false
      )
   ;  Xs0 == []
   -> freeze(X,(X == 1 -> Truth = true ; Truth = false))
   ;  Truth = false
   ).

All this code, for expressing the safe logical negation of is_marker([_,1])? UGLY!

Let's see if it (at least) helped above query (the one which gave so many useless answers)!

?- Ls=[[1,1],[_,0],[_,0],[_,0],[3,1],[_,0],[9,1],[2,0],[4,0]],
   splitlistIf(marker_truth,Ls,Pss).
Ls  = [[1,1],[_A,0],[_B,0],[_C,0],[3,1],[_D,0],[9,1],[2,0],[4,0]],
Pss = [[     [_A,0],[_B,0],[_C,0]],    [[_D,0]],    [[2,0],[4,0]]] ? ;
no

It works! When considering the coding effort required, however, it is clear that either a code generation scheme or a variant of dif/2 (which shows above behaviour) will have to be devised.

Edit 2015-05-25

Above implementation marker_truth/2 somewhat works, but leaves a lot to be desired. Consider:

?- marker_truth(M,Truth).                   % most general use
freeze(M, marker_truth__1(M, Truth)).

This answer is not what we would like to get. To see why not, let's look at the answers of a comparable use of integer_truth/2:

?- integer_truth(I,Truth).                  % most general use
Truth = true,  freeze(I, integer(I)) ;
Truth = false, freeze(I, \+integer(I)).

Two answers in the most general case---that's how a reified predicate should behave like!

Let's recode marker_truth/2 accordingly:

marker_truth(Xs,Truth) :- subsumes_term([_,1],Xs), !, Truth = true.
marker_truth(Xs,Truth) :- Xs \= [_,1],             !, Truth = false.
marker_truth([_,1],true).
marker_truth(Xs   ,false) :- nonMarker__1(Xs).

nonMarker__1(T) :- var(T),      !, freeze(T,nonMarker__1(T)).
nonMarker__1(T) :- T = [_|Arg], !, nonMarker__2(Arg).
nonMarker__1(_).

nonMarker__2(T) :- var(T),    !, freeze(T,nonMarker__2(T)).
nonMarker__2(T) :- T = [_|_], !, dif(T,[1]).
nonMarker__2(_).

Let's re-run above query with the new implementation of marker_truth/2:

?- marker_truth(M,Truth).                   % most general use
Truth = true,  M = [_A,1] ;
Truth = false, freeze(M, nonMarker__1(M)).

Instead of showing a wall of answer substitutions, why not make queries that detect the incorrect answer substitutions? This would reduce the need for highlighting. — false, May 20 '15 at 12:25
After "OMG": Why don't you give concrete queries, why you are unhappy with the first version? I don't think that it is easy to follow you without. — false, May 20 '15 at 12:26

score 1 · Answer 3 · 2015-02-10T05:14:22.247

1

You can use a predicate like append/3. For example, to split a list on the first occurence of the atom x in it, you would say:

?- L =  [a,b,c,d,x,e,f,g,x,h,i,j], once(append(Before, [x|After], L)).
L = [a, b, c, d, x, e, f, g, x|...],
Before = [a, b, c, d],
After = [e, f, g, x, h, i, j].

As @false has pointed out, putting an extra requirement might change your result, but this is what is nice about using append/3:

"Split the list on x so that the second part starts with h:

?- L =  [a,b,c,d,x,e,f,g,x,h,i,j], After = [h|_], append(Before, [x|After], L).
L = [a, b, c, d, x, e, f, g, x|...],
After = [h, i, j],
Before = [a, b, c, d, x, e, f, g].

This is just the tip.

edited Feb 10 '15 at 05:14

answered Feb 08 '15 at 11:12

1

Downside: This approach is not steadfast. If `Before` or `After ` is (partially) given, the result might be a different one. – false Feb 08 '15 at 16:37
.. like `After = [h|_]` – false Feb 08 '15 at 16:43
@false Yes, but how is that a problem? Saying that `After` must begin with something (in your example, `After = [h|_]`, just puts another requirement, and the solution is "correct", as in, you get what you ask for. – Feb 09 '15 at 09:24
1

The problem is that `After = [h|_], g(After)` and `g(After), After = [h|_]` mean entirely different things. Thus you have to take into account all details of execution instead of simply the set of ground solutions. More complexity means less chance to get it right. – false Feb 09 '15 at 21:00
@fase Yes, because of `once/1`. If it is not there, it works as expected. – Feb 10 '15 at 05:14
You *need* `once/1` to catch exactly the first occurrence, without it you would describe all occurences. – false Feb 10 '15 at 13:35
@false Yes, I realize that. I am not claiming that this is a perfect solution. But saying that changing the order of the goals leads to "entirely different things" is a slight exaggeration which might lead to confusion. – Feb 10 '15 at 13:48
The situation is pretty much the same when you mix these goals with constraints where you have much less control of what is instantiated when. – false Feb 10 '15 at 13:49
@false Getting philosophical again, but many (most) questions here on SO "how do I do X" are best answered with "don't do it" (this includes my questions, too). This question is a perfect example. I know that your answer is good, I know that my answer is not completely useless, and understand its limitations. I don't even know why I keep answering misguided questions with misguided answers. – Feb 10 '15 at 13:51
As long as you do not explicitly shield your solution against those uses that you do not cover, your program must be considered incorrect. – false Feb 10 '15 at 13:54
@false This is not different from saying "as long as you don't understand what you are doing, all your programs must be incorrect", which for most of us mortals is actually true. – Feb 10 '15 at 13:56
I cannot agree with you. – false Feb 10 '15 at 13:58
@false I would have been shocked if you did :) in my defense, I do read carefully what you write and try to learn. – Feb 10 '15 at 13:59

Split a list in separate lists

3 Answers3

Edit 2015-05-25