Prolog:按奇偶校验分区整数列表项

Question

编写一个谓词,它将整数列表作为输入L,并生成两个列表:包含偶数元素L的列表和来自的奇数元素列表L.

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

Answer 1

只需在列表上使用结构递归.记下每个互斥案例的等价:

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([],[],[]).

这意味着:关系parity_partition(L,E,O) 成立,

1. 如果L=[A|B]和A是偶数,当 E=[A|X],O=Y和关系parity_partition(B,X,Y)成立.
2. 在壳体L=[A|B]和A是奇数,时 E=X,O=[A|Y]以及关系parity_partition(B,X,Y)成立.
3. 在情况下L=[],当E=[]和O=[].

只记下这些等价物,我们就可以通过Prolog程序来解决这个问题.

在操作上,这意味着:将列表L分成一个平均E列表和一个赔率列表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

实际的操作顺序可能略有不同,但在概念上是相同的:

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