Re: [Scheme-reports] R7RS-large comparators Alexey Radul 13 Jul 2013 02:48 UTC
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 <email@example.com> 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.