<= and < and partial orders and Common Lisp

[shivers@xxxxxxxxxxxxx]

    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...)