Represent Ordering using PartialOrder

[normen662]

For a lot of semantic reasoning we already use a PartialOrder<KeyPart> to represent orderings. However, for plan annotation and book keeping we use a List<KeyPart>. That proves to be lossy in a way that certain operations lose desirable and advantageous properties.

Example:

• three orderings:
  • o1: (a, b) with c = 5
  • o2: (a, b) with c = 6
  • o3: (a, b, c)

The combined ordering for union distinct purposes is (a, b, c). The function for combining these ordering is called combine(...) which is n-ary, i.e. combine(o1, o2, o3) ==> (a, b, c).

However, combine(combine(o1, o2), o3) is (a, b):

• combine(o1, o2) ==> one of three: (a, b, c), (a, c, b), or (c, a, b) (it's stable but not well-defined)
• combine((a, b, c), o3) ==> a variety of options:
  • (a, b, c), if combine(o1, o2) ==> (a, b, c)
  • (a), if combine(o1, o2) ==> (a, c, b)
  • empty(), if combine(o1, o2) ==> (c, a, b)

Of course that behavior is not really desirable at all. If expressed using PartialOrder this is not a problem as combine(o1, o2) is always ({a, b, c}, {a->b}), i.e. not fixing the position of c within (a, b).