Lambda the Ultimate

Order structures seem to be abstract concepts of theoretical mathematics with
minor practical importance. But this is just at first glance. A closer look
reveals that many data types have order structure.

• The basic types NATURAL, INTEGER, FLOAT etc. have a total order
• The type SET[T] has a partial order with "is_subset" playing the role of
  "<=".
• All inductive types have a partial order where "a<=b" means "a has been used
  directly or indirectly in the construction of b". E.g. any subtree of a tree
  is smaller than the tree.
• The nodes in a graph have a preorder relation with "a<=b" meaning "a can
  reach b".
• The functions "f:A->B" have a partial order where the "smaller" function has
  the same values as the "greater" function but has a restricted domain.
• The predicates "p:T?" have a partial order where "a<=b" meaning "a" is
  stronger than "b", i.e. "a" has less elements for which it is true than "b".

The article Order structure, an excercise in abstraction and multiple inheritance
describes preorders and partial orders together with the basic assertions which can
be derived from the basic structure and its functions.

Why is it interesting to carve out the order structure?

It is possible to prove a lot of properties by just using the definition of
the functions of order relations. Any structure which inherits the appropriate
order relation has access to all already proved asssertions. The order classes
act as an "assertion library" and inheritance is reuse of these assertions.