Prolog: partition integer list items by their parity

Question

Write a predicate which takes as input a list of integers, L, and produces two lists: the list containing the even elements from L and the list of odd elements from L.

?- separate_parity([1,2,3,4,5,6], Es, Os).
Es = [2,4,6], Os = [1,3,5] ? ;
no

Answer 1

Just use structural recursion on lists. Write down the equivalences for each mutually exclusive case:

parity_partition([A|B], [A|X], Y):- 0 is A mod 2, parity_partition(B,X,Y).
parity_partition([A|B], X, [A|Y]):- 1 is A mod 2, parity_partition(B,X,Y).
parity_partition([],[],[]).

This means: relation parity_partition(L,E,O) holds,

1. in case L=[A|B] and A is even, when E=[A|X], O=Y and relation parity_partition(B,X,Y) holds.
2. in case L=[A|B] and A is odd, when E=X, O=[A|Y] and relation parity_partition(B,X,Y) holds.
3. in case L=[], when E=[] and O=[].

Just writing down these equivalences gives us the Prolog program to solve this.

---

Operationally, this means: to separate a list L into a list of evens E and a list of odds O,

  1. if `L` is a non-empty list `[A|B]`,
     1a.  if `A` is even, 
              allocate new list node for `E=[H|T]`, 
              set its data field `H=A`,
              and continue separating the rest of input list `B`
                           into `T` and `O` ; or
     1b.  if `A` is odd, 
              allocate new list node for `O=[H|T]`, 
              set its data field `H=A`,
              and continue separating the rest of input list `B`
                           into `E` and `T` ; or
  2. if `L` is an empty list, set both `E` and `O` to be empty lists

the actual sequence of operations might be a little bit different but conceptually the same:

  1. try to unify L=[A|B], E=[A|X]. If not, go to 2. 
     1a. check if A is even. 
         If not, abandon the instantiations made 
                 as part of unifications, and go to 2.
     1b. Continue with B, X, and the same O: use B as L, X as E, and go to 1.
  2. try to unify L=[A|B], O=[A|Y]. If not, go to 3.
     2a. check if A is odd. 
         If not, abandon the instantiations made 
                 as part of unifications, and go to 3.
     2b. Continue with B, Y, and the same E: use B as L, Y as O, and go to 1.
  3. Unify L,E,O with [].

Answer 2

You can use clpfd for this. In this manner you get a pure relation:

:- use_module(library(clpfd)).
list_evens_odds([], [], []).
list_evens_odds([E|Zs], [E|Es], Os) :-
   0 #= E mod 2,
   list_evens_odds(Zs, Es, Os).
list_evens_odds([E|Zs], Es, [E|Os]) :-
   1 #= E mod 2,
   list_evens_odds(Zs, Es, Os).

You can use this not only to split a list into evens and odds. But you can go even further. The following interaction is with SWI, but you get similar in SICStus with asserta(clpfd:full_answer).

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

?- Zs = [A,B,C], list_evens_odds(Zs, Es, Os).
Zs = [A, B, C],
Es = [A, B, C],
Os = [],
A mod 2#=0,
B mod 2#=0,
C mod 2#=0 ;
Zs = [A, B, C],
Es = [A, B],
Os = [C],
A mod 2#=0,
B mod 2#=0,
C mod 2#=1 ;
Zs = [A, B, C],
Es = [A, C],
Os = [B],
A mod 2#=0,
B mod 2#=1,
C mod 2#=0 ...

?- Es = [E], Os = [O], list_evens_odds(Zs, Es, Os).
Es = [E],
Os = [O],
Zs = [E, O],
E mod 2#=0,
O mod 2#=1 ;
Es = [E],
Os = [O],
Zs = [O, E],
E mod 2#=0,
O mod 2#=1 ;
false.

The next is probably most irritating: Here, we ask whether there is an integer EO that is both even and odd. Certainly, such an integer cannot exist. But we still get two answers!

?- EOs=[EO], list_evens_odds(Zs, EOs, EOs).
EOs = [EO],
Zs = [EO, EO],
EO mod 2#=1,
EO mod 2#=0 ;
EOs = [EO],
Zs = [EO, EO],
EO mod 2#=0,
EO mod 2#=1 ;
false.

This illustrates the difference between answers and solutions. We get here two answers, but both do not contain a solution. Most of the time an answer contains one or more solutions, but it can also contain none as in this case. Such answers are sometimes called inconsistencies.

Inconsistencies are not necessarily considered a bug of an implementation. They are rather an engineering tradeoff: Ensuring consistency might be very costly compared to the actual benefits. And: Prolog does not produce an incorrect answer: For the condition that has to hold is shown. Even if that condition turns out to be false.

Answer 3

This answer is based on clpfd, meta-predicate tpartition/4, and reified test zodd_t/2:

:- use_module(library(clpfd)).

Using tpartition/4 in combination with zodd_t/2 we can simply write:

?- tpartition(zodd_truth,[1,2,3,4,5,6],Es,Os).
Es = [1,3,5], Os = [2,4,6].                 % succeeds deterministically

Answer 4

the answer from @Will Ness is good and detailed. I'll just add the possibility, if your Prolog offers it, to use a 'higher order' builtin (i.e. a predicate that receives a predicate as argument):

separate_parity(L, E, O) :-
    partition(is_even, L, E, O).
is_even(N) :- N mod 2 =:= 0.

You can find here a brief explanation for the builtin.