Prolog - Recursive call

Question

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

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...

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)

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

Answer 1

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.

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).

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).

to represent that.

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.

An application to your predicate

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

would become

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).

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

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

• when there is one team left

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

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

Resulting code is:

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).

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 :)