Prolog 代码将列表的各个部分拆分为连续的偶数和奇数部分

Question

有人向我提出以下问题:

任何整数列表都可以(唯一地)分解为“奇偶校验游程”，其中每个游程都是原始列表中连续偶数或奇数的(最大)序列。例如，列表列表 = [8,0,4,3,7,2,-1,9,9]可以分为 [8, 0, 4]、[3, 7]、[2] 和 [-1, 9, 9]编写一个谓词 paruns(List, RunList) 将数字列表转换为相应的奇偶校验运行列表。例如:

?- paruns([8,0,4,3,7,2,-1,9,9], RunList).
RunList = [[8, 0, 4], [3, 7], [2], [-1, 9, 9]] 

这是我尝试过的代码，由于一个建议，它似乎适用于上述示例案例，但我遇到了一个问题，当我运行 paruns([8,0,4], RunList)。 它打印 RunList = [[8,0,4],[]]。任何建议将不胜感激:)

paruns([],[]).
paruns([Head | Tail], [E, O | S]) :-
   even([Head | Tail], E, Last),
   odd(Last, O, Last1),
   paruns(Last1, S).

even([Head | Tail], [], [Head | Tail]) :-
   Head mod 2 =:= 1.
even([Head | Tail], [Head | L], Last) :-
   Head mod 2 =:= 0,
   even(Tail, L, Last).
even([],[],[]).

odd([Head | Tail], [], [Head, Tail]) :-
   Head mod 2 =:= 0.
odd([Head | Tail], [Head | L], Last) :-
   Head mod 2 =:= 1,
   odd(Tail, L, Last).
odd([],[],[]).

Answer 1

Prolog 的一个主要吸引力在于它的关系性质。这意味着，只要我们坚持足够通用的原语，我们通常可以在几个方向使用Prolog谓词。

在这个具体案例中，由于您正在对整数进行推理，因此我强烈建议您使用 Prolog 系统的CLP(FD) 约束来从这种通用性中受益。请参阅clpfd有关这一重要声明性功能的更多信息。

此外，由于您描述的是列表，请考虑使用DCG 表示法 ( dcg )。

这是适合您任务的关系解决方案:

parity_runs([], [])     --> [].parity_runs([E|Es], Os) --> [E], { E mod 2 #= 0 }, parity_runs(Es, Os).parity_runs(Es, [O|Os]) --> [O], { O mod 2 #= 1 }, parity_runs(Es, Os).

我们可以将它用于您发布的测试用例，其中指定了列表:

?- phrase(parity_runs(Es, Os), [8,0,4,3,7,2,-1,9,9]).Es = [8, 0, 4, 2],Os = [3, 7, -1, 9, 9] ;false.

此外，我们还可以将其用于其他方向。例如，假设运行已知，但列表未知:

?- phrase(parity_runs([2,4], [1,3]), Ls).Ls = [2, 4, 1, 3] ;Ls = [2, 1, 4, 3] ;Ls = [2, 1, 3, 4] ;Ls = [1, 2, 4, 3] ;Ls = [1, 2, 3, 4] ;Ls = [1, 3, 2, 4] ;false.

此外，我们还可以发布最一般的查询，其中什么都不知道:

?- phrase(parity_runs(Es, Os), Ls).Es = Os, Os = Ls, Ls = [] ;Es = Ls, Ls = [_2012],Os = [],_2012 mod 2#=0 ;Es = Ls, Ls = [_256, _258],Os = [],_256 mod 2#=0,_258 mod 2#=0 ;Es = Ls, Ls = [_826, _832, _838],Os = [],_826 mod 2#=0,_832 mod 2#=0,_838 mod 2#=0 ;etc.

为了公平列举答案，我们可以使用迭代深化:

?- length(Ls, _), phrase(parity_runs(Es, Os), Ls).Ls = Es, Es = Os, Os = [] ;Ls = Es, Es = [_168],Os = [],_168 mod 2#=0 ;Ls = Os, Os = [_550],Es = [],_550 mod 2#=1 ;Ls = Es, Es = [_770, _776],Os = [],_770 mod 2#=0,_776 mod 2#=0 ;Ls = [_770, _776],Es = [_770],Os = [_776],_770 mod 2#=0,_776 mod 2#=1 ;etc.