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

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

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