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

Answer 1

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)).

Answer 2

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,[_])

Answer 3

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.