prolog

How to write a transitive predicate?


gt(ace,ten).
gt(ten,king).
gt(king,queen).
gt(queen,jack).

gt_(X,Y) :- 
    ( gt(X,Z1), gt(Z1,Z2), gt(Z2,Z3), gt(Z3,Y) ) ;
    ( gt(X,Z1), gt(Z1,Z2), gt(Z2,Y) ) ;
    ( gt(X,Z1), gt(Z1,Y) ) ;
    gt(X,Y) 
    .

gt means "greater than" and should be transitive. that means for example gt_(ace, jack) should yield true.

The above explicit implementation works but it is obviously unsatisfying to have all possible transitive indirection written out.

What would be a better more succinct way to write gt_?


Solution

  • Your previous code was in the right direction except you would use a fact for the direct relations and the rule with different name for the recursive step:

    gt(ace,ten).
    gt(ten,king).
    gt(king,queen).
    gt(queen,jack).
    
    gt_(X,Y) :- ( gt(X,Z1), gt_(Z1,Y) ) ; gt(X,Y) .
    

    sample run:

    ?- gt_(X,Y).
    X = ace,
    Y = jack ;
    X = ace,
    Y = queen ;
    X = ace,
    Y = king ;
    X = ten,
    Y = jack ;
    X = ten,
    Y = queen ;
    X = king,
    Y = jack ;
    X = ace,
    Y = ten ;
    X = ten,
    Y = king ;
    X = king,
    Y = queen ;
    X = queen,
    Y = jack.
    
    ?- gt_(ten,ace).
    false.