Disclaimer: I seem to have a preoccupation with ordering and sorting; I have managed to not let it influence my daily life too badly. I lived in Germany once but I left the country. This topic pops up periodically. This time it is the library(ordsets) and multisets discussion . This is not an exclu…

[image] Boris: Yes, but I had a reason not to. That code ends up in the same place but does not include multisets (lists as sorted by msort/2 ) in the spec. What do you mean by that? Amazingly he explicitly considers duplicates in chapter 4 where he defines what a multi-set list is, and he c…

[image] Johnny_Rotten: Could be that SWI-Prolog got lost track of that spec: Maybe we could say Richard O’Keefe nicely covers the merge/3 operation for multi-set lists and non-multi set lists. But there are usually more operations like intersection/3, subtraction/3, etc.. And their semanti…

Yes, sure. You can also find the msorted_until/4 predicate in msorted.pl I shared above. The ordered_list/1 you show can be bootstrapped as ordered_list(L) :- msorted_until(L, _, _, Rest), Rest == []. I had versions of all predicates in msorted.pl that used the weaker less_than/2 compariso…

I took a shortcut in msorted.pl and just used the merge/3 available in backcomp.pl: %! merge(+List1, +List2, -List3) % % Merge the ordered sets List1 and List2 into a new ordered list. % Duplicates are not removed and their order is maintained. % % @deprecated The name of this predicate…

[image] Johnny_Rotten: [image] Boris: Yes, but I had a reason not to. That code ends up in the same place but does not include multisets (lists as sorted by msort/2 ) in the spec. What do you mean by that? What I mean is that unless I am very confused, the code in “The Craft of Prolog” …

[image] Boris: , the code in “The Craft of Prolog” from 1990, just like the code in the original oset.pl from 1993, talks about ordered lists as created by sort/2 . But it obviously does not in the book for merge/3 and ord_union/3. Or Richard O’Keefe is not aware what he did. This is also pos…

What do you mean? Either way, I am not interested in archeology that much. Note that I have not claimed any authorship in the source files I have shared because I believe this is all in the public domain. All I want is to have a useful library, and in fact I do already.

[image] Boris: What do you mean? Either way, I am not interested in archeology that much. Well you are right that he considers only sets. Because he defines: “A good representation to use is the one that the built-in predicate setof/3 returns, namely a list of elements in standard order (a…

[image] Johnny_Rotten: The same glitch is now found in the SWI-Prolog library. Yes, exactly! This is what motivated me to open this topic. On the other hand, it seems that multisets are not that popular :grinning_face:

[image] Boris: On the other hand, it seems that multisets are not that popular :grinning_face: Well now I got myself confused. ord_union/3 doesn’t implement merge/3. You see it here: ?- ord_union([a],[a,a,a], X). X = [a, a, a]. ?- ord_union([a,a,a,a,a],[a,a,a], X). X = [a, a, a, a, a]. On…

Order and sorting

Help! Algorithm

Johnny_Rotten April 9, 2026, 2:18pm 35

But it obviously does not in the book for merge/3 and ord_union/3.
Or Richard O’Keefe is not aware what he did. This is also possible.
He says his version is a cleaned up version of some Quintus Prolog code.

Topic		Replies	Views
Unexpected semantics of library(ordsets) for ordered _lists_ (not sets) General	55	307	March 26, 2026
On sorting non-ground terms and the standard order of terms General	26	1914	January 2, 2020
What does sort/2 do? Predicate	33	7879	December 22, 2020
Sorting predicates in PROLOG Help! how-to	23	3390	August 3, 2022
Effective implementation of a set Help!	11	1501	February 26, 2020

Order and sorting

Related topics