Abbott@AeroSpace@sri-unix.UUCP (09/17/83)
From: Abbott at AeroSpace ( Russ Abbott ) The recent discussion of transitive relations has drifted somewhat from the original question. I thought this might be a good time to raise it again. Does anyone know of a good way to write a predicate in Prolog that defines a relation to be the transitive closure of another relation. For example: transitive_closure(R, T_R). should have the side-effect of ensuring that if R(a, b) and R(b, c) are either in the database or ( important! ) are added to the database later, then T_R(X, Y) will succeed with (X, Y) being bound to (a, b), (b, c), and (a, c) in turn. One might imagine writing something like: transitive_closure(R, T_R) :- assert(( T_R(A, C) :- R(A, C); T_R(A, B), T_R(B, C) )). But that leads to various difficulties involving infinite recursion. So far, there are no clean solutions.
puder@burdvax.UUCP (09/26/83)
Here is how I define the transitive closure and avoid infinite loops, etc. % cprolog CProlog version 1.3 | ?- [user]. | | % The base relation. | r(a,b). | r(b,c). | r(b,d). | r(f,a). | r(e,a). | | % The transitive relation. | tr(X,Y):-r(X,Y). | % Note that the next clauses call r and tr, they do not call tr twice! | tr(X,Y):-nonvar(X),!,r(X,Z),tr(Z,Y). | tr(X,Y):-r(Z,Y),tr(X,Z). | | user consulted 484 bytes 0.2 sec. yes | ?- tr(A,B). A = a B = b ; A = b B = c ; A = b B = d ; A = f B = a ; A = e B = a ; A = f B = b ; A = e B = b ; A = a B = c ; A = f B = c ; A = e B = c ; A = a B = d ; A = f B = d ; A = e B = d ; no | ?- -- Karl Puder {sdcrdcf,presby,psuvax}!burdvax!puder (215)648-7555