Splitting a list of integers into a list of positive integers and a list of negative integers

Question

I've been trying to create a predicate in Prolog which splits a list of integers into a list of positive integers and into a list of negative integers.

Sample query with expected result:

?- split([1,-2,3,4,-8],X,Y).
X = [1,3,4],
Y = [-2,-8].

This is the code I got so far:

split([], [], []).
split([Head|Tail], List1, List2) :- split(Tail, [Head|List1], List2), Head>=0.
split([Head|Tail], List1, List2) :- split(Tail, List1, [Head|List2]), Head<0.

I can't seem to figure out what I'm doing wrong.

What should happen if the input list contains a zero? – Kaarel Mar 03 '12 at 21:35 — Kaarel, Mar 03 '12 at 21:35
It should be put in the list of positive integers. – Martin Mar 04 '12 at 00:38 — Martin, Mar 04 '12 at 00:38

Sufian Latif · Accepted Answer · 2012-03-03T15:25:19.353

9

The recursive part is not quite correct.

split([], [], []).
split([Head|Tail], [Head|List1], List2) :- Head>=0, split(Tail, List1, List2).
split([Head|Tail], List1, [Head|List2]) :- Head<0, split(Tail, List1, List2).

The Head should be added to the positive list if Head >= 0 and to the negative list when Head < 0.

Moreover, checking the sign of Head at the beginning is better, because it will prevent unnecessary recursive calls.

edited Mar 03 '12 at 15:25

answered Mar 03 '12 at 15:15

Sufian Latif

13,086
3
33
70

Thank you so much! Thanks for explaining the optimization as well. – Martin Mar 03 '12 at 18:01
@MizaCoroda Use `trace` to understand the recursions :) – Sufian Latif Mar 03 '12 at 18:12
@FlopCode: Your solution is nice, but on current Prolog implementations it consumes additional auxiliary space proportional to the number of non-negative elements. It is probably best to use `compare/3` here. – false Mar 03 '12 at 18:55
Can you please illustrate the derivation tree of the given solution? That would be a great help. – Samitha Chathuranga Mar 04 '14 at 05:59

Kaarel · Answer 2 · 2015-05-05T19:32:58.797

6

In SWI-Prolog you can use the predicate partition/4 (which is typically autoloaded from the apply module):

?- partition(=<(0), [1,-2,3,4,-8,0], X, Y).
X = [1, 3, 4, 0],
Y = [-2, -8].

edited May 05 '15 at 19:32

answered Mar 03 '12 at 15:39

Kaarel

10,554
4
56
78

SWI-Prolog `partition/4` predicate is not a built-in predicate. It's a library predicate defined in the `apply` module (which is most likely being auto-loaded). – Paulo Moura May 05 '15 at 18:23
@PauloMoura Tnx, fixed. – Kaarel May 05 '15 at 19:33

false · Answer 3 · 2022-08-20T17:22:59.580

Here is a definition using constraints. In this case, it is library(clpfd) of SWI and YAP (maybe also XSB). This library is so general that it subsumes regular integer uses.

:- use_module(library(clpfd)).

Using reification:

split([], [], []).
split([E|Es], Poss, Negs) :-
   E #>= 0 #<==> B,
   i_split(B, E, Es, Poss, Negs).

i_split(1, E, Es, [E|Poss], Negs) :-
   split(Es, Poss, Negs).
i_split(0, E, Es, Poss, [E|Negs]) :-
   split(Es, Poss, Negs).

Alternatively, you can use zcompare/3, I prefer that version:

split([], [], []).
split([E|Es], Poss, Negs) :-
   zcompare(Order, E, 0),
   c_split(Order, E, Es, Poss, Negs).

c_split(>, E, Es, [E|Poss], Negs) :-
   split(Es, Poss, Negs).
c_split(=, E, Es, [E|Poss], Negs) :-
   split(Es, Poss, Negs).
c_split(<, E, Es, Poss, [E|Negs]) :-
   split(Es, Poss, Negs).

You can use it for the regular queries, and for more general ones, like

?- split(Es,[A],[]).
   Es = [A], A in 1..sup
;  Es = [0], A = 0
;  false.

score 2 · Answer 4 · edited May 23 '17 at 12:24

Stay logically pure and efficient. How? By using meta-predicate tpartition/4 and (#=<)/3!

First, let us define (#=<)/3, the reified version of (#=<)/2, based on bool01_t/2.
For the sake of completeness, let's also define (#<)/3, (#>)/3, and (#>=)/3!

#=<(X,Y,Truth) :- X #=< Y #<==> B, bool01_t(B,Truth).

#<( X,Y,Truth) :- X #<  Y #<==> B, bool01_t(B,Truth).

#>( X,Y,Truth) :- X #>  Y #<==> B, bool01_t(B,Truth).

#>=(X,Y,Truth) :- X #>= Y #<==> B, bool01_t(B,Truth).

That's it! Now, let's do the split the OP wanted:

?- tpartition(#=<(0),[1,-2,3,4,-8,0],Ts,Fs).
Ts = [1,3,4,0], Fs = [-2,-8].                   % succeeds deterministically

This is monotone, so we get sound answers even when using general, non-ground terms:

?- tpartition(#=<(0),[A,B,C],Ts,Fs).
Ts = [     ], Fs = [A,B,C], A in inf.. -1, B in inf.. -1, C in inf.. -1 ;
Ts = [    C], Fs = [A,B  ], A in inf.. -1, B in inf.. -1, C in   0..sup ;
Ts = [  B  ], Fs = [A,  C], A in inf.. -1, B in   0..sup, C in inf.. -1 ;
Ts = [  B,C], Fs = [A    ], A in inf.. -1, B in   0..sup, C in   0..sup ;
Ts = [A    ], Fs = [  B,C], A in   0..sup, B in inf.. -1, C in inf.. -1 ;
Ts = [A,  C], Fs = [  B  ], A in   0..sup, B in inf.. -1, C in   0..sup ;
Ts = [A,B  ], Fs = [    C], A in   0..sup, B in   0..sup, C in inf.. -1 ;
Ts = [A,B,C], Fs = [     ], A in   0..sup, B in   0..sup, C in   0..sup .

Edit 2015-06-02

What if we used the SWI-Prolog library predicate partition/4 in above query?

?- partition(#=<(0),[A,B,C],Ts,Fs).
Ts = [A,B,C], Fs = [], A in 0..sup, B in 0..sup, C in 0..sup.

We would lose 7 out of 8 solutions because partition/4 is not monotone!

`#=<(X, Y, Truth) :- X #=< Y #<==> B, ( B = 0, Truth = false ; B = 1, Truth = true ).` (provided there is indexing for `B = 0 ; B = 1`) — false, May 05 '15 at 17:33
@false. Sure, why not? What does the `t` in `tfilter` etc actually stand for btw?-) — repeat, Jun 02 '15 at 23:21

Splitting a list of integers into a list of positive integers and a list of negative integers

4 Answers4

Edit 2015-06-02

Linked