list - Prolog - 递归调用

Question

我在递归搜索列表和根据结果创建列表列表时遇到问题..

知识库包含球队名称、获胜次数和他们所在的区域，所有这些都与他们的球队编号相关联。我正在传递 Teams 中的团队编号列表，并且正在使用 findMinMax/3 搜索匹配对。我需要的结果是...

配对团队列表列表(例如 X = [[gonzaga, washington], [iowa, oklahoma], …])和 1 个不匹配的团队(由奇数个团队产生)或 0 个(在偶数的情况下)

我想通了其他一切，并且可以达到 [gonzaga, washington] 部分，但在递归部分失败...

findPair(Teams,[HL|TL],Rest) :-
    findMinMax(Teams,Min,Max),
    delete(Teams,Min,TeamsNoMin),
    delete(TeamsNoMin,Max,Rest),
    createPair(Min,Max,Pair), %Pair = "["Min_team","Max_team"]"
    append(HL,[Pair],TL),
    findPair(Rest,TL,[]).

Answer 1

一个通用的递归方案

在这里，我将尝试向您展示我们通常如何在 Prolog 中执行递归。这对初学者来说并不容易，因为列表是“反向”构建的:在我们到达列表末尾之前，什么都没有真正构建。

这个“向后构建”原则的原因是，一旦设置了一个变量，就不能将它设置为另一个值，所以例如很难说结果是 [1] 在递归的第一步，然后变成 [1, 2]。相反，我们在 Prolog 中说的是结果头是 1，结果尾是递归调用的结果(是的，如果它变得困惑，请读两遍:d)。因此，只要我们不遇到基本情况(不执行递归的情况)，我们就不会明确绑定(bind)变量(即我们总是让部分术语未绑定(bind))。

对于谓词 rec/2: rec(Input, Result) 通过将输入列表的元素与 somepredicate/2 链接起来从输入列表中生成结果列表，我们将写:

rec([InputHead|InputTail], [ResultHead|ResultTail]) :-
    somepredicate(InputHead, ResultHead),
    rec(InputTail, ResultTail).

代表那个。

在这里您可以看到我们声明结果的头部是 ResultHead 并且它的尾部是通过调用 rec(InputTail, ResultTail) 计算的。

现在很好，但我们需要在某个时刻停止，例如，当列表为空时。我们会这样写:

rec([], []).

这意味着:当输入列表为空时，结果列表也是空的。

对你的谓词的应用

现在，要解决您的问题，您首先必须修复递归子句:

findPair(Teams,[HL|TL],Rest) :-
    findMinMax(Teams,Min,Max),
    delete(Teams,Min,TeamsNoMin),
    delete(TeamsNoMin,Max,Rest),
    createPair(Min,Max,Pair), %Pair = "["Min_team","Max_team"]"
    append(HL,[Pair],TL),
    findPair(Rest,TL,[]).

会变成

findPair(Teams, [Pair|Tail], LeftOver) :-
    findMinMax(Teams, Min, Max),
    delete(Teams, Min, TeamsNoMin),
    delete(TeamsNoMin, Max, Rest),
    createPair(Min, Max, Pair), %Pair = "["Min_team","Max_team"]"
    findPair(Rest, Tail, LeftOver).

需要注意的重要一点:现在 Rest 已经变成了两个独立的变量。 findPair/3 的最后一个参数不再改变，因为在递归调用中我们还不知道任何关于它的信息，所以我们不能绑定(bind)它，并且 in-predicate Rest 因此现在是独立的，只代表尚未处理的团队，因此对我们结果列表的尾部(以及 LeftOver)感兴趣。

现在我们必须处理基本情况:

• 没有队伍时

  findPair([], [], []).
  

  这里我们说当 Teams 为空时，Result 和 LeftOver 也为空。

• 当只剩下一个团队时

  findPair([Last], [], [Last]).
  

  这里我们说当Teams只有一个元素时，LeftOver等于Teams，Result是空。

结果代码是:

findPair([], [], []).
findPair([Last], [], [Last]).
findPair(Teams, [Pair|Tail], LeftOver) :-
    findMinMax(Teams, Min, Max),
    delete(Teams, Min, TeamsNoMin),
    delete(TeamsNoMin, Max, Rest),
    createPair(Min, Max, Pair), %Pair = "["Min_team","Max_team"]"
    findPair(Rest, Tail, LeftOver).

要使您的子句具有排他性，您可以将 Teams 替换为 [Not, Empty|AtAll] 以确保最后一个子句仅用于长度为 2 或更长的列表，或者只是在子句的开头添加一个守卫，例如 Teams = [_, _|_],。

希望它有所帮助，不要犹豫，在评论中要求澄清:)