时间戳

首页 > 解决方案 > Prolog递归累加器

recursion - Prolog递归累加器

问题描述

我正在尝试为大学课程建立知识库。具体来说，现在我正在尝试制作一个累加器，它将学习一门课程并提供必须首先学习的所有课程的列表，即课程的先决条件，这些先决条件的先决条件等......基于此图表。

这是谓词的示例：

prereq(cst250, cst126).
prereq(cst223, cst126).
prereq(cst126, cst116).
prereq(cst105, cst102).
prereq(cst250, cst130).
prereq(cst131, cst130).
prereq(cst130, cst162).
prereq(anth452, wri122).
prereq(hist452, wri122).

这是我对累加器的尝试：

prereq_chain(Course, PrereqChain):-
    %Get the list of prereqs for Course
    findall(Prereq, prereq(Course, Prereq), Prereqs),

    %Recursive call to all prereqs in X
    forall(member(X, Prereqs),
           (prereq_chain(X, Y),    
            %Combine current layer prereqs with deeper
            append(Prereqs, Y, Z))),

    %Return PrereqChain
    PrereqChain = Z.

查询的所需输出将是：

?- prereq_chain(cst250, PrereqList).
PrereqList = [cst116, cst126, cst162, cst130]

相反，我得到了一个真实的答案，以及一个关于 Z 是单身人士的警告。

我看过其他关于类似问题的帖子，但它们都有一条反向遍历的通道，而我的解决方案需要多个通道。

提前感谢您的任何指导。

标签： recursionprologaccumulator

解决方案

using 的问题forall/2是它没有建立绑定。看看这个人为的例子：

?- forall(member(X, [1,2,3]), append(['hi'], X, R)).
true.

如果 为 X 或 R 建立了绑定forall/2，它将出现在结果中；相反，我们只是得到了true，因为它成功了。因此，您需要使用一个不仅运行一些计算而且会产生值的构造。在这种情况下，您想要的是maplist/3，它接受一个目标和一个参数列表并构建一个更大的目标，然后将结果返回给您。输入下面的解决方案后，您将能够在控制台中看到效果。

?- maplist(prereq_chain, [cst126, cst130], X).
X = [[cst116], [cst162]].

所以这得到了列表中两个类的先决条件列表，但给了我们一个列表列表。这是append/2派上用场的地方，因为它本质上是扁平化列表列表：

?- append([[cst116], [cst162]], X).
X = [cst116, cst162].

这是我想出的解决方案：

prereq_chain(Class, Prereqs) :-
    findall(Prereq, prereq(Class, Prereq), TopPrereqs),
    maplist(prereq_chain, TopPrereqs, MorePrereqs),
    append([TopPrereqs|MorePrereqs], Prereqs).

推荐阅读