Hi,
While the rep() approach leads automatically
to total orders. As was already seen in Mercio’s
Algorithm where rep(A) = A’. We can also arrange
that it leads to natural orders that are
conservative, using the Dushnik–
Miller theorem:
Dushnik–Miller theorem
Countable linear orders have non-identity order self-embeddings.
https://en.wikipedia.org/wiki/Dushnik%E2%80%93Miller_theorem
I guess the theorem can be proved
with a Hilbert Hotel argument?
Here are some examples, works for terms that
don’t use '$VAR'/1 with a negative index, using
in fact an identity self-embedding on acyclic terms:
?- X = f(f(f(X))), naish(X,A).
X = f(f(f(X))),
A = f(f(f(S_3))).
?- X = s(Y,0), Y = s(X,1), naish(X,A), naish(Y,B).
X = s(s(X, 1), 0),
Y = s(X, 1),
A = s(s(S_2, 1), 0),
B = s(s(S_2, 0), 1).
naish/2 is named after Lee Naish, we use a
variant with deBruijn indexes:
naish(X, Y) :-
naish([], X, Y).
naish(_, X, X) :- var(X), !.
naish(S, X, Z) :- compound(X),
nth1(N, S, Y), same_term(X, Y), !,
M is -N,
Z = '$VAR'(M).
naish(S, X, Y) :- compound(X), !,
X =.. [F|L],
maplist(naish([X|S]), L, R),
Y =.. [F|R].
naish(_, X, X).
Bye
Mild Shock schrieb:
Hi,
Functional requirement:
?- Y = g(_,_), X = f(Y,C,D,Y), term_singletons(X, L),
L == [C,D].
?- Y = g(A,X,B), X = f(Y,C,D), term_singletons(X, L),
L == [A,B,C,D].
Non-Functional requirement:
?- member(N,[5,10,15]), time(singletons(N)), fail; true.
% Zeit 1 ms, GC 0 ms, Lips 4046000, Uhr 11.08.2025 01:36
% Zeit 3 ms, GC 0 ms, Lips 1352000, Uhr 11.08.2025 01:36
% Zeit 3 ms, GC 0 ms, Lips 1355333, Uhr 11.08.2025 01:36
true.
Can your Prolog system do that?
P.S.: Benchmark was:
singletons(N) :-
hydra2(N,Y),
between(1,1000,_), term_singletons(Y,_), fail; true.
hydra2(0, _) :- !.
hydra2(N, s(X,X)) :-
M is N-1,
hydra2(M, X).
Bye
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)