# Food for thought: Schwartzian Transform

**URL:** <https://discourse.prolog-lang.org/t/food-for-thought-schwartzian-transform/207>\
**Category:** General discussions on Prolog\
**Created:** [September 23, 2026, 7:52pm UTC](https://discourse.prolog-lang.org/t/food-for-thought-schwartzian-transform/207 "2026-09-23T19:52:38Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![j4n\_bur53](https://discourse.prolog-lang.org/user_avatar/discourse.prolog-lang.org/j4n_bur53/32/62_2.png) [@j4n\_bur53](https://discourse.prolog-lang.org/u/j4n_bur53)\
**Post date:** [September 23, 2026, 7:52pm UTC](https://discourse.prolog-lang.org/t/food-for-thought-schwartzian-transform/207/1 "2026-09-23T19:52:38Z")

</div>

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:

```c++
/* 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](https://gemini.google.com/) and [Deepseek](https://www.deepseek.com/) 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:

```c++
/* 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](https://en.wikipedia.org/wiki/Schwartzian_transform)