How can I find the input from a list which yields the maximum result from some query in SWI-Prolog?

Question

I'm just picking up Prolog now, so I'm unfamiliar with the normal way of doing most things.

Essentially I have a rule which gives a value from an input:

ScoreFromInput(Input, Score) :- ...

And I have a list of inputs, which are just numbers. I'm having trouble figuring out how to find the input which yields the maximum score.

This is what I have right now, but I think it recurses infinitely:

bestInput(BestInput) :-
    %#Bind the list of valid inputs
    legalInputs(ValidInputs),
    %# -1000 is a dummy score, it should get replaced on the first call to bestInputHelper
    bestInputHelper(ValidInputs,-1000,BestInput).

%#I think this rule should work if the first input in the list is not the best one
bestInputHelper([Input|RestOfInputs],BestScore,BestInput):-
    bestInputHelper(RestOfInputs,RestBestScore,BestInput),
    ScoreFromInput(Input,BestScore),
    RestBestScore > BestScore.

%#And this one if it is the best input
bestInputHelper([Input|RestOfInputs],BestScore,Input):-
    bestInputHelper(RestOfInputs,RestBestScore,_RestBestInput),
    ScoreFromInput(Input,BestScore),
    RestBestScore =< BestScore.

This is what I have so far, but I imagine there is a much more straightforward way of doing it. Any help is appreciated! Thanks!

Answer 1

Despite Chris's lack of familiarity with Prolog, the approach he outlined may be a more efficient way of finding the input with the maximum score than mat's. Instead of doing a quadratic number of comparisons, an approach like Chris's is possible that linearly scans the possible inputs.

Here maxScoreOfList/3 will return the best item Z and the best score B for a list of valid inputs as the third argument. The predicate will fail on an empty list.

maxScoreOfList(Z,B,[H|T]) :-
    scoreFromInput(H,S),
    maxScoreOfListAux(Z,B,H,S,T).

A "helper" function is needed as follows, which illustrates the "trick" of adding some extra arguments so that when the end of the input list is reached, the outputs Z and B can be bound to the best item and score found "so far":

maxScoreOfListAux(Z,B,Z,B,[ ]).
maxScoreOfListAux(Z,B,X,S,[H|T]) :-
    scoreFromInput(H,Q),
    (   S >= Q
     -> ( Y = X, R = S )
     ;  ( Y = H, R = Q )
    ),
    maxScoreOfListAux(Z,B,Y,R,T).