This page is part of the web mail archives of SRFI 32 from before July 7th, 2015. The new archives for SRFI 32 are here. Eventually, the entire history will be moved there, including any new messages.
From: David Feuer <dfeuer@xxxxxxxxxxxxx> Date: Tue, 23 Jul 2002 10:28:50 -0400 (EDT) DOH! I finally understood an earlier comment someone else made about <= being worse for stable sorting. This is because with a partial rather than total order, (< x y) !=== (not (<= y x)), but rather (< x y) === (and (<= x y) (not (<= y x))) It seems plausible that this is why CL did what it did. Probably more efficient... Well... I don't think that any of these sorting algos are going to do something interesting when given a partial order, even the stable algos. Consider insertion sort, which is going to swap pairs ... x y ... when y < x. Suppose we're using a partial order and there's an adjacent pair ... x y ... that are incomparable. They won't get swapped. But y might nonetheless be less than some item occuring to the left of x. Too bad -- you don't swap y & x, so you never move it left into adjacency with that item for the comparison to be made. So when your insertion sort is done, you really can't conclude much of anything at all about your result data set. (You'd *like* to be able to conclude something like "the result is *a* topological-sort linearisation of the data by partial order <." But you can't.) Ok, so worrying about partial orders is a snare & a delusion. We don't have to stress out about them; that's not a game we can win. Have I made a mistake in my reasoning? Does that all make sense? I received a reply from Kent Pitman, one of the two most knowledgeable Common Lisp gurus in the world, about Common Lisp's use of <. He basically said it was for no compelling technical reason, possibly just backward compatibility with CL. I'm appending Kent's mail to this msg for the record. In summary: - I don't see a compelling technical reason to use one over the other. - It is clear, however, that a uniform convention must be adopted. - The convention in wide, if not universal use, today is <. - The only downside of < is that the English defn of "sorted" with <= is a little simpler (not quite so much nested negation in the statement). So I'm going to stick with <. -Olin ------------------------------------------------------------------------------- Date: Tue, 23 Jul 2002 09:49:27 -0400 From: Kent M Pitman <pitman@xxxxxxxxxxxxx> To: shivers@xxxxxxxxxxxxx In-reply-to: <200207210330.g6L3U7J27168@xxxxxxxxxxxxxxxxxx> (shivers@xxxxxxxxxxxxx) Subject: Re: sorting comparison function -- < vs. <= Date: Sat, 20 Jul 2002 23:30:07 -0400 From: shivers@xxxxxxxxxxxxx [Sorry about the slow reply.] I'm designing a sorting library spec for Scheme. You must decide if you do such a thing if your functions take a < comparison function or a <= function; it affects stability. It seems to me the two choices are interconvertible: < is (lambda (x y) (not (<= y x))) <= is (lambda (x y) (not (< y x))) I see no real reason to settle on one as opposed to the other. Common Lisp chose <. I am wondering why. Do you know? I suspect the choice comes through from Maclisp compatibility. Looking at the Maclisp manual, I don't see a <=, >=, or /= [for fixnums and flonums]. (I'm looking at online text that presently has no index, so I may be missing something.) I _believe_ those were added in Common Lisp. I remember being surprised in CL by the choice of /= rather than != ... (Maclisp also had GREATERP, LESSP, and EQUAL for bignums, but had nothing like NGREATERP nor NOT-GREATERP nor LESS-THAN-OR-EQUAL-P.) (When designing ISLISP, there was some similar push by some to not have all 6 comparison operators. I thought this foolish, and grumbled some, but didn't put my foot down until the same people didn't want to include TAN (figuring SIN and COS were "enough"). I believe ISLISP ended up with TAN and with all 6 comparison functions, though I'm too lazy to look right now to be sure. Phew...)