Hi Jan, we are now at 48 (!) posts here, I understand this is too much.
Yes, fully agree. I wanted to provide such a library, based on existing practice. While researching, I learned something and I wrote some code but I only ended up with more questions 
Existing practice is to provide algorithms that create or work on sorted lists [1]. The set operations “union”, “intersection”, and so on are part of it. Other examples would be “partition point”, “is sorted until”, or “merge” [2].
I am attaching two files which contain a few such algoritms and a test suite for them, including tests for some of the library(ordsets) predicates:
sorted.pl (6.5 KB)
test_sorted.pl (6.2 KB)
At the moment those only work with compare/3 on the full terms, so equality.
All of this is quite useless because it is using equality and the “set” algorithms are de facto identical to library(ordsets). These algorithms become useful when we can use equivalence instead [3]. Initially, I planned to provide equivalence using a predsort/3 -like interface, where the client code provides a comparison predicate. I have not done it because it is trivial; and because I am not sure that this is the way forward.
Current status: the code in sorted.pl is marginally useful, as a starting point for a discussion for a possible library. The tests were useful to me while writing the code. This could be extended in two orthogonal directions:
- A presumably more efficient version could be implemented in C as a foreign library, I think I’d know how to do that;
- Versions of the algorithms that take a comparison predicate with the same signature as compare/3 (the predsort/3 interface) can be trivially added to it.
Now I have answered my original question from the first post in this topic (yay!). This only opened a new question:
Is this useful in Prolog at all? I don’t see an obvious way of providing an efficient implementation of these algorithms for equivalence, with a client-code provided comparison predicate (it will require calling Prolog from C on every comparison, right?). I suspect it is possible to achieve a useful efficient implementation if we used the sort/4 interface instead, where the client code provides a key and an order. I wanted to share this preliminary work in this post, hoping to get some comments. Implementing algorithms on sorted lists that use the sort/4 interface (Key + Order instead of Comparison) is just a vague idea at the moment and it will require more work. I will do eventually
[1] I purposefully used the specifications and reference implementation from the C++ algorithms library as a starting point. Section 6, “Sequences” pp 187-259 of O’Keefe’s “The Craft of Prolog” covers the same topics in a very similar manner. For example, 6.8.1 “Prefixes of lists” on page 232 shows another take on partition_point/5 in the attached sorted.pl. Section 5, “Data Structure Design” pp 153-186 contains the “set as a sorted list” examples, which seem to have strongly influenced library(oset) and library(ordsets). See this post above.
There is a powerful idea: keeping the algorithms separate from the data structure. Alex Stepanov, the original author of the notorious “Standard Template Library”, has tried to demonstrate this; his approach is to define the algorithms only through iterators on the data structure. See “Elements of Programming” by Stepanov and McJones and “From Mathematics to Generic Programming” by Stepanov and Rose. O’Keefe also spends some time showing how to convert from one concrete sequence implementation (list, backtracking…) to another.
[2] In my proposal I have only considered algorithms that require a “forward iterator”, so that they can be efficiently implemented on Prolog lists.
[3] Sorted in languages from the C tradition usually means “sorted on a binary relation”, and the default is “less than”. There is no reason to prefer the binary relation over compare/3. If needed, one could define compare_rel/3 in terms of a relation rel/2 like this:
compare_rel(Order, A, B) :-
( rel(A, B)
-> Order = (<)
; rel(B, A)
-> Order = (>)
; Order = (=)
).
A binary relation is a total ordering if it is transitive and obeys the trichotomy law, where for every pair of elements, only one holds: the relation, its converse, or equality. Prolog’s standard order of terms with compare/3 is an example of a total ordering. If we replace equality with equivalence, we have the weak-trichotomy law. keysort/2 in Prolog is an example of equivalence, where two terms are equivalent if the keys are equal. sort/4 already supports equivalence with a more expressive interface than keysort/2.
A small observation: nat_sort() in pl-list.c seems to sort using a “sorted until” and “merge”, but those are deeply embedded in the implementation and I didn’t see an obvious way to reuse them for my purposes, other than as inspiration.
