On to Hydro

[Dean Tribble]

Given how well partial prders worked out in the Xanadu collections, I'm a 
strong advocate of using them.  To the extent that programmers are stayed 
in familiar domains, the difference between partial and full orders was 
never an issue (i.e., the programmer did not have to be aware of it).  But, 
use of partial orders enabled straightforward extension and *understanding* 
of domains for which full orders could not be defined, but for which all 
the iteration, collection, sorting (which for partial orders must be 
stable), etc. were still coherent.

>True, but maybe we need some other concept for them other than "less
>than". Less than implies that I can sort. I can't sort with only a
>partial ordering. I can't even search with only a partial ordering.

Sure you can.  :-)  For sorting, you end up with a full ordering consistent 
with the partial ordering.  For searching, typically you would have 
data-structures that are directly suited to your problem (e.g., a graph to 
walk).  However for a general tree data structure, each comparison operator 
splits the set of possible targets into things for which the comparison is 
true, and things for which it is not (e.g., "all points <= to (3,4)" where 
the point (4,3) is not in that set because it is not comparable).  You can 
then do a binary search.  The fancy Xanadu data-structures just require 
partial ordering (plus a few other properties independent of ordering).

The primary comparison operator we used was '<='.  Everything else was 
defined in terms of that.  Strict weak ordering sorts into three categories 
of less-than, greater-than, and mu where mu is defined as 
equivalence.  '<=' gives you four categories of less-than, greater-than, 
equivalence, and mu.  The result or using partial orders is equally 
efficient searching for full orders, and efficient support for partial 
orders.  By contrast, not using partial provides minimal if any advantage, 
and prevents the straightforward reuse of the system collection 
abstractions for any partially ordered space (N-dimensional, distributed 
time, trees, graphs, function spaces, etc.,).

>I
>think you'll have to upgrade the "<" operator to at least strict weak
>ordering, though I'll push for total ordering.
>
>I think the solution might be that we don't provide any 'automatic'
>comparison operators, and just map them all into method names.
>
>Operator   Method     Ordering
>--------   ------     ---------
>    <       before     total or strict weak
>    <=      within     partial
>    >       after      total or strict weak
>    >=      includes   partial
>
>Tyler