How could we speed it up any further. Well
we can make at least the following observation.
Let A and B be two lists of truncation pairs.
Capital greek letters denote sublists:
A = Γ, P, Δ, P, Π
B = Γ, P, Δ, Π
Then mercio2_iter(A) gives the same comparison
like the shorter mercio2_iter(B). The truncation
leafs obey a contraction law. So if we find methods
to get smaller pair lists, then I guess
we will also get faster Mercio’s Algorithm
implementation. Possible methods to contract the
pair list are at least either Naive HK based
on same_term/2 or Non-Naive HK based on same_term/2:
Hopcroft and Karp’s algorithm (HK)
https://inria.hal.science/hal-00639716v2
But there is a twist, which stuns me, how to
make contraction between levels? Is such an inter
level optimization even somehow defined? It seems
levels are still copied during expansion?
Mild Shock schrieb:
The good thing is we have at least Mercio’s
Algorithm. This can be used for Total Order Sorting
of Prolog terms, cyclic and acyclic. But how speed
it up? Here is a take. The idea is sketched as follows:
Sketch to determine (<) or (>):
1. Use a list of pairs. These are the leafs of
a truncation.
2. Compare this list, if the result
differs from (=) you are done.
3. Expand the list of pairs to get a new level,
and continue with step 1.
The Prolog code reads as follows:
Step 1:
compare_truncs(C, []) :- !, C = (=).
compare_truncs(C, [X-Y|_]) :-
trunc(X, A),
trunc(Y, B),
compare(D, A, B),
D \== (=), !, C = D.
compare_truncs(C, [_|L]) :-
compare_truncs(C, L).
trunc(X, A) :- var(X), !, A = X.
trunc(X, F/N) :- functor(X, F, N).
Step 2:
next_truncs([], []).
next_truncs([X-_|L], R) :- var(X), !,
next_truncs(L, R).
next_truncs([X-Y|L], R) :-
next_truncs(L, H),
X =.. [_|A],
Y =.. [_|B],
zip(A, B, J),
append(J, H, R).
zip([], [], []).
zip([X|L], [Y|R], [X-Y|H]) :-
zip(L, R, H).
Step 3:
mercio2(C, X, Y) :- X == Y, !, C = (=).
mercio2(C, X, Y) :- mercio2_iter(C, [X-Y]).
mercio2_iter(C, L) :-
compare_truncs(D, L),
D \== (=), !, C = D.
mercio2_iter(C, L) :-
next_truncs(L, R),
mercio2_iter(C, R).
The new mercio2/3 is an itch faster than the old mercio/3:
?- X = s(s(X, 1), 0), Y = s(X, 1),
Z = s(s(1, s(Z, 1)), 1),
time((between(1,10000,_), mercio(C, X, Z),
mercio(D, Z, Y), fail; true)).
% Zeit 184 ms, GC 0 ms, Lips 11141728, Uhr 06.08.2025 07:39
?- X = s(s(X, 1), 0), Y = s(X, 1),
Z = s(s(1, s(Z, 1)), 1),
time((between(1,10000,_), mercio2(C, X, Z),
mercio2(D, Z, Y), fail; true)).
% Zeit 145 ms, GC 0 ms, Lips 9379848, Uhr 06.08.2025 07:39
Mild Shock schrieb:
Now question is whether compare_rat/2 can
be extended to a total order or not. On
the positive side we find that a partial
order can always be extended:
Szpilrajn Extension Theorem https://en.wikipedia.org/wiki/Szpilrajn_extension_theorem
But what if compare_rat/2 by @kuniaki.mukai
is not a partial order? What if it is only a
preorder, or even worse only a binary relation.
Returning 4 values doesn’t guarantee that it
is a partial order. We have help from here:
Szpilrajn, Arrow and Suzumura https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-999X.2011.04130.x
A binary relation needs to be Suzumura
consistent, so that it can be extended
into a total order. And compare_rat/2 is
not Suzumura consistent, as the following
cycle a < c < b < a shows:
/* Not SWI, Windows Console is SNAFU */
?- repeat, fuzzy(A), fuzzy(C),
compare_rat(_X, A, C), _X = (<),
fuzzy(B), compare_rat(_Y, C, B), _Y = (<),
compare_rat(_Z, B, A), _Z = (<).
A = s(s(A, A), 1), _A = s(_A, s(_, 1)), C = s(_A, _),
_B = s(1, _B), B = s(B, s(1, _B))
Was only testing with compare_rat/3, but
the theorem applies also to other compare
proposals, and can be used to exclude
them, as soon as a Suzumura inconsistency is found.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)