Prolog - stop repeat when last fact

Question

I have a list of facts like this:

set(h, 3).
set(h, 6).
set(h, 12).
set(h, 1).
set(h, 7).

I need to find the maximum value of set h and the query needs to look like this:

?- maximum(h, Max).
Max = 12.

Now there are many ways to do this, obviously. But currently I'm looking for a way to do it with a dynamic predicate and also a fail predicate. I might have to use repeat I guess? Unfortunately both the repeat and dynamic predicate seem confusing to me.

I was thinking something like this:

set(h, 3).
set(h, 6).
set(h, 12).
set(h, 1).
set(h, 7).

:- dynamic current_max/1.

assert(current_max(0)).

maximum(Set, Element):-
    repeat,
    set(Set,Element),
    current_max(Max),
    (Max > Element,
        fail);
     (Element > Max,
     retract(current_max(Max)),
     assert(current_max(Element)),
     fail).

maximum(_, Max):-
    current_max(Max).

One of the issues I see myself is that the repeat cycle doesn't stop. If I would somehow know that it was the last element of the set I could probably use cut, but I'm not sure how.

score 3 · Accepted Answer · edited May 23 '17 at 12:30

A failure-driven loop looks like this:

(   Generator,
    Side_effect,
    fail
;   true
)

In your case set/2 is the generator, and updating the current maximum is the side effect. You shouldn't need repeat in this case: calling set/2 will generate the choice points. You need repeat when you have to create choice points without a generator.

Again, I have to say that this is a very strange question (and you have asked it before). If you want to do something like this, at least don't use a dynamic predicate to hold the current maximum: this is just begging for trouble.

In SWI-Prolog's library(aggregate) there are examples of doing this. Taking aggregate_all/3 as a starting point, and leaving only the code for finding the maximum of numbers, you have:

set(h, 3).
set(h, 6).
set(h, 12).
set(h, 1).
set(h, 7).

maximum(Set, Max) :-
        State = state(Max),
        (       set(Set, Max),
                arg(1, State, M0),
                M is max(M0, Max),
                nb_setarg(1, State, M),
                fail
        ;       arg(1, State, Max),
                nonvar(Max)
        ).

This uses a term to hold the current maximum, so the state you are keeping is local to the maximum/2 predicate. It also doesn't assume an initial value (if you start with 0, as you do, and all values happen to be negative, you will get an incorrect result!). With this definition:

?- maximum(h, M).
M = 12.

?- maximum(x, M).
false.

Few comments:

you need the nonvar(Max) at the very end for the case when the call to set/2 at the beginning of the disjunction fails. Note however that as it stands at the moment, you can still get wrong results:

?- maximum(x, 42).
true.

You should be able to figure out how to deal with this.

Currently, this uses the arithmetic function max to get the larger of two numbers. This will not work if you have anything else, say atoms (even though there is a defined total ordering for atoms). You can define a predicate that finds the maximum of any two terms:

term_max(X, Y, Max) :-
    (   X @> Y
    ->  Max = X
    ;   Max = Y
    ).

Then, you just replace

M is Max(M0, Max)

with:

term_max(M0, Max, M)

Man, I'm gonna be honest. This seems to be on another level with lots of things I have yet to learn (state, arg, nb_setarg, nonvar etc). Is there not a way to get it work with a dynamic predicate that keeps the max value? Or with a repeat. I'm trying to get a handle on those specifically. Also, what if I did want to get it to work with atoms? So it would go numbers first and then letters (a-z)? Would that be possible? — PadaKatel, Dec 01 '16 at 11:28
@PadaKatel You really don't need `repeat` here, because `set/2` will create the choice points. At the beginning of the answer I show how a failure-driven loop looks, and how to use it to solve your problem; the retract+assert you already have in your question is the "side effect". But please remember that doing it as you want is inherently broken, and should be used only for learning purposes! — , Dec 01 '16 at 15:34
Hey. I wrote another example of code to a different comment. — PadaKatel, Dec 05 '16 at 16:55

score 0 · Answer 2 · answered Dec 05 '16 at 16:55

Okay. I have been looking over this one for a few days now. I think I understand why we don't need repeat. I tried combining my (bad) method with some of your ideas.

This is what I came up with:

maximum(Set, Element):-
    ((set(Set,Element),
        current_max(Max),
        (Max > Element,
            fail);
         (Element > Max,
         retract(current_max(Max)),
         assert(current_max(Element)),
         fail))
     ;
     true
     ).

maximum(_, Max):-
    current_max(Max).)

Unfortunately right now it gives me "Arguments are not sufficiently instantiated".

Here's what I was thinking: set/2 generates thee values (Set can be given it, Element takes first value from facts). Then it takes a value from current_max/1 (is 0 at first). If max is bigger than it fails and goes to take another value from set. If Element is bigger than Max we remove previous current_max fact and create new. Then we also fail and go back. Once all values are gone through it returns true. And then I wish it would also go through the second rule to give out the Max answer.

score 0 · Answer 3 · answered Dec 14 '16 at 21:01

An inefficient, but perhaps didactically useful solution would be to use forall/2 to find the right value for you:

maximum(Set, Max) :-
  set(Set, Max),
  forall(set(Set, Other), 
           Max >= Other).

Prolog will (inefficiently) choose each element as a candidate Max until the forall/2 step is satisfied, so this is definitely a quadratic time solution at best, but it illustrates "Prolog thinking" better than failure-driven loops do, in my opinion.

repeat/0 is really a sort of low-level piece of machinery in Prolog. Most of the time you get better results by thinking logically about your problem and structuring your solution around that logic, rather than worrying up-front about how Prolog's resolution system is going to cook up the result. In the former approach, you still need to be aware of backtracking and how Prolog will retry things, but you work with it, rather than fighting it or trying to harness it directly.

Prolog - stop repeat when last fact

3 Answers3