Prolog-递归调用 [英] Prolog - Recursive call

问题描述

我在递归搜索列表和从结果中创建列表列表时遇到了麻烦.

I am having trouble with recursive searching of list and creation of list of lists from the result..

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

The knowledge base contains team name, number of wins and zone they are in, all associated withe their team number. I am passing list of team numbers in Teams and I am searching for a matching pair with findMinMax/3. The result I need is...

配对队名单列表(例如X = [[gonzaga, washington], [iowa, oklahoma], …]) 还有1个无与伦比的团队(由奇数个团队得出)或0(如果是偶数)

List of lists of paired teams (ex. X = [[gonzaga, washington], [iowa, oklahoma], …]) And 1 unmatched team (resulted from odd number of teams) or 0 (in case of even)

我弄清楚了其他所有内容，可以解决[gonzaga, washington]部分，但是递归部分失败了.

I figured out everything else and can get up to the part [gonzaga, washington], but failing at recursive portion...

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,[]).

推荐答案

一般的递归方案

在这里，我将向您展示我们通常如何在Prolog中执行递归.对于初学者来说，获得该列表并不容易，因为列表是向后"构建的:直到我们到达列表的末尾，才真正构建出一个真正的列表.

A general recursive scheme

Here I'll try to show you how we usually perform recursion in Prolog. It's not simple to get for beginners because the lists are built "backwards": nothing gets really built until we hit the end of the list.

之所以采用向后构建"的原则，是因为一旦设置了变量，就不能将其设置为另一个值，例如，很难说结果的第一个是[1]递归的步骤，然后变为[1, 2].取而代之的是，我们在Prolog中说的是结果标头是1，而结果标尾是递归调用的结果(是的，如果它弄乱了，请读两次:d).因此，只要我们不使用基本情况(不执行递归的情况)，我们就不会明确绑定变量(即，我们总是让术语的一部分不受约束).

The reason for this "build backwards" principle is that once a variable is set, you can't set it to another value, so for example it'd be hard to say that the result is [1] at the first step of the recursion and then becomes [1, 2]. Instead, what we say in Prolog is that the result head is 1 and that the result tail is the result of the recursive call (yeah read it twice if it got messy : d). So as long as we do not hit a base case (a case where no recursion is performed), we don't bind variables definitely (ie we always let a part of the term unbound).

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

For a predicate rec/2: rec(Input, Result) producing a result list from an input list by linking their elements with somepredicate/2, we'd write:

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

代表这一点.

在这里您可以看到我们说结果的开头是ResultHead，而其尾部是通过调用rec(InputTail, ResultTail).

Here you can see that we stated that the head of the result is ResultHead and that its tail is calculated thanks to the call rec(InputTail, ResultTail).

现在很好，但是我们需要在列表为空的情况下停下来.我们将其编写如下:

Now that's fine but we need to stop at some point, when the list is empty, for example. We'd write that as follows:

rec([], []).

表示:当输入列表为空时，结果列表也为空.

which means: when the input list is empty, so is the result list.

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

Now, to fix your problem, you first have to fix the recursive clause:

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现在是独立的，只是代表尚未处理的团队，因此对于我们的结果列表的末尾(以及LeftOver)感兴趣.

Important to note: now Rest has become two separate variables. The last argument of findPair/3 doesn't get changed anymore, since in the recursive call we do not know anything about it yet, so we can't bind it, and the in-predicate Rest is therefore now independant and just represents the teams that have not been handled yet and are therefore of interest for the tail of our result list (and for LeftOver).

现在我们要处理基本情况:

Now we have to handle the base cases:

• 没有队伍了

• when there are no teams left

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

这里我们说当Teams为空时，Result和LeftOver也是如此.

Here we say that when Teams is empty, so are the Result and LeftOver.

只剩一支队伍了

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

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

Here we say that when Teams has only one element, LeftOver is equal to Teams and Result is empty.

结果代码为:

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 = [_, _|_],

To make your clauses exclusive you could replace Teams with [Not, Empty|AtAll] to ensure the last clause is used only with lists of length 2 or more, or just add a guard such as Teams = [_, _|_], at the start of the clause.

希望它有所帮助，请毫不犹豫地在评论中进行澄清:)

Hope it helped and do not hesitate to ask for clarifications in comments :)

这篇关于Prolog-递归调用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！