2

这是我做的样本考试中的一个问题。

给出 Prolog 谓词 split_into_pairs 的定义，它接受一个列表作为参数，并作为结果返回一个由成对元素组成的列表。例如，split_into_pairs([1,2,3,4,5,6],X)将作为结果返回X=[[1,2],[3,4],[5,6]]。同样，split_into_pairs([a,2,3,4,a,a,a,a],X)将作为结果返回，X=[[a,2],[3,4],[a,a],[a,a]]而split_into_pairs([1,2,3],X)将返回No。

我相信这并不意味着使用内置谓词来完成，但它也不应该太复杂，因为它只值 8/120 分。

我不确定它应该对两个元素的列表做什么，所以我猜要么没有指定它，所以它返回 no，或者split_into_pairs([A,B],[[A,B]]).

我的主要问题是如何正确地进行递归调用，而不需要额外的括号，而不是像X=[[A,B],[[C,D],[[E,F]]]]？。

我最近的尝试是以下代码的变体，但显然这是不正确的。

split_into_pairs([A,B],[A,B])
split_into_pairs([A,B|T], X) :- split_into_pairs(T, XX), X is [A,B|XX]
4

2 回答 2

3

这是一个相对简单的递归：

split_into_pairs([], []).
split_into_pairs([First, Second | Tail], [[First, Second] | Rest]) :-
    split_into_pairs(Tail, Rest).

第一条规则说一个空列表已经被分成对；第二个要求源列表至少有两个项目，将它们配对，并将尾列表配对的结果插入到它们后面。

这是关于 ideone 的演示。

您的解决方案也可以通过在结果中添加方括号并将规则的第二部分移动到标题中来修复，如下所示：

split_into_pairs([A,B],[[A,B]]).
split_into_pairs([A,B|T], [[A,B]|XX]) :- split_into_pairs(T, XX).

请注意，此解决方案不会将空列表视为对列表，因此split_into_pairs([], X)会失败。

于 2013-06-14T15:44:32.730 回答
0

您的代码几乎是正确的。它有明显的语法问题，以及几个实质性问题：

split_into_pairs([A,B], [ [ A,B ] ] ):- !.

split_into_pairs([A,B|T], X) :- split_into_pairs(T, XX),

      X = [ [ A,B ] | XX ] .

现在它是正确的：=用于代替is（通常与算术运算一起使用），两个子句都以点正确终止，第一个子句添加了一个剪切，以使谓词具有确定性，只产生一个结果。正确的结构是通过将每对元素用括号括在它们自己的列表中来产生的。

虽然这是低效的，因为它描述了一个递归过程- 它在从基本案例返回的路上构造结果。

有效的定义适用于从起始案例前进的道路：

split_into_pairs([A,B],[[A,B]]):- !.
split_into_pairs([A,B|T], X) :- X = [[A,B]|XX], split_into_pairs(T, XX).

这是尾递归模缺点优化技术的精髓，它将递归过程转变为迭代过程- 这样就能够在恒定的堆栈空间中运行。它与带有累加器的尾递归技术非常相似。

必须引入 cut 是因为这两个子句并不相互排斥：与 with 统一的术语[A,B]也可以与[A,B|T], in case统一T=[]。我们可以通过使两个子句互斥来摆脱削减：

split_into_pairs([], [] ).
split_into_pairs([A,B|T], [[A,B]|XX]):- split_into_pairs(T, XX).
于 2013-06-15T12:01:13.813 回答