list - 了解Swi-prolog中的拆分

Question

我有这段代码可以将输入列表分成两半。好像还可以

halve(List,A,B) :- halve(List,List,A,B), !.
halve(B,[],[],B).
halve(B,[_],[],B).
halve([H|T],[_,_|T2],[H|A],B) :-halve(T,T2,A,B). 

好的，所以我尝试对其进行解码。开头很清楚：

“减半获取列表和2个逻辑变量”是这样的：

halve(List,A,B) 

（1）然后继续这一部分：

:- halve(List,List,A,B).

这意味着，我要从第一个创建新的两个列表（列表，列表），或者是什么？确切地代表“：-”的是什么？我猜新的列表= A和B将减半，对吧？

（2）第二，请，我不太明白这两行：

halve(B,[],[],B).
halve(B,[_],[],B).

也许您可以在一些例子中解释一下？

（3）好吧，希望您对（1）和（2）做出解释后，我会自己做最后一部分...

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B). 

非常感谢您对我的帮助。



好的，我们的第一个问题已经有了解决方案。长话短说，它是这样的：

halve([1,2,3,4,5],[1,2],[3,4,5]). 
->true

如果您注意到它将列表分成两半，但是如果列表中元素的数量为奇数，则后半部分为较大的元素。

现在，我想要获得的是第一个更大的。

所以我在想这个：

我要达到这个目标：

Halves_div([1,2,3],A,B).
A=[1,2],
B=[3].

假设我的输入是列表：[1,2,3]。因此，我将从分割列表的头部和尾部开始： [H|T]，然后将 H与新的空列表合并-我的第一半（ A）。
之后，我有A = [1]，B = []和Input = [2,3]。

对于合并，我有：

merge([],List,List).
merge([H|T],List,[H|New]) :- merge(T,List,New).

还有一件事-我需要检查第一半是否已经> =第二半，对吗？

所以这是我的主意，我唯一希望您提供帮助的就是写在序言中。我有点困惑如何将其放在一起。

谢谢！



看来我的解决方案想法太复杂了，我发现更好的东西！

Answer 1

首先，Prolog子句如下所示：

Head :- Body

您可以将其读为“ Head（如果 Body”）或“ Body暗示 Head”。

请注意，有时您只有

Head

那是因为Head总是 true。在这种情况下，我们不称 Head子句，而是称其为事实。

所以在这里，我们有：

halve(List,A,B) :- halve(List,List,A,B).

这意味着，如果 halve(List, A, B)为true，则 halve(List, List, A, B)为true。具体来说，这只是将 halve/3的工作委托给 halve/4的一种方法，即所谓的工作者谓词。

为什么我们需要一个工人谓词？好吧，因为在这里我们想使用另一个变量来计算 A和 B项。但是我们无法使用 halve/3进行操作，因为 halve/3的3个参数点已由输入列表 List，结果的前半部分， A和结果的下半部分占用， B。

关于 List, List事情，这只是一种说法，就像使用任何编程语言一样，我们用相同的第一和第二个参数调用 halve/4。

然后有趣的东西开始了。 Prolog将尝试证明 halve/4对于某些给定参数是正确的。假设以这种方式说明我们称为 halve/3的执行：

?- halve([1, 2], A, B).

然后，如果您按照我之前提到的内容进行操作，那么Prolog现在将通过使用以下参数证明 halve/3正确，从而尝试证明 halve/4正确。

为此，Prolog有3种选择。首选是以下子句：

halve(B,[],[],B).

显然，那是行不通的。因为当Prolog尝试通过统一使调用方的第二个参数适合被调用方的第二个参数时，它将失败。因为
halve([1, 2], [1, 2], A, B).无法与 [1, 2]统一。

仅剩两个选择，下一个是：

halve(B,[_],[],B).

同样，Prolog无法统一 []和 [1, 2]，因为 [_]只是一个变量（如果遇到麻烦，请参见 my post有关匿名变量 _的信息）。

因此，Prolog必须为您提出的问题找到解决方案的唯一机会是最后一个子句，即：

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B).

在这里，Prolog将找到一种统一事物的方法，让我们看看哪种方法：


我们必须将 _与 [1, 2]统一起来。这意味着 [H|T]和 H = 1.
我们必须将 T = [2].与 [1, 2]统一起来。这表示 [_,_|T2]
现在我们开始用下一个统一的结果建立结果，即 T2 = [].（我对第二个 A = [H|A']进行了预填，因为变量是局部作用域的，并且它们是不同的）。在这里，我们告诉我们从子句的主体中计算出结果时，将在其中添加 A。这里的 H是 H，因此我们已经知道 1的第一个元素将是 A。


好吧好，统一成功了，太好了！我们可以继续该条款的正文。它只是使用这些值（如上计算）以递归方式调用 1：

halve([2], [], A, B).

在这里，我们从头再来。尽管这次情况很快，因为Prolog的首选将非常适合：

halve(B,[],[],B).

可以统一为

halve([2], [], A, B).

具有以下值： halve/4和 A = []。

因此，这是一个好步骤，我们现在到达了递归的“基本情况”。现在，我们只需要从下到上建立结果。还记得上面几步递归调用谓词 B = [2]吗？我们已经说过， halve/4的第一个元素是 A。现在我们知道尾巴是 1，所以我们可以声明 []。我们没有对 A = [1]进行特别说明，因此 B保持不变。

现在，我详细介绍了执行过程，您可能想知道，为什么这样做有效？好吧，如果您注意的话，您会注意到 B = [2]的第二个参数的执行速度是第一个参数的两倍。 halve/4与 [H|T]。这意味着当我们使用第二个参数将列表结尾时，第一个仍然在列表的中间。这样，我们可以将事物分为两部分。

希望我能帮助您了解这里工作中的一些细微问题。