Define the following predicate into a prolog program so that
Minis the smaller of two numbersXandY.
min (X, Y, Min)
Can you help me understand the question?
2 Answers
In Prolog, we talk about predicates. In other languages you would probably call it a function, but in mathematics we are firm that a function associates a single value with the result of applying some formula to some other parameters to the function. That directionality does not hold in Prolog, so we call it a predicate or a relation.
The canonical solution to this problem is just this:
min(X, Y, Min) :- X =< Y, Min = X; Min = Y.
In Prolog, you always have a Horn clause, which has a head and a body. The head is what goes before the :- and names the predicate. The body is the list of expressions to the right of the :-. You should read this as "infer min(X, Y, Min) when X =< Y and Min = X, or else Min = Y". If the body of the clause is fulfilled, the head of the clause is inferred. In other words, if X =< Y and Min = X, then you could say min(X, Y, X) holds.
This says, essentially, if X =< Y, then Min is X; otherwise, Min is Y. It is probably more readably expressed with multiple clauses:
min(X, Y, X) :- X =< Y.
min(X, Y, Y) :- X > Y.
But this will create an unnecessary choice point; Prolog may think it has multiple solutions here even though you and I both know that X can only either be greater-or-equal to Y or less than Y. (We might inform Prolog of our awareness by using the cut operator, !, but it's overkill for this situation when you could just use conjunction and disjunction.)
Comments
This returns the min arguments of X&Y
min(X,Y,M):-
X<Y,!,M=X.
min(X,Y,M):-
M=Y.
4 Comments
Daniel Lyons
You have a singleton variable on your second clause, and I am vaguely concerned that the code is not entirely backwards-correct as a result.
amjad khatabi
Just saw your answer it's totally more elegant and has no singletons. I am at my learning phase of prolog I don't get what you mean by backwards-correct, I just debugged it and it works fine. [trace] 15 ?- min(1,5,M). Call: (7) min(1, 5, _G6208) ? creep Call: (8) 1<5 ? creep Exit: (8) 1<5 ? creep Call: (8) _G6208=1 ? creep Exit: (8) 1=1 ? creep Exit: (7) min(1, 5, 1) ? creep M = 1.
Daniel Lyons
It does appear to work, but I'm suspicious because the clause by itself is equivalent to
min(X,Y,Y) with no guard. Relying on the cut in another clause to supply correctness makes me shudder. Presumably @false can demonstrate a way to trip over backwards correctness; this is an area where I can now smell the problem but still can't reliably produce the effect of it. Essentially what it means is that if you hit something later in the query that causes you to reconsider a choice point, you could be backed into a clause unexpectedly.
G_V
So adding the conditions to the bottom question would work? Like min(X,Y,M):- Y<X, !, M=Y. That way the compiler could work through the predicate both ways and not evade checks.
min(X, Y, Min)which succeeds ifMinis the minimum of the valuesXandY(as stated in the question,Minis the smaller of the two numbersXandY).