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).因此,只要我们没有遇到基本情况(没有执行递归的情况),我们就不会明确地绑定变量(即我们总是让一部分术语解除绑定).

对于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没有得到在递归调用,我们不知道这件事呢,所以我们不能将其绑定,并在谓词了改变,因为Rest因此现在是独立的,只是表示还没有球队已被处理,因此对我们的结果列表的尾部感兴趣(和for 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 = [_, _|_],在子句的开头.

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