This might require detective work. The original oset.pl file seems to be from 1993 and contained the relevant code that is now in library(ordsets). That code is again very similar to the code in “The Craft of Prolog” by O’Keefe, which was published in 1990. I have seen that before; but I also took care to translate the procedural code (for multisets!) I linked above in a “mechanical” fashion (see below for a demonstration). And I ended up with basically the same predicates and helper predicates (I did order my arguments differently…). But I don’t see any references in O’Keefe’s text, so I assume it is just such an obvious algorithm that you end up with the same anyway.
It is an optimization, when the head and tail of the second argument are already unpacked, they are used in a call to the helper predicate that initially takes the head and tail of the first argument. You save two predicate calls.
Yes, correct. Because a set is not ordered, the implementation is free to throw away the initial order and work with lists of sorted elements, since this allows for a better algorithm. Python for example has a container called OrderedDict which maintains the order in which key-value pairs were inserted.