递归地创建Prolog中的后代列表

Question

我对Prolog非常陌生，并且正在与递归地附加到列表中进行斗争。我试图创建一个程序，告诉你一个人是否是另一个人的后代，以及他们之间的后代列表。例如，示例数据和所需的输出：

parent(greatgrandma, grandma).
parent(grandma, mom).
parent(mom, daughter).

?- relatives(greatgrandma, daughter, Lineage).
Lineage = [greatgrandma, grandma, mom, daughter]

?- relatives(mom, son, Lineage).
False.

我能够递归地搜索，以检查两个人是否与下面的代码相关，并让它作为测试基用例.

relatives(X, Y, Lineage):- isChild(X,Y, Lineage).
isChild(X,Y, Lineage):- parent(X,Y), append([X], [Y], Lineage).
isChild(X,Y, Lineage):- parent(X,Z), isChild(Z,Y, Lineage).

但是，到目前为止，我试图从这个子代搜索中构建一个列表的所有工作都没有成功。这是我得到的最接近的：

relatives(X, Y, Lineage):- append([X], Lineage, NewLineage), isChild(X,Y, NewLineage).
isChild(X,Y, Lineage):- parent(X,Z), append(Lineage, [Z], NewLineage), isChild(Z,Y, NewLineage).
isChild(X,Y, Lineage):- parent(X,Y), append(Lineage, [Y], NewLineage).

[trace]  ?- relatives(grandma, daughter, P).
   Call: (10) relatives(grandma, daughter, _12442) ? creep
   Call: (11) lists:append([grandma], _12442, _12904) ? creep
   Exit: (11) lists:append([grandma], _12442, [grandma|_12442]) ? creep
   Call: (11) isChild(grandma, daughter, [grandma|_12442]) ? creep
   Call: (12) parent(grandma, _13040) ? creep
   Exit: (12) parent(grandma, mom) ? creep
   Call: (12) lists:append([grandma|_12442], [mom], _13136) ? creep
   Exit: (12) lists:append([grandma], [mom], [grandma, mom]) ? creep
   Call: (12) isChild(mom, daughter, [grandma, mom]) ? creep
   Call: (13) parent(mom, _13272) ? creep
   Exit: (13) parent(mom, daughter) ? creep
   Call: (13) lists:append([grandma, mom], [daughter], _13368) ? creep
   Exit: (13) lists:append([grandma, mom], [daughter], [grandma, mom, daughter]) ? creep
   Call: (13) isChild(daughter, daughter, [grandma, mom, daughter]) ? creep
   Call: (14) parent(daughter, _13510) ? creep
   Fail: (14) parent(daughter, _13554) ? creep
   Redo: (13) isChild(daughter, daughter, [grandma, mom, daughter]) ? creep
   Call: (14) parent(daughter, daughter) ? creep
   Fail: (14) parent(daughter, daughter) ? creep
   Fail: (13) isChild(daughter, daughter, [grandma, mom, daughter]) ? creep
   Redo: (12) isChild(mom, daughter, [grandma, mom]) ? creep
   Call: (13) parent(mom, daughter) ? creep
   Exit: (13) parent(mom, daughter) ? creep
   Call: (13) lists:append([grandma, mom], [daughter], _13914) ? creep
   Exit: (13) lists:append([grandma, mom], [daughter], [grandma, mom, daughter]) ? creep
   Exit: (12) isChild(mom, daughter, [grandma, mom]) ? creep
   Exit: (11) isChild(grandma, daughter, [grandma]) ? creep
   Exit: (10) relatives(grandma, daughter, []) ? creep
P = [] .

因此，我得到了正确的顺序，奶奶，妈妈，女儿，但我不知道如何返回的值为P，而不是空的列表。此外，使用'son‘的测试会导致使用此代码的没完没了的递归循环，但不会使用前面的基本情况。

如有任何帮助或建议，将不胜感激。

Answer 1

你快到了！如果您想使用这种方法，主要缺少的是下面的观察:如果isChild既接受“当前谱系”，又希望产生“新谱系”，那么它需要两个谱系参数。一个代表“旧”国家，一个代表“新”国家。

如下所示：

isChild(X,Y, Lineage, NewLineage) :-
    parent(X,Z),
    append(Lineage, [Z], Lineage2),
    isChild(Z,Y, Lineage2, NewLineage).
isChild(X,Y, Lineage, NewLineage) :-
    parent(X,Y),
    append(Lineage, [Y], NewLineage).

调用它时，首先需要传递正确的初始谱系：

relatives(X, Y, Lineage) :-
    isChild(X,Y, [X], Lineage).

现在这一切都是你想要的：

?- relatives(grandma, daughter, Lineage).
Lineage = [grandma, mom, daughter] ;
false.

?- relatives(mom, son, Lineage).
false.

然而，，，真正的答案是，在Prolog中执行这种搜索时，通常不会将内容附加到列表中。相反，您可以使用_pre_pend数据。这样做的效率要高得多，而且更短、更易读，中间状态也更少：

ancestor_successor_lineage(Ancestor, Successor, [Ancestor, Successor]) :-
    parent(Ancestor, Successor).
ancestor_successor_lineage(Ancestor, Successor, [Ancestor | Lineage]) :-
    parent(Ancestor, Intermediate),
    ancestor_successor_lineage(Intermediate, Successor, Lineage).

请注意，如果您对谱系不感兴趣，这与您编写的内容本质上是相同的。添加中间状态的记录只是简单地添加一个(而不是像以前一样两个！)额外的参数和使用列表构造函数[_ | _]将parent的“单步”与递归步骤中的列表结合起来。这确实是在Prolog中编写这篇文章的首选方式。

这与另一个解决方案的行为相同：

?- ancestor_successor_lineage(grandma, daughter, Lineage).
Lineage = [grandma, mom, daughter] ;
false.

?- ancestor_successor_lineage(mom, son, Lineage).
false.