[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Scheme-reports] R7RS-large comparators



The world has many useful partial orders.  However, clarity is greatly
aided by the programmer being able to express their expectation that a
particular set of interest in fact forms a total order.  I therefore
think it is not unreasonable for a programming language to have two
different operations that are like "less than" -- one for total order
comparison, which signals a condition or otherwise does something
extraordinary if given two incomparable objects, and another for
partial order comparison, which always returns normally but is free to
return one of four objects (which themselves form a natural partial
order) to indicate "equal", "less", "greater", or "incomparable".

Under this view, I suggest that SRFI 114 concern itself with total
orders only; perhaps it would be appropriate to propose another SRFI
for partial orders.  Doing so should be very interesting: Among other
subtleties, in general partial orders meet and join are not max and
min; and in particular, may not always exist, or may exist but not be
unique, or may exist and be unique but be considerably more expensive
to compute than comparison.  So it becomes reasonable to make a
distinction between partial orders and lattices (and also
semi-lattices, which have one of meet or join but not the other);
whereas every total order is a lattice.

~Alexey

P.S.  Unfortunately, the mathematical tradition uses the same symbol
for both total and partial comparison, and Scheme has not yet
standardized a generic dispatch facility that could be used to
disambiguate by the types of the arguments.  So the putative partial
order comparisons SRFI would have to choose whether to use an ugly
notation right off, or walk right into naming collisions and rely on
(programmers and) the module system to fix them.


On Fri, Jul 12, 2013 at 7:52 PM, Alan Manuel Gloria <almkglor@xxxxxxxxx> wrote:
>
>
>> > General Issues:
>> > It is my personal opinion that this module should be helpful to anyone
>> > involved in either total orders or partial orders, such as
>> > floating-point
>> > numbers (which form a total order if you ignore NaNs and -0.0). One way
>> > of
>> > doing this would be to use an exception/condition to express a lack of
>> > total order, another would be to return something other than -1, 0, 1
>> > from
>> > the compare procedure (perhaps return +nan.0), which would violate the
>> > conditions for a compare procedure according to this module as specified
>> > so
>> > far. I'm not sure what the best way to do this is, except to provide
>> > additional procedures for floating-point numbers, and not handle partial
>> > orders in a general way. My intuition tells me that a general approach
>> > would be more valuable in the long term, than to special case floats.
>> > Treating any and all partial orders that come along as special cases,
>> > just
>> > seems wrong to me.
>>
>> SRFI 114 does provide a special case for floats.  What would be other
>> use cases for partial orders in general?
>
>
> Subtyping relations are a partial ordering.
>
> Consider:
>
> Numbers >= Complex >= Reals >= Rationals >= Integers >= Naturals
>
> However, consider also:
>
> Numbers >= Complex >= Imaginaries
>
> The Imaginaries type is "incomparable" to the Reals, Rationals, Integers, or
> Naturals type, because it follows a different branch of subtyping.  This
> forms a partial ordering.
>
> It would be nice to be able to "compare" two type objects and learn if one
> is a sub-type of the other, is the same type, or are incomparable.
>
> Sets may also be compared (basically, if you consider that subtype ==
> subset, so that "the set of Numbers is a superset of Reals"), and the result
> may also be "incomparable", i.e. one is not a strict subset of or equal to
> the other.
>
> For floats, perhaps NaN should return "incomparable" if one side is a NaN
> and the other is not, or "equal" if both are NaN (this would simplify some
> uses of hash tables).  As for -0.0, perhaps we can consider it as actually
> being -(epsilon/2), so that it is less than 0.0 but greater than -epsilon,
> where epsilon is the tiniest representable non-zero float.
>
> Personally, I'd like the "incomparable" case to return "a unique,
> non-numeric object of unspecified type, which may be compared by eq? to the
> exported binding INCOMPARABLE, e.g. (eq? (compare a b) INCOMPARABLE)." but
> that's just me.