Prolog：递归函数分支和“返回”-Java 学习之路

我写了一些递归的Prolog谓词，并且遇到了一个我目前还不太了解的观点 .

例如，我编写了谓词 split/3 ，它将整数列表分为非负整数列表和负整数列表：

Version 1

split([], [], []).
split([ListHead|ListTail], [ListHead|PList], NList) :- 
   ListHead >= 0,
   split(ListTail, PList, NList).
split([ListHead|ListTail], PList, [ListHead|NList]) :- 
   ListHead < 0,
   split(ListTail, PList, NList).

但在达到该解决方案之前，我在下面编写了解决方案，并想知道为什么它不起作用：

Version 2

split([], [], []).
split([ListHead|ListTail], PList, NList) :- 
   ListHead >= 0,
   split(ListTail, [ListHead|PList], NList).
split([ListHead|ListTail], PList, NList) :- 
   ListHead < 0,
   split(ListTail, PList, [ListHead|NList]).

哪里：

第一个给定的参数分为 ListHead 和 ListTail .
如果 ListHead 元素（整数）大于或等于0，则它前置于非负整数列表，并使用参数进行递归调用，并使用未经操作的 Nlist .
如果 ListHead 元素（整数）小于0，则它会添加到负整数列表中，并用作带有未操作 PList 的递归调用的参数 .

我'm not getting why version 2 doesn'工作;它编译时没有任何警告，但只返回错误 . 与上述版本的唯一区别在于，整数元素前置为 Nlist 或 PList 是在谓词定义中（在 :- 运算符之后）完成的，而不是在谓词调用的参数中完成的 . 对我来说，将结果作为下一次调用的参数的一部分进行前置是有意义的...

我觉得我错过了一些关于Prolog的“搜索”递归调用的方式！

有人可以解释为什么版本1按预期工作而版本2没有？

3 回答

0
它不起作用，因为当你回到后退时你会失去元素 .

在版本1中，当返回开始时，PList用[]实例化，你开始堆叠这样的元素：
```
[ListHead|PList]    the same as   [ListHead| [] ] at first level.
```
最后你有所有的清单 .

在版本2中，Plist仍然未实例化，切割条件永远不会满足，因为您有类似的东西：
```
[[]|1,2,3,4,5,6]
```
并且与任何东西都不匹配 .

在版本2中，您需要在最后使用累加器（或辅助变量）将累加器复制到实际变量中，如下所示：
```
split([],A,B,A,B).
split([ListHead|ListTail], PList, NList, PListAcum, NListAcum) :- ListHead >= 0, 
    split(ListTail, PList, NList, [ListHead|PListAcum], NListAcum).
split([ListHead|ListTail], PList, NList, PListAcum, NListAcum) :- ListHead < 0, 
    split(ListTail, PList, NList,  PListAcum, [ListHead|NListAcum]).
```
你这样称呼：
```
split([1,2,3,-1,-2,-3] , P, N, [], []);
```
让我解释一下，累加器已初始化并累积数据 . 当列表为空时，第一行只将累加器复制到实变量中，然后累加器将其元素丢失回y递归（如果你查看不同回溯级别上的变量名称，你会明白）但实际变量仍然存在通过回溯保持不变 .

你需要为你想要返回的每个变量都有一个累加器，或者像你的第一个版本一样 .

您可以搜索有关累加器的信息 .

映入眼帘 .
回复于 2024-04-17T04:02:22+08:00
0
模式匹配它是Prolog的一个关键特性，占该语言功能的一半，并且一起进行回溯，允许以优雅但不寻常的方式表达控制 . 以下是您可以“更正”第二个版本的方法
```
split([],[],[]).
split([ListHead|ListTail], PList, NList) :-
    ListHead >= 0, split(ListTail, Temp, NList), PList=[ListHead|Temp].
split([ListHead|ListTail], PList, NList) :-
    ListHead < 0, split(ListTail, PList, Temp), NList=[ListHead|Temp].
```
当然问题是基本案例无法与原始版本匹配 .
回复于 2024-04-17T04:02:22+08:00
0
使用较短的变量名重写代码并将规则头分配移到规则体中，可能更容易阅读 .

我们假设它被一个给定的列表调用，产生它的两个半部分，其中一个是非负数（我们称之为“正数”，简称为0，包括0），另一个是负数元素 .

Version 1 读，
```
split([],[],[]).
split(X, Y, Z) :-        X = [A|B], Y = [A|POS], Z = NEG,
    A >= 0, split(B, POS, NEG).
split(X, Y, Z) :-        X = [A|B], Y = POS, Z = [A|NEG],
    A <  0, split(B, POS, NEG).
```
- 一个空列表分成两个空列表;
- 分割一个列表 X 与头 A 这是非负的，我们将它的尾部 B 分成两个列表，正面列表 POS 和负面列表 NEG ，并且（自然地）将 A 前置 B 的正面值作为 X 返回是积极的;
- 分割一个列表 X 与头 A 这是否定的，我们将它的尾部 B 分成两个列表，正面列表 POS 和负面列表 NEG ，并且（自然地）将 A 前置为 B 的否定值，作为 X 返回消极的 .
Version 2 读，
```
split([],[],[]).
split(X, Y, Z) :-        X = [A|B], Y = POS, Z = NEG,
    A >= 0, split(B, [A|POS], NEG).
split(X, Y, Z) :-        X = [A|B], Y = POS, Z = NEG,
    A <  0, split(B, POS, [A|NEG]).
```
- 一个空列表分成两个空列表;
- 将 X 与头 A 拆分为非负，我们将其尾部 B 分成两个列表，正面列表和负面列表，我们要求 B 的正面与 A （其中最不可能的）;然后我们只返回 B 的正面（即 POS ）的尾部作为 X 的正面（即一个元素更短...... ??）;
- 与负头元素类似 .
我想你可以看出这没有任何意义 .

这里没有回溯，因为所有规则的子句都是互斥的（保证在回溯时失败） .
回复于 2024-04-17T04:02:22+08:00

Prolog：递归函数分支和“返回”

3 回答

相关问题