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
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,
L=[A|B] and A is even, when E=[A|X], O=Y and relation parity_partition(B,X,Y) holds. L=[A|B] and A is odd, when E=X, O=[A|Y] and relation parity_partition(B,X,Y) holds. 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 [].