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

Yesterday, 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: [...]

(I didn't know that Mike was on the numeric results side too.)


> Of course, the SRFI still went the other way. I would be happy to add 
> functions to convert between the two conventions.

And I replied (half asleep, and from my phone):

> Conversion isn't doing anything, as in the two arguments case.

That should have been "the two valued case".  I need to clarify that:

1. Adding it as conversion functions is not doing much for people who
   are aware of it, since writing these lambdas by hand is almost as
   short as using a conversion function.

2. Meanwhile, people who look for something like `datum-order<?' won't
   find it, and people who want a -1/0/+1 result would easily miss the
   conversion and write it manually anyway.  (This is a problem of
   documentation and of most people reading about what they looked for
   and not looking at the whole page.)

3. Finally, there's the issue of efficiency.  As long as some
   particular choice is the native one and the rest are going via
   conversion, there's much less point in the whole thing.  This is
   very relevant in this case since efficiency is the main point of
   having 3-valued comparison functions -- this is why I said earlier
   that there's a place for an additional `sort' that uses a 3-valued
   comparator, even when it's easy to convert them to boolean ones.

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://barzilay.org/                   Maze is Life!