functionprologforall

Prolog: Check if list of tuples is a function


I want to check, if a list L of tuples (x1,y1) has the function property:

āˆ€(x1,y1),(x2,y2) āˆˆ L (x1=x2 šŸ ’ y1 = y2)

I tried to solve it with the following predicate:

m_Function(L) :-
    ((member(M1, L), member(M2, L), 
    M1 = (X1, Y1), M2 = (X2, Y2), X1 = X2) 
    -> Y1 = Y2).

the problem of that is, that e.g. the input

L = [(p, q),  (p, r)]

results in true.

The trace of my debug shows me I more exactly realised the statement:

āˆƒ(x1,y1),(x2,y2) āˆˆ L (x1=x2 šŸ ’ y1 = y2)

trace:

 T Call: (8) m_Function([(p, q),  (p, r)])
   Call: (8) m_Function([(p, q),  (p, r)]) ? creep
   Call: (9) lists:member(_5074, [(p, q),  (p, r)]) ? creep
   Exit: (9) lists:member((p, q), [(p, q),  (p, r)]) ? creep
   Call: (9) lists:member(_5074, [(p, q),  (p, r)]) ? creep
   Exit: (9) lists:member((p, q), [(p, q),  (p, r)]) ? creep
   Call: (9) (p, q)=(_5060, _5062) ? creep
   Exit: (9) (p, q)=(p, q) ? creep
   Call: (9) (p, q)=(_5066, _5068) ? creep
   Exit: (9) (p, q)=(p, q) ? creep
   Call: (9) p=p ? creep
   Exit: (9) p=p ? creep
   Call: (9) q=q ? creep
   Exit: (9) q=q ? creep
 T Exit: (8) m_Function([(p, q),  (p, r)])
   Exit: (8) m_Function([(p, q),  (p, r)]) ? creep

Is their in prolog some elegant way e.g. with some "for all"-quantifier which I can use to solve this kind of problem?


Solution

  • You can use forall/2.

    m_Function(L) :-
        forall((member((X, Y1), L), member((X, Y2), L)), Y1 == Y2).
    

    forall(Condition, Action) succeeds if for all alternative bindings of Condition, Action can be proven. It is equivalent to \+(Condition, \+ Action).