Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #15937

Food for thought: Schwartzian Transform (Was: VIP0111: Does a Map have a Constructor?)

From Mild Shock <janburse@fastmail.fm>
Newsgroups comp.lang.prolog
Subject Food for thought: Schwartzian Transform (Was: VIP0111: Does a Map have a Constructor?)
Date 2026-09-23 22:01 +0200
Message-ID <1191b63$6fpr$1@solani.org> (permalink)
References <107cdg8$3ok7g$1@solani.org> <10p44s1$16ps$1@solani.org>

Show all headers | View raw

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:

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
completely ordered, the original cyclic terms will be also
completely 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:

1. List' = [ (rep(x),x)  | x e List ]
2. List'' = sort_on(π1, List')             %% sort on 1st argument
3. Result = [ π2(x) | x e List'']          %% project to 2nd argument

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!

Bye

See also:

Schwartzian transform
https://en.wikipedia.org/wiki/Schwartzian_transform

(*)
https://gemini.google.com/
(**)
https://www.deepseek.com/

Mild Shock schrieb:
> Hi,
> 
> How would we do a reverse sorted map?
> 
> I find in Java:
> 
> TreeMap(Comparator<? super K> comparator)
> Constructs a new, empty tree map, ordered
> according to the given comparator.
> https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html
> 
> Or in Dogelog Player:
> 
> tree_new(T):
> tree_new(T, F):
> The predicate succeeds in R with a new red-black tree.
> The binary predicate allows specifying a term compare F.
> https://www.dogelog.ch/typtab/doclet/book/12_lang/05_libraries/03_util/06_tree.html 
> 
> 
> Here is an example, using the destructive API. But
> the same constructor works also for the non-destructive API.
> 
> ?- tree_new(_T), tree_add(_T, 0rInf, foo),
>     tree_add(_T, 0rNaN, bar), tree_pairs(_T, L).
> L = [0rNaN-bar, 0rInf-foo].
> 
> And now using a comparator modifier, aggregate with a comparator,
> as a closure. Some Joy of Higher Order logic programming:
> 
> reverse(C, R, X, Y) :- call(C, R, Y, X).
> 
> ?- tree_new(_T,reverse(compare)), tree_add(_T, 0rInf, foo),
>     tree_add(_T, 0rNaN, bar), tree_pairs(_T, L).
> L = [0rInf-foo, 0rNaN-bar].
> 
> ?- tree_new(_T,reverse(reverse(compare))), tree_add(_T, 0rInf, foo),
>     tree_add(_T, 0rNaN, bar), tree_pairs(_T, L).
> L = [0rNaN-bar, 0rInf-foo].
> 
> Just toying around with my new NaNs.
> 
> Have Fun!
> 
> 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
>

Back to comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

VIP0909: VibeCore Improvement Proposal Mild Shock <janburse@fastmail.fm> - 2025-08-11 11:35 +0200
  VIP0111: Does a Map have a Constructor? (Was: VIP0909: VibeCore Improvement Proposal) Mild Shock <janburse@fastmail.fm> - 2026-03-14 18:11 +0100
    100% Prolog Hash map beats SWI C Trie (Was: VIP0111: Does a Map have a Constructor?) Mild Shock <janburse@fastmail.fm> - 2026-03-17 04:07 +0100
    AI Accelerators and ISO Prolog multi-threading (Was: VIP0111: Does a Map have a Constructor?) Mild Shock <janburse@fastmail.fm> - 2026-07-29 15:28 +0200
      Actor/Erlang is dead, no Thread and Mailbox conflation [golang channels] (Was: AI Accelerators and ISO Prolog multi-threading) Mild Shock <janburse@fastmail.fm> - 2026-07-29 15:41 +0200
        Summer Challenge: libSQL = Prolog+Modes [VDBE versus π-WAM] (Was: Actor/Erlang is dead, no Thread and Mailbox conflation [golang channels]) Mild Shock <janburse@fastmail.fm> - 2026-07-30 11:22 +0200
          Work slicing can simulate AbortController (Was: Summer Challenge: libSQL = Prolog+Modes [VDBE versus π-WAM]) Mild Shock <janburse@fastmail.fm> - 2026-08-01 13:23 +0200
      Introducing an asm/1 statement in a Prolog system (Was: AI Accelerators and ISO Prolog multi-threading) Mild Shock <janburse@fastmail.fm> - 2026-08-09 20:21 +0200
      Introducing an asm/1 statement in a Prolog system (Re: AI Accelerators and ISO Prolog multi-threading) Mild Shock <janburse@fastmail.fm> - 2026-08-09 20:25 +0200
      MADV_HAWAII: Aloha from the 300ms Abyss [Exception Handling in Prolog] (Re: AI Accelerators and ISO Prolog multi-threading) Mild Shock <janburse@fastmail.fm> - 2026-09-10 23:42 +0200
        MADV_HAWAII: Aloha from Minimal Terms (Was: MADV_HAWAII: Aloha from the 300ms Abyss) Mild Shock <janburse@fastmail.fm> - 2026-09-14 14:43 +0200
          MADV_HAWAII: Decomposing the Ouroboros Road (Was: MADV_HAWAII: Aloha from the 300ms Abyss) Mild Shock <janburse@fastmail.fm> - 2026-09-20 18:30 +0200
    Food for thought: Schwartzian Transform (Was: VIP0111: Does a Map have a Constructor?) Mild Shock <janburse@fastmail.fm> - 2026-09-23 22:01 +0200
      Food for thought: Bayesian Experimental Designer (Was: Food for thought: Schwartzian Transform) Mild Shock <janburse@fastmail.fm> - 2026-09-24 14:32 +0200
        What will microsoft say, will they buy it? (Was: Food for thought: Bayesian Experimental Designer) Mild Shock <janburse@fastmail.fm> - 2026-09-24 15:34 +0200
          The recursive AI bottom line (Was: What will microsoft say, will they buy it?) Mild Shock <janburse@fastmail.fm> - 2026-09-24 15:38 +0200

csiph-web