Mercio’s Algorithm (2012) for Rational
Tree Compare is specified here mathematically.
It is based on computing truncations A' = (A_0,
A_1, etc..) of a rational tree A:

A < B ⟺ A′ <_lex B′

https://math.stackexchange.com/a/210730

Here is an implementation in Prolog.
First the truncation:

trunc(_, T, T) :- var(T), !.
trunc(0, T, F) :- !, functor(T, F, _).
trunc(N, T, S) :-
M is N-1,
T =.. [F|L],
maplist(trunc(M), L, R),
S =.. [F|R].

And then the iterative deepening:

mercio(N, X, Y, C) :-
trunc(N, X, A),
trunc(N, Y, B),
compare(D, A, B),
D \== (=), !, C = D.
mercio(N, X, Y, C) :-
M is N + 1,
mercio(M, X, Y, C).

The main entry first uses (==)/2 for a
terminating equality check and if the
rational trees are not equal, falls back
to the iterative deepening:

mercio(C, X, Y) :- X == Y, !, C = (=).
mercio(C, X, Y) :- mercio(0, X, Y, C).

I couldn’t find yet a triple that violates
transitivity. But I am also not much happy
with the code. Looks a little bit expensive
to create a truncation copy iteratively.

Provided there is really no counter example,
maybe we can do mit more smart and faster? It
might also stand the test of conservativity?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

Mild Shock schrieb:

Mercio’s Algorithm (2012) for Rational
Tree Compare is specified here mathematically.
It is based on computing truncations A' = (A_0,
A_1, etc..) of a rational tree A:

A < B ⟺ A′ <_lex B′

https://math.stackexchange.com/a/210730

Here is an implementation in Prolog.
First the truncation:

trunc(_, T, T) :- var(T), !.
trunc(0, T, F) :- !, functor(T, F, _).
trunc(N, T, S) :-
   M is N-1,
   T =.. [F|L],
   maplist(trunc(M), L, R),
   S =.. [F|R].

And then the iterative deepening:

mercio(N, X, Y, C) :-
   trunc(N, X, A),
   trunc(N, Y, B),
   compare(D, A, B),
   D \== (=), !, C = D.
mercio(N, X, Y, C) :-
   M is N + 1,
   mercio(M, X, Y, C).

The main entry first uses (==)/2 for a
terminating equality check and if the
rational trees are not equal, falls back
to the iterative deepening:

mercio(C, X, Y) :- X == Y, !, C = (=).
mercio(C, X, Y) :- mercio(0, X, Y, C).

I couldn’t find yet a triple that violates
transitivity. But I am also not much happy
with the code. Looks a little bit expensive
to create a truncation copy iteratively.

Provided there is really no counter example,
maybe we can do mit more smart and faster? It
might also stand the test of conservativity?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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)

You have the habit to post incomplete code:

bfs_sort(X, Y):- minimum_coa(X, Is, Mcoa),

My friend, where did you hide the predicate
minimum_coa/3 ? Also its irrelevant to mercio/3
or any frontier method. The TRUNCATIONS are
the same either with

or without a canonical form as input. The
only thing that might be a little faster is
the (==)/2 pretest in mercio/3, and short cuts
like here profit also:

fpl_compare(C, [I-J|F], FPL, FPL0, Mcoa):-
( I = J -> fpl_compare(C, F, FPL, FPL0, Mcoa)

But practically one could also use same_term/2
and gain some speed. But given that minimum_coa/3
can be quite expensive, I don’t count this as the

real mercio/3 sorting method. If sorting is O(N * log(N))
for a fast compare but minimum_coa/3 is O(N^2),
not much is gained, rather contra productive.

Thats basically why bisimiliarity was invented
by Hopcroft and Carp and reported in their 1971
paper to avoid the trap of doing equality via
expensive canonical form.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Mercios decidability was already attested in 2012,
you find it in the original SE post. But it could
be that the two persons that didn't understand the

SE post, are @jp-diegidio and mercio. Especially since
decidability was explicitly asked in the SE post back then,

- Is it decidable for rational trees?
user4414, October 12, 2012

The question was asked by myself back in 2012, I
am also the author of the original SE post question.
Nevertheless the contrarian @jp-diegidio suddently
claims semi-decidabilty! So I have doubts that

mercio didn't understand his SE post,
since he correctly states:

- If two trees are distincts then there is a level
that distinguishes them, and so you don't need to
look infinitely far down the tree to decide how
they are ordered. You just need to check level
after level until you find the difference. So it
boils down to deciding equality among rational trees
mercio, October 12, 2012

Do you @jp-diegidio have a pair `X` and `Y` where
this here in SWI-Prolog does not properly terminate,
making the comment by mercio ultimately useless for
the implementation of `mercio/3` ?

?- X == Y.
%%% hangs or aborts ?

Here is `mercio/3` again, it uses (==)/2, and shows
decidability of a total order on rational trees,
although the order is not a natural order. I placed
comments into the code, so that the

gifted computer scientists and the blessed
mathematicians likewise understand what is going on
in Mercio's as described on the SE post. You see the
yellow highlight passages now placed into

the beautiful Prolog code:

/* equality among rational trees */
mercio(C, X, Y) :- X == Y, !,
/* boils down */
C = (=).

/* if two trees are distinct */
mercio(C, X, Y) :-
/* level that distinguishes them */
mercio(0, X, Y, C).

Mild Shock schrieb:

Mercio’s Algorithm (2012) for Rational
Tree Compare is specified here mathematically.
It is based on computing truncations A' = (A_0,
A_1, etc..) of a rational tree A:

A < B ⟺ A′ <_lex B′

https://math.stackexchange.com/a/210730

Here is an implementation in Prolog.
First the truncation:

trunc(_, T, T) :- var(T), !.
trunc(0, T, F) :- !, functor(T, F, _).
trunc(N, T, S) :-
   M is N-1,
   T =.. [F|L],
   maplist(trunc(M), L, R),
   S =.. [F|R].

And then the iterative deepening:

mercio(N, X, Y, C) :-
   trunc(N, X, A),
   trunc(N, Y, B),
   compare(D, A, B),
   D \== (=), !, C = D.
mercio(N, X, Y, C) :-
   M is N + 1,
   mercio(M, X, Y, C).

The main entry first uses (==)/2 for a
terminating equality check and if the
rational trees are not equal, falls back
to the iterative deepening:

mercio(C, X, Y) :- X == Y, !, C = (=).
mercio(C, X, Y) :- mercio(0, X, Y, C).

I couldn’t find yet a triple that violates
transitivity. But I am also not much happy
with the code. Looks a little bit expensive
to create a truncation copy iteratively.

Provided there is really no counter example,
maybe we can do mit more smart and faster? It
might also stand the test of conservativity?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

You can use Fuzzy Testing also for
benchmarking. Not only to find faults.
For example when I benchmark mercio/3 via
fuzzy/1, I find it doesn’t fare extremly bad:

?- time((between(1,100,_), mercio, fail; true)).
% 4,386,933 inferences, 0.375 CPU in 0.376 seconds (100% CPU, 11698488 Lips) true.

And I am not using some of the optimization
that @kuniaki.mukai posted elsewhere and that
I posted 06.08.2025 on comp.lang.prolog. Fact is,
it only ca. 20% slower than SWI-Prologs compare/3:

?- time((between(1,100,_), swi, fail; true)).
% 3,786,880 inferences, 0.312 CPU in 0.325 seconds (96% CPU, 12118016 Lips) true.

The test harness was:

swi :-
between(1,1000,_),
fuzzy(X), fuzzy(Y),
swi(_, X, Y), fail; true.

mercio :-
between(1,1000,_),
fuzzy(X), fuzzy(Y),
mercio(_, X, Y), fail; true.

The difficulty was to find a 100% Prolog compare/3
that corresponds to SWI-Prolog. But you find a
fresh implementation in 100% Prolog using a Union
Find structure in the below:

% swi(-Atom, +Term, +Term)
swi(C, X, Y) :-
swi(X, Y, C, [], _).

% swi( -Atom, +Term, +Term,+List, -List)
swi(C, X, Y, L, R) :- compound(X), compound(Y), !,
sys_union_find(X, L, Z),
sys_union_find(Y, L, T),
swi_found(C, Z, T, L, R).
swi(X, Y, C, L, L) :- compare(C, X, Y).

% swi_found(-Atom, +Term, +Term, +List, -List)
swi_found(C, X, Y, L, L) :-
same_term(X, Y), !, C = (=).
swi_found(C, X, Y, _, _) :-
functor(X, F, N),
functor(Y, G, M),
compare(D, N/F, M/G),
D \== (=), !, C = D.
swi_found(C, X, Y, L, R) :-
X =.. [_|P],
Y =.. [_|Q],
foldl(swi(C), P, Q, [X-Y|L], R).

% sys_union_find(+Term, +List, -Term)
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).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

I see it as fuzzy testing of the community.
It is certainly beneficial if used correctly

Fuzzy Testing goes also by the name QuickCheck.
You can use Fuzzy Testing also for benchmarking.
Mathematically it uses the Law of Large Numbers:

Law of large numbers
https://en.wikipedia.org/wiki/Law_of_large_numbers

Means you even don’t need a random generator
with a programmable seed, so that a comparison
involves the exact same random number sequences.

Just assume that your results have a variation σ.
Then most likely the overall variation decreases
proportionally to the number n of experiments,
i.e. gets washed out:

VAR(X) = σ^2 / n

A third use case of Fuzzy Testing is to determine
frequentist probabilities . Like when I determined
that 25% of a variant of @kuniaki.mukai compare/3
triples are not transitive.


Mild Shock schrieb:

You can use Fuzzy Testing also for
benchmarking. Not only to find faults.
For example when I benchmark mercio/3 via
fuzzy/1, I find it doesn’t fare extremly bad:

?- time((between(1,100,_), mercio, fail; true)).
% 4,386,933 inferences, 0.375 CPU in 0.376 seconds (100% CPU, 11698488
Lips)
true.

And I am not using some of the optimization
that @kuniaki.mukai posted elsewhere and that
I posted 06.08.2025 on comp.lang.prolog. Fact is,
it only ca. 20% slower than SWI-Prologs compare/3:

?- time((between(1,100,_), swi, fail; true)).
% 3,786,880 inferences, 0.312 CPU in 0.325 seconds (96% CPU, 12118016 Lips) true.

The test harness was:

swi :-
    between(1,1000,_),
    fuzzy(X), fuzzy(Y),
    swi(_, X, Y), fail; true.

mercio :-
    between(1,1000,_),
    fuzzy(X), fuzzy(Y),
    mercio(_, X, Y), fail; true.

The difficulty was to find a 100% Prolog compare/3
that corresponds to SWI-Prolog. But you find a
fresh implementation in 100% Prolog using a Union
Find structure in the below:

% swi(-Atom, +Term, +Term)
swi(C, X, Y) :-
   swi(X, Y, C, [], _).

% swi( -Atom, +Term, +Term,+List, -List)
swi(C, X, Y, L, R) :- compound(X), compound(Y), !,
   sys_union_find(X, L, Z),
   sys_union_find(Y, L, T),
   swi_found(C, Z, T, L, R).
swi(X, Y, C, L, L) :- compare(C, X, Y).

% swi_found(-Atom, +Term, +Term, +List, -List)
swi_found(C, X, Y, L, L) :-
   same_term(X, Y), !, C = (=).
swi_found(C, X, Y, _, _) :-
   functor(X, F, N),
   functor(Y, G, M),
   compare(D, N/F, M/G),
   D \== (=), !, C = D.
swi_found(C, X, Y, L, R) :-
   X =.. [_|P],
   Y =.. [_|Q],
   foldl(swi(C), P, Q, [X-Y|L], R).

% sys_union_find(+Term, +List, -Term)
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).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

You can also test what was posted 06.08.2025
on comp.lang.prolog and then adopted by @kuniaki.mukai .
Here are the benchmark resuts, I find now.
Using again the Monte Carlo method:

?- time((between(1,100,_), mercio2, fail; true)).
% 4,404,670 inferences, 0.375 CPU in 0.375 seconds
true.

Practically no difference between mercio2/3
and mercio/2. The problem is that mercio2 doesn’t
add much smarts to the algorithm. Whereas for
example SWI-Prolog compare/3

has the smarts of Union Find. So a little break
through in Mercio’s Idea needs more than only
recasting the truncation sequences as a frontier list:

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).

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), !, X = A.
trunc(X, F/N) :- functor(X, F, N).

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).

Mild Shock schrieb:

I like the vibe, clearing the mind of everything
existing has a touch of a mystic human being living
an eremitic solitary vocation on a far out mountain
top. Using the internet only to emit his wisdom,

but not to ingest the outer world, just as in
Thus Spoke Zarathustra (*). Another name for Fuzzy Testing,
if the outcome is not finding the needle in the haystack,
but rather producing quantitative outcomes is,

unless of course you were living in a submerged pineapple (**):

Monte Carlo methods
or Monte Carlo experiments, are a broad class of
computational algorithms that rely on repeated random
sampling to obtain numerical results https://en.wikipedia.org/wiki/Monte_Carlo_method

(*)
Also Sprach Zarathustra, Op. 30 - Strauss https://www.youtube.com/watch?v=dfe8tCcHnKY

(**)
Every Time Patrick Was Actually Smart https://www.youtube.com/watch?v=siBRUuDxU1E

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

I like the vibe, clearing the mind of everything
existing has a touch of a mystic human being living
an eremitic solitary vocation on a far out mountain
top. Using the internet only to emit his wisdom,

but not to ingest the outer world, just as in
Thus Spoke Zarathustra (*). Another name for Fuzzy Testing,
if the outcome is not finding the needle in the haystack,
but rather producing quantitative outcomes is,

unless of course you were living in a submerged pineapple (**):

Monte Carlo methods
or Monte Carlo experiments, are a broad class of
computational algorithms that rely on repeated random
sampling to obtain numerical results https://en.wikipedia.org/wiki/Monte_Carlo_method

(*)
Also Sprach Zarathustra, Op. 30 - Strauss https://www.youtube.com/watch?v=dfe8tCcHnKY

(**)
Every Time Patrick Was Actually Smart https://www.youtube.com/watch?v=siBRUuDxU1E

Mild Shock schrieb:

I see it as fuzzy testing of the community.
It is certainly beneficial if used correctly

Fuzzy Testing goes also by the name QuickCheck.
You can use Fuzzy Testing also for benchmarking.
Mathematically it uses the Law of Large Numbers:

Law of large numbers
https://en.wikipedia.org/wiki/Law_of_large_numbers

Means you even don’t need a random generator
with a programmable seed, so that a comparison
involves the exact same random number sequences.

Just assume that your results have a variation σ.
Then most likely the overall variation decreases
proportionally to the number n of experiments,
i.e. gets washed out:

VAR(X) = σ^2 / n

A third use case of Fuzzy Testing is to determine
frequentist probabilities . Like when I determined
that 25% of a variant of @kuniaki.mukai compare/3
triples are not transitive.

Mild Shock schrieb:

You can use Fuzzy Testing also for
benchmarking. Not only to find faults.
For example when I benchmark mercio/3 via
fuzzy/1, I find it doesn’t fare extremly bad:

?- time((between(1,100,_), mercio, fail; true)).
% 4,386,933 inferences, 0.375 CPU in 0.376 seconds (100% CPU, 11698488
Lips)
true.

And I am not using some of the optimization
that @kuniaki.mukai posted elsewhere and that
I posted 06.08.2025 on comp.lang.prolog. Fact is,
it only ca. 20% slower than SWI-Prologs compare/3:

?- time((between(1,100,_), swi, fail; true)).
% 3,786,880 inferences, 0.312 CPU in 0.325 seconds (96% CPU, 12118016
Lips)
true.

The test harness was:

swi :-
     between(1,1000,_),
     fuzzy(X), fuzzy(Y),
     swi(_, X, Y), fail; true.

mercio :-
     between(1,1000,_),
     fuzzy(X), fuzzy(Y),
     mercio(_, X, Y), fail; true.

The difficulty was to find a 100% Prolog compare/3
that corresponds to SWI-Prolog. But you find a
fresh implementation in 100% Prolog using a Union
Find structure in the below:

% swi(-Atom, +Term, +Term)
swi(C, X, Y) :-
    swi(X, Y, C, [], _).

% swi( -Atom, +Term, +Term,+List, -List)
swi(C, X, Y, L, R) :- compound(X), compound(Y), !,
    sys_union_find(X, L, Z),
    sys_union_find(Y, L, T),
    swi_found(C, Z, T, L, R).
swi(X, Y, C, L, L) :- compare(C, X, Y).

% swi_found(-Atom, +Term, +Term, +List, -List)
swi_found(C, X, Y, L, L) :-
    same_term(X, Y), !, C = (=).
swi_found(C, X, Y, _, _) :-
    functor(X, F, N),
    functor(Y, G, M),
    compare(D, N/F, M/G),
    D \== (=), !, C = D.
swi_found(C, X, Y, L, R) :-
    X =.. [_|P],
    Y =.. [_|Q],
    foldl(swi(C), P, Q, [X-Y|L], R).

% sys_union_find(+Term, +List, -Term)
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).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)