But the above is difficult to understand, since compare/3
is a black box. Nobody looks at the C source code.
But we can make compare/3 also a white box:
?- member(N,[5,10,15]), time(testx6(N)), fail; true.
% 426 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 1,301 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 2,626 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
true.
The test case was:
order_compare(C, X, Y) :-
deutsch(X, A),
deutsch(Y, B),
order(C, A, B).
testx6(N) :- hydrax(N,Z,X), hydrax(N,Z,Y), order_compare(_, X, Y).
And this is the Union Find algorithm, from Hopcroft and Karp (1971)
as used in various places inside SWI-Prolog, using additional memory
pointers in the functor. Here done in 100% Prolog using same_term/2:
order(C, X, Y) :-
sys_order(X, Y, C, [], _).
sys_order(X, Y, C, L, R) :- compound(X), compound(Y), !,
sys_union_find(X, L, Z),
sys_union_find(Y, L, T),
(same_term(Z, T) ->
C = (=), L = R;
functor(Z, F, N), functor(T, G, M),
compare(D, N/F, M/G), D \== (=) ->
C = D, L = R;
Z =.. [_|P], T =.. [_|Q],
sys_order_list(P, Q, C, [Z-T|L], R)).
sys_order(X, Y, C, L, L) :- compare(C, X, Y).
sys_order_list([], [], =, L, L).
sys_order_list([X|P], [Y|Q], C, L, R) :-
sys_order(X, Y, D, L, H),
(D \== (=) -> C = D, H = R;
sys_order_list(P, Q, C, H, R)).
sys_union_find(X, L, T) :-
member(Y-Z, L),
same_term(X, Y), !,
sys_union_find(Z, L, T).
sys_union_find(X, _, X).