Prolog code error

Question

My code is supposed to output a schedule for a competetion the predicate scheduleround2 is used to generate a list of game(player1,player2,round). however there is an error most probably with the unification for Z.

here is the code:

sample input:

schedule_round([player(alex,2), player(jane,5), player(djokovich,1), player(nadal,3), player(anderson,4), player(jack,6), player(nilson,7), player(pete,8)], R).

and the output should be

R=[game(pete,djokovich,quarter_final), game(nilson,alex,quarter_final), game(jack,nadal,quarter_final), game(jack,jane,quarter_final)]

What actually happens is that is computes forever producing nothing

%gets the maximum player rating 
maxf([H|T], R) :- maximum(T, H, R).

maximum([], R, R).
maximum([player(X,Y)|T], player(_,R), F) :-
    Y > R,
    maximum(T, player(X,Y), F).
maximum([player(_,Y)|T], player(Z,R), F) :-
    R > Y,
    maximum(T, player(Z,R), F).

%gets the minimum player rating
minf([H|T], R) :- minimum(T, H, R).

minimum([], R, R).
minimum([player(X,Y)|T], player(_,R), F):-
    Y < R,
    minimum(T, player(X,Y), F).
minimum([player(_,Y)|T], player(Z,R), F):-
    R < Y,
    minimum(T, player(Z,R), F).

%removes players who are scheduled from the list
del(X, [X|L], L).
del(X, [A|L], [A|L1]) :- del(X, L, L1).

%gets size of the list
size([], 0).
size([_|T], N) :- size(T, M), N is M+1.

%scheduling predicate
schedule_round(X, R) :-
    size(X, N),
    schedule_round2(N, X, R).

%helper
schedule_round2(0, _, []).
schedule_round2(N, H, Z) :-
    N2 is N-2,
    maxf(H, F),
    minf(H, B),
    del(F, H, L),
    del(B, L, J),
    append(Z, game(F, B, quarter_final), K), 
    schedule_round2(N2, J, K).

You didn't say what the error actually is. And what predicate clause is the error pointing to? The error message will tell you what line(s) of code are implicated. — lurker
actually it is not an error message but when it keeps processing the predicate schedule_round2 forever — Ahmadposten
What query did you enter that resulted in the infinite loop? — lurker
You don't need the size predicate. ISO prolog has length/2 which gives you the length of a list: length(List, N). — lurker
Your del(X, [A|L], [A|L1]) :-... needs to check that X \== A. Otherwise prolog will backtrack to and succeed on that clause even if X and A are the same. And I assume you are querying with a list of an even number of elements, but just in case, schedule_round2(N, H, Z) :-... should first check, N > 1. — lurker

lurker lurker · Accepted Answer · 2014-03-22T13:44:50

There are a couple of problems with the definition of schedule_round.

The termination case schedule_round(0, _, []). fails because the third argument in the recursive calls to schedule_round is always a non-empty list. Also, I the original append/3 statement you have is indeed an issue. It will always fail after the first time around since your second argument isn't a list and should be [game(F, B, quarter_final)] rather than just game(F, B, quarter_final). When append fails, the schedule_round code backtracks through the other predicate queries, comes up with another possible solution and fails append again... infinitely. In addition, what's being appended to what is flipped around. We want the recursive call to schedule_round2 to be the tail of the solution for any given call, so the new element prepends to the tail giving the new solution in the current call.

So the "quick fix" would be to just change schedule_round2 recursive clause to:

schedule_round2(N, H, Z) :-
    N2 is N-2,
    maxf(H, F),
    minf(H, B),
    del(F, H, L),
    del(B, L, J),
    append([game(F, B, quarter_final)], K, Z),
    schedule_round2(N2, J, K).

This will work, but it turns out you don't need the append/3 since append([X], In, Out) is the same as Out = [X|List]. We can reduce this to:

%helper
schedule_round2(0, _, []).
schedule_round2(N, H, [game(F,B,quater_final)|Z]) :-
    N > 1,              % This ensures N2 won't go negative due to bad input
    N2 is N-2,
    maxf(H, F),
    minf(H, B),
    del(F, H, L),
    del(B, L, J),
    schedule_round2(N2, J, Z).  % Schedule round for rest of the list

This version will recurse with the third argument (the tail of the solution) to schedule_round2 uninstantiated until it hits the base clause. At that point, the third argument (solution tail) will instantiate to [] and rewind your solution to the desired result on the recursive returns.

Here are a few other optional suggested changes:

(1) Your minimum and maximum assume that the values compared are never equal. Perhaps this is the case. But you might consider:

maximum([player(_,Y)|T], player(Z,R), F) :-
    R >= Y,
    ...

and

minimum([player(_,Y)|T], player(Z,R), F):-
    R =< Y,
    ...

(2) In schedule_round2/3 I added the check for N > 1. It's not necessary if you always give it an even-parity list (which is what's expected) but if you did give it an odd-parity list, it will cause the predicate to fail gracefully rather than recurse on negative N for a very long time.

(3) Your size/2 predicate is unnecessary since Prolog already provides a list length predicate, length/2.

Prolog code error

1 Answers