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 [].