[racket-dev] Comparison functions and the `data' collection

On 6/21/12 6:04 PM, Ryan Culpepper wrote:
> On 06/21/2012 09:38 AM, Eli Barzilay wrote:
>> More than a week ago, Ryan Culpepper wrote:
>>> On 06/11/2012 02:36 PM, Eli Barzilay wrote:
>>>> Yesterday, Danny Yoo wrote:
>>>>>
>>>>> It's a little unfortunate that there's a slight impedance mismatch
>>>>> between what datum-order provides and what sort expects; the
>>>>> my-less-than function in the example adapts the output of
>>>>> datum-order so it can be used with sort.
>>>>
>>>> Thanks for pointing it out (I didn't know about it).  When I
>>>> looked into this, I saw that in addition to `data/order' there is
>>>> also an issue with `data/heap'.  It certainly does look like a
>>>> problem worth addressing.
>>>>
>>>> The thing is that are two common ways to specify comparison functions:
>>>> (a) three-valued comparison functions returning -1/0/+1, (b) a boolan
>>>> strictly-smaller-than predicate.  The first is common in several
>>>> mainsteam languages and the second is traditionally common in
>>>> lisps (which leads to its use in the sort function).
>>>>
>>>> The issues are described very thoroughly in srfi-67 -- specifically,
>>>> see the first two subsections in section 6.  I highly recommend
>>>> reading that for this discussion.  They decide to go with option (a),
>>>> with an explanation for the choice of a three-valued function and for
>>>> their choice of -1/0/+1 values.
>>>
>>> I don't remember if I discovered srfi-67 before or after I added
>>> data/order.  In any case, I disagree with its rationale for -1/0/+1:
>>> I dislike the idea of performing arithmetic on orderings.
>>
>> (See below.)
>>
>>
>>> OTOH, data/order is used primarily by the ordered dictionary types
>>> (data/splay-tree, data/skip-list), so it's probably missing operations
>>> and conveniences for tasks like sorting a list.
>>
>> (I take it that they will be added, then...)
>>
>>
>>>> 2. The `data/order' interface has several problems that I think is
>>>>      best to resolve.
>>>>
>>>>      - Regadless of the above, it seems like a good idea to extend
>>>>        the interface with a simple boolean predicate.  Maybe
>>>>        something like `datum<?' and possibly others.  This would
>>>>        address the issue that Danny raised above.
>>>
>>>    From an order you can get the less-than and equality predicates:
>>>
>>>     (order-<? datum-order)
>>>     (order-=? datum-order)
>>
>> Yes, of course this is easy.  I can also do that `case' in a tiny λ.
>> But it should be part of the library.
>>
>>
>> On Saturday, Matthias Felleisen wrote:
>>>
>>> This response leaves us with the impression that we whimsically
>>> challenged established conventions in the general and the
>>> Lisp-specific PL family. In addition it leaves us with
>>> inconsistencies across our libraries, which I am coming to consider
>>> more and more as a serious problem.
>>
>> Yes, that was exactly why I raised it.  Since it's core-ish
>> functionality, having it behave well wrt expectations is IMO extremely
>> important.  Right now we have a sad state of two different
>> incompatibilities there, and I don't see any good explanation except
>> for the "I disagree/dislike" (in contrast to the srfi).  Because of
>> such expectations and because of existing code, I'd follow that
>> without thinking about what might the right choice be.
>>
>> (Personally, I now think that the more lenient approach of any
>> numbers, negative, 0, or positive is even better -- and I can also
>> explain and justify why I think that, but that's irrelevant.)
>>
>>
>>> Now -- I would be the last one to defend "established tradition"
>>> over "getting things right" but at a minimum, the reasoning of why
>>> we challenge tradition should be noted.
>>
>> +7
>
> There's an advocate of my position in the SRFI discussion archives. See
> the following messages by Panu Kalliokoski:
>
> http://srfi.schemers.org/srfi-67/mail-archive/msg00021.html
> http://srfi.schemers.org/srfi-67/mail-archive/msg00023.html
> http://srfi.schemers.org/srfi-67/mail-archive/msg00025.html
>
> Of course, the SRFI still went the other way. I would be happy to add
> functions to convert between the two conventions.

I think {-1,0,1} is the worst of all worlds.  I prefer the more lenient 
approach of allowing any number[*].  This follows the Lisp tradition of 
returning "more than just the truth", since a comparison can also convey 
the difference between the arguments; in other words `-' is a comparison 
function, which is the trick I use to remember how to interpret the 
result of compare functions in Java, for example.

If we really want to break tradition by restricting to "just the truth" 
(a three-valued function), meaningful symbols is my preference over 
{-1,0,1}.

[*] Well, reals minus infinities and nans.

David