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

Answer 2

@Will Ness的答案是好的和詳細的。我剛纔添加的可能性，如果你的Prolog提供它，使用「高階」內建（即接收謂詞作爲參數謂詞）：

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

你可以找到here了一個簡要的解釋內置。

Answer 3

您可以使用clpfd。通過這種方式，您可以獲得純粹的關係：

:- 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). 

您可以使用它不僅將列表拆分爲均等和可能性。但你可以走得更遠。以下是SWI的交互，但您在SICStus中與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. 

下一個可能是最惱人的：在這裏，我們問是否有一個整數EO是偶數和奇數。當然，這樣的整數不能存在。但我們仍然得到兩個答案！

?- 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. 

這說明了答案和解決方案之間的區別。我們在這裏得到兩個答案，但都不包含解決方案。大多數情況下答案都包含一個或多個解決方案，但在這種情況下也可以不包含任何解決方案。這種答案有時被稱爲不一致。

不一致不一定被認爲是實施的錯誤。它們相當於一種工程折衷：與實際效益相比，確保一致性可能成本高昂。並且：Prolog不會產生不正確的答案：顯示必須保存的條件。即使這種情況證明是錯誤的。

Answer 4

這個答案是基於clpfd，meta-predicatetpartition/4和物化測試zodd_t/2：

:- use_module(library(clpfd)). 

結合使用tpartition/4與zodd_t/2我們可以簡單的寫：

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