Prolog, split list into two lists

Question

I got a problem with lists. What I need to do is to split one list [1,-2,3,-4], into two lists [1,3] and [-2,-4]. My code looks like the following:

lists([],_,_).
lists([X|Xs],Y,Z):- lists(Xs,Y,Z), X>0 -> append([X],Y,Y) ; append([X],Z,Z).

and I'm getting

Y = [1|Y],
Z = [-2|Z].

What am I doing wrong?

Solution 1

Refer this:

domains
    list=integer*

predicates
    split(list,list,list)
clauses
    split([],[],[]).
    split([X|L],[X|L1],L2):-
        X>= 0,
        !,    
        split(L,L1,L2).

    split([X|L],L1,[X|L2]):-
        split(L,L1,L2).

Output :

Goal: split([1,2,-3,4,-5,2],X,Y)
Solution: X=[1,2,4,2], Y=[-3,-5]

See, if that helps.

Solution 2

If your Prolog system offers clpfd you could preserve logical-purity. Want to know how? Read on!

We take the second definition of lists/3 that @CapelliC wrote in his answer as a starting point, and replace partition/4 by tpartition/4 and (<)/2 by (#<)/3:

lists(A,B,C) :- tpartition(#<(0),A,B,C).

Let's run a sample query!

?- As = [0,1,2,-2,3,4,-4,5,6,7,0], lists(As,Bs,Cs).
As = [0,1,2,-2,3,4,-4,5,6,7,0],
Bs = [  1,2,   3,4,   5,6,7  ],
Cs = [0,    -2,    -4,      0].

As we use monotone code, we get logically sound answers for more general queries:

?- As = [X,Y], lists(As,Bs,Cs).
As = [X,Y], Bs = [X,Y], Cs = [   ], X in   1..sup, Y in   1..sup ;
As = [X,Y], Bs = [X  ], Cs = [  Y], X in   1..sup, Y in inf..0   ;
As = [X,Y], Bs = [  Y], Cs = [X  ], X in inf..0  , Y in   1..sup ;
As = [X,Y], Bs = [   ], Cs = [X,Y], X in inf..0  , Y in inf..0   . 

Solution 3

Here you have. It splits a list, and does not matter if have odd or even items number.

div(L, A, B) :-
    append(A, B, L),
    length(A, N),
    length(B, N).

div(L, A, B) :-
    append(A, B, L),
    length(A, N),
    N1 is N + 1,
    length(B, N1).

div(L, A, B) :-
    append(A, B, L),
    length(A, N),
    N1 is N - 1,
    length(B, N1).

Solution 4

Just for variety, this can also be done with a DCG, which is easy to read for a problem like this:

split([], []) --> [].
split([X|T], N) --> [X], { X >= 0 }, split(T, N).
split(P, [X|T]) --> [X], { X < 0 }, split(P, T).

split(L, A, B) :-
    phrase(split(A, B), L).

As in:

| ?- split([1,2,-4,3,-5], A, B).

A = [1,2,3]
B = [-4,-5] ? ;

no

It also provides all the possible solutions in reverse:

| ?- split(L, [1,2,3], [-4,-5]).

L = [1,2,3,-4,-5] ? ;

L = [1,2,-4,3,-5] ? ;

L = [1,2,-4,-5,3] ? ;

L = [1,-4,2,3,-5] ? ;

L = [1,-4,2,-5,3] ? ;

L = [1,-4,-5,2,3] ? ;

L = [-4,1,2,3,-5] ? ;

L = [-4,1,2,-5,3] ? ;

L = [-4,1,-5,2,3] ? ;

L = [-4,-5,1,2,3] ? ;

(2 ms) no

Gaurav's solution will also do this if the cut is removed and an explicit X < 0 check placed in the third clause of the split/3 predicate.

View more solutions