Search code examples
recursionprologterminate

Prolog iteration/recursion to drill down to lowest value

I'm trying to create a predicate in prolog which will hold true if it reaches the lowest numerical value out of a set of values.

For example:
I have something like this at the moment

Base Step 

lowest(Object, Value) :- \+ lessThan(Object, Value, NewValue).

Recursive Step 

lowest(Object, Value) :- lessThan(Object, Value, NewValue), lowest(Object, NewValue).

Where Object is some abstract object which can have multiple numerical values attached to it.
lessThan returns Values (NewValue) for the Object which are less than the input Value.

And since NewValue will be lower than the input of Value I can assume that with each recursive step Value will be decreasing.

I have abstracted this problem from another which I am trying to solve, but basically what is happening is that I expect only 2 outputs from the whole recursive function, but instead I am getting as many outputs as lessThan(Object, Initial, X) + 2.

I'm not sure if this question is clear, please let me know so I can clarify.

I believe that my base step is correct, since I am making the assumption that if Value is the lowest coupled with Object, then there are no other values less than Value.

I am unsure where to terminate the recursion also, which is adding to my confusion. My guess is that it will terminate once it reaches a state where there are no lower Values for Object.

Solution

  • This sample should work, renaming value/2 as appropriate for your domain.

    value(a, 10).
value(a, 3).
value(a, 100).

lowest(Object, L) :-
    value(Object, First), !, lowest(Object, First, L).
lowest(Object, LowestSoFar, Lowest) :-
    value(Object, Try), Try < LowestSoFar, !,
    lowest(Object, Try, Lowest).
lowest(_, Lowest, Lowest).

    it yields

    ?- lowest(a,X).
X = 3.

    Note that it repeats the value 'peek' each time, then is not efficient. A possible alternative is storing the lower value and run a failure driven loop. Otherwise, SWI-Prolog (and YAP) has library(aggregate): 

    ?- aggregate(min(V), value(a,V), M).
M = 3.