Segregating Lists in Prolog

A logically pure implementation is very straight-forward, thanks to clpfd:

:- use_module(library(clpfd)).

list_evens_odds([],[],[]).
list_evens_odds([X|Xs],[X|Es],Os) :-
   X mod 2 #= 0,
   list_evens_odds(Xs,Es,Os).
list_evens_odds([X|Xs],Es,[X|Os]) :-
   X mod 2 #= 1,
   list_evens_odds(Xs,Es,Os).

Some sample queries we expect to succeed (with a finite sequence of answers):

?- Xs = [1,2,3,4,5,6,7], list_evens_odds(Xs,Es,Os).
Xs = [1,2,3,4,5,6,7],
Es = [  2,  4,  6  ],
Os = [1,  3,  5,  7] ;
false.

?- list_evens_odds(Ls,[2,4],[1,3]).
Ls = [2,4,1,3] ? ;
Ls = [2,1,4,3] ? ;
Ls = [2,1,3,4] ? ;
Ls = [1,2,4,3] ? ;
Ls = [1,2,3,4] ? ;
Ls = [1,3,2,4] ? ;
no

What about queries we expect to fail?

?- list_evens_odds(Ls,[2,4,5],[1,3]).
no
?- list_evens_odds(Ls,[2,4],[1,3,6]).
no
?- list_evens_odds([_,_,_],[2,4],[1,3]).
no

At last, the most general query:

?- assert(clpfd:full_answer).
yes

?- list_evens_odds(Ls,Es,Os).
Ls = [],   Es = [],   Os = []                              ? ;
Ls = [_A], Es = [_A], Os = [], _A mod 2#=0, _A in inf..sup ? ...

---

Edit 2015-05-06

Here’s another way to do it with logical-purity!

Use the meta-predicate tpartition/4 together with zeven_t/2 or zodd_t/2.

bool01_t(1,true).
bool01_t(0,false).

zeven_t(Z,Truth) :- Z mod 2 #= 0 #<==> B, bool01_t(B,Truth).

%zodd_t(Z,Truth) :- Z mod 2 #= 1 #<==> B, bool01_t(B,Truth).
zodd_t(Z,Truth)  :- Z mod 2 #=         B, bool01_t(B,Truth). % tweaked

zeven_t/2 reifies the evenness of an integer, zodd_t/2 the oddness.

With everything in place, let’s run some queries!

?- tpartition(zeven_t,[1,2,3,4,5,6,7],Es,Os).
Es = [2,4,6], Os = [1,3,5,7].
?- tpartition(zodd_t ,[1,2,3,4,5,6,7],Os,Es). % argument order differs
Es = [2,4,6], Os = [1,3,5,7].

Both succeed deterministically. The equivalent query using list_evens_odds/3 does not.