In as far the Million Dollar question of Prolog is still open.
Problem is, because it belongs to the naish/2 family of
representations and because it uses (==)/2, it is extremly
slow. Try this performance test case:
hydra(0, _) :- !.
hydra(N, h(X,X)) :- M is N-1, hydra(M, X).
test(N) :- hydra(N,X), hydra(N,Y), compare(_, X, Y).
test2(N) :- hydra(N,X), hydra(N,Y), ft_compare(_, X, Y).
The SWI-Prolog implementation maintains time linearity
in the term size, since it uses Union Find:
/* compare/3 */
?- member(N,[5,10,15]), time(test(N)), fail; true.
% 12 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 22 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 32 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
true.
naish/2 family of representations simply explodes, not
to be recommended in practice:
/* ft_compare/3 */
?- member(N,[5,10,15]), time(test2(N)), fail; true.
% 832 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 36,874 inferences, 0.000 CPU in 0.004 seconds (0% CPU, Infinite Lips)
% 1,507,348 inferences, 0.125 CPU in 0.130 seconds (96% CPU, 12058784 Lips)
true.
Union Find as deployed by SWI-Prolog compare/3 can not only
detect loops but also sharing. Union Find algorithms were
introduced by Hopcroft and Karp in 1971 through this paper:
A Linear Algorithm for Testing Equivalence of Finite Automata
Hopcroft & Karp - 1971
https://ecommons.cornell.edu/server/api/core/bitstreams/47fc124d-2094-4f23-be59-d25fde0f9108/content
I guess it is actually possible to realize a compare/3 around the HK
technique, that is a total order for cyclic terms and that is conservative.
Through a modification of SWI-Prolog compare/3.