Hi,
Creating a compare/3 on cyclic terms is a fascinating
topic. Obviously the following implementation would work,
namely transform a cyclic term into a non-cyclic representation,
and compare its representation:
/* total order using a representation */
compare_rep(C, X, Y) :-
rep(X, A),
rep(Y, B),
compare(C, A, B).
Provided rep is injective, if the non-cyclic representation can be
totally ordered, the original cyclic terms will be also totally
ordered. One might add further requirements to
rep, namely that it is conservative, ordering acyclic terms in
the standard order as require by the ISO core standard. This
was a discussion on SWI discourse a few months ago. But it
never adressed the issue how to efficiently sort/2 or keysort/2,
when the involved lists or pair lists contain cyclic terms. Now
since AI has become so omniscent, it easily handled me a tip,
both Gemini and Deepseek did that, and pointed me to the
Schwartzian Transform. Possibly even more ideal when one
has ultra fast minimization. The idea is very simple, sketch:
/* sorting using a representation */
sort_rep(List, Result) :-
maplist(λXλZ.(rep(X,Y), Z = (Y,X)), List, List2),
keysort(List2, List3),
maplist(λZλX.(Z = (_,X)), List3, List4),
dedup(List4, Result).
The benefit when measured against predsort/3, that would use
compare_rep/2, is that predsort might call O(N log(N)) or more
comparisons. While the above only does a collation key computation
once per element, making it O(N). AI being quite a buddy here!
If the representation is injective, the dedup/2, which can be realized
via hash table, can be replaced by a more simpler unique/2.
Bye
P.S.: Strange thing, I like the two AIs more than the agentic AI
approach, that fiddles with your code. The AIs are a little bit more
talkie, and do make connections to math, logic and even Perl!
See also:
Schwartzian transform
The idiom is named after Randal L. Schwartz, who first
demonstrated it in Perl, shortly after the release of Perl 5 in 1994.
Schwartzian transform - Wikipedia