4 ms·
For whatever it's worth, here's how you would actually implement the reflexive-transitive closure of a relation in Prolog: subtype(gerbil, rodent). sub
by tom_mellior 7y ago
For whatever it's worth, here's how you would actually implement the reflexive-transitive closure of a relation in Prolog:
subtype(gerbil, rodent).
subtype(rodent, mammal).
subtype(mammal, animal).
transitive_subtype(S, T) :-
subtype(S, T).
transitive_subtype(S, T) :-
subtype(S, U),
transitive_subtype(U, T).
reflexive_transitive_subtype(T, T). % FIXME: should check if T is a type
reflexive_transitive_subtype(S, T) :-
transitive_subtype(S, T).
This terminates as expected:
?- transitive_subtype(gerbil, X).
X = rodent ;
X = mammal ;
X = animal ;
false. % meaning "I have proved that there are no further solutions"
?- reflexive_transitive_subtype(gerbil, X).
X = gerbil ;
X = rodent ;
X = mammal ;
X = animal ;
false.
or even:
?- reflexive_transitive_subtype(S, T).
S = T ;
S = gerbil,
T = rodent ;
S = rodent,
T = mammal ;
S = mammal,
T = animal ;
S = gerbil,
T = mammal ;
S = gerbil,
T = animal ;
S = rodent,
T = animal ;
false.
Left recursion can indeed be a problem in Prolog, but this is not a problematic case.