From Newsgroup: comp.lang.prolog

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?
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

Hi,

Nope, stack overflow didn't invent Gameification.
This was already quite fun:

IEEE Guide to Classificaton of Software Anomalies https://github.com/Orthant/IEEE/blob/master/1044.1-1995.pdf

Here some examples:

- Boing Airplane lost in the Maledives:
No problem, severity 7

- Salary Payed twice by Booking Software:
No problem, severity 0

LoL

Bye

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?

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

Hi,

But who would have thought that Gameification leads to
Bitrot? I mean I asked the question when I had user4414,
until somebody mobbed me on MSE.

Now there is a nonsense answer accepted, and I will
not correct it. Since I don't use Bitrot anymore:

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

The question "What is a natural one that is closest
to the lexical order?" of course wants "Conservativity".
Because by "lexical order" we mean (@<)/2 from Prolog.

But Mercio’s Algorithm doesn't satisfy Mats Carlsons appeal,
so we find a counter example to "Conservativity", which
is quite interesting:

problem(X, Y) :-
repeat, fuzzy(X), acyclic_term(X),
fuzzy(Y), acyclic_term(Y),
mercio(<, X, Y), \+ X @< Y.

?- problem(X, Y).
X = s(s(1, 1), 1),
Y = s(s(1, _), s(_, 1))

It is interesting, since it is now an a) an acyclic term,
and that b) violates Mats Carlsons appeal:

?- X = s(s(1, 1), 1), Y = s(s(1, _), s(_, 1)), mercio(C, X, Y).
X = s(s(1, 1), 1),
Y = s(s(1, _), s(_, 1)),
C = (<).

?- X1 = s(1,1), Y1 = s(1,_), mercio(C, X1, Y1).
X1 = s(1, 1),
Y1 = s(1, _),
C = (>).

This is kind of an independence proof of total
order and Mats Carlsons appeal.

Cool!

Bye

Mild Shock schrieb:

Hi,

Nope, stack overflow didn't invent Gameification.
This was already quite fun:

IEEE Guide to Classificaton of Software Anomalies https://github.com/Orthant/IEEE/blob/master/1044.1-1995.pdf

Here some examples:

- Boing Airplane lost in the Maledives:
  No problem, severity 7

- Salary Payed twice by Booking Software:
  No problem, severity 0

LoL

Bye

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?

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog


I guess its back to Hopcroft and Karp. And say
goodby to Mercio’s. What would work for sorting
and conservativity is a certain normal form of a DFA.
I was researching creating a minimal DFA,

but didn’t found yet a good paper. A O(N^2)
algorithm is rather straight forward, but I
wonder what a O(N log(N)) algorithm does. I only
find a good paper detailing bisimulation.

Especially from an implementation point of view,
still forming an arc to mathematical theory as well:

Hopcroft and Karp’s algorithm for Non-deterministic Finite Automata https://hal.science/hal-00639716v1/file/hkc.pdf

You might be surprised that your algorithms
compare_with_stack/3, escentially contain what
is know by the name “Naive Hopcroft and Karp
for Equality of DFA”. Whereby what SWI-Prolog

internally uses with Union Find, ist called the
“Non-Naive Hopcroft and Karp for Equality of DFA”.

Mild Shock schrieb:

Hi,

But who would have thought that Gameification leads to
Bitrot? I mean I asked the question when I had user4414,
until somebody mobbed me on MSE.

Now there is a nonsense answer accepted, and I will
not correct it. Since I don't use Bitrot anymore:

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

The question "What is a natural one that is closest
to the lexical order?" of course wants "Conservativity".
Because by "lexical order" we mean (@<)/2 from Prolog.

But Mercio’s Algorithm doesn't satisfy Mats Carlsons appeal,
so we find a counter example to "Conservativity", which
is quite interesting:

problem(X, Y) :-
   repeat, fuzzy(X), acyclic_term(X),
   fuzzy(Y), acyclic_term(Y),
   mercio(<, X, Y), \+ X @< Y.

?- problem(X, Y).
X = s(s(1, 1), 1),
Y = s(s(1, _), s(_, 1))

It is interesting, since it is now an a) an acyclic term,
and that b) violates Mats Carlsons appeal:

?- X = s(s(1, 1), 1), Y = s(s(1, _), s(_, 1)), mercio(C, X, Y).
X = s(s(1, 1), 1),
Y = s(s(1, _), s(_, 1)),
C = (<).

?- X1 = s(1,1), Y1 = s(1,_), mercio(C, X1, Y1).
X1 = s(1, 1),
Y1 = s(1, _),
C = (>).

This is kind of an independence proof of total
order and Mats Carlsons appeal.

Cool!

Bye

Mild Shock schrieb:

Hi,

Nope, stack overflow didn't invent Gameification.
This was already quite fun:

IEEE Guide to Classificaton of Software Anomalies
https://github.com/Orthant/IEEE/blob/master/1044.1-1995.pdf

Here some examples:

- Boing Airplane lost in the Maledives:
   No problem, severity 7

- Salary Payed twice by Booking Software:
   No problem, severity 0

LoL

Bye

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?

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog


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?

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog


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.

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog


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.

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog


Disclaimer: I don’t know whether Non-Naive
HK is even allowed in this setting, and how
one would exactly implement it. Realization

should not distort future (<) or (>) outcomes.

Mild Shock schrieb:

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.

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

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.
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog


What is worth looking into, is whether your
“frontier pair list” variant of mercio/3 has
some merit. It might be an improvement of what
I have posted on comp.lang.prolog 06.08.2025,

by fusing compare_truncs/2 and next_truncs/2
into a single predicate. This is quite possible,
but is it necessary? Does it give some speed
advantage? I guess no, because

you will do next_truncs/2 even when not needed,
when compare_truncs/2 gives (<) or (>). So
my guess your fpl_compare/4 is slower than
this, which has

a fast failure feature builtin-in, no unnecessary
add_pair_of_args/5 if the current level is
different. What one could learn from fpl_compare/4
is doing the code more DCG-ish

and for example fuse zip/3 and append/3.

Mild Shock schrieb:

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.

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

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?

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

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).
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog

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

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog


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

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.prolog


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

--- Synchronet 3.21a-Linux NewsLink 1.2