prolog - 如何在递归Prolog中将数据插入列表中

Question

试图弄清楚如何返回一个包含 A 人的祖先直到 B 人的列表。例如，我有以下事实:

parent(john,paul).
parent(paul,henry).
parent(henry,helen).

我可以使用下面的代码来找到 Y 的祖先

ancestor(X,Y):-parent(X,Y).
ancestor(X,Y):-parent(X,Z), ancestor(Z,Y).

我想要一个函数 list(X,Y,L)这将返回 X 之间的祖先列表, Y .
例如， List(john,helen,L)将返回 L = [paul, henry]
根据前面的代码，我知道 Z 是所需的值。但我不知道如何将这些值插入列表并返回。

我试过这个，但没有按预期工作:

list([]).
ancestorList(X,Y,L):- parent(X,Y).
ancestorList(X,Y,L):- parent(P,Y), list(Old), L = [P | Old], ancestorList(X,P,L).

任何帮助将不胜感激。

Answer 1

根据您的方法，您 - 就像许多其他开始使用 Prolog 的人一样 - 旨在将 Prolog 编程为“命令式语言”。

在 Prolog 中，您不能重新分配变量。如果你写 L = [] ，那么这意味着，除非你回溯，L将永远是空列表。所以打电话L = [P|Old]稍后，将导致 false ，因为 unficiation 永远不会产生 []和 [_|_]是平等的。

因此，您不能通过首先将列表初始化为 [] 来“创建”列表。然后后来“改变”它，因为改变是(或应该)是不可能的。有一些值得注意的异常(exception)(比如用 assert/1 添加事实，但这些通常是“糟糕的设计”)。

在实现谓词之前，最好先设计一个归纳定义，指定您要实现的逻辑关系。然后，您可以将此定义转换为谓词。

这里的归纳定义可能如下所示:

ancestorList(X, Z, L)两人份 X和 Z是 [X]给定 parent(X, Z)持有；和

ancestorList(X, Y, L)两人份 X和 Y是一个以 X 开头的列表给定 parent(X, Y) hols，列表的其余部分是 ancestorList/3的 Y高达 Z .

一旦我们有了这个归纳定义，我们就可以将其翻译成代码。这个“骨架”看起来像:

ancestorList(X, Z, ___):-
    ___.
ancestorList(X, Z, ___) :-
    parent(X, Y),
    ___.

与 ___还需要填写。

鉴于没有无限 parent/2链，我们知道这个程序不会陷入无限循环，如果两个给定的父链之间没有父链，则最终会失败。