Prev: The Erik Naggum cll archive
Next: a defense of ad hoc software development
From: Barry Margolin on 17 Jan 2010 20:23
In article <hitemu$aj$1(a)z-news.wcss.wroc.pl>,
Waldek Hebisch <hebisch(a)math.uni.wroc.pl> wrote:

> Barry Margolin <barmar(a)alum.mit.edu> wrote:
> > In article <hikrkk$m7j$1(a)news.eternal-september.org>,
> > Joshua Taylor <tayloj(a)cs.rpi.edu> wrote:
> >
> > >
> > > Note that the negation, or complement, of dates-in-lists< is not
> > > dates-in-lists>, but rather dates-in-lists>=. If dates-in-lists>= is OK
> > > for your purposes, then you can use COMPLEMENT [1]. E.g.,
> >
> > Unless you're using STABLE-SORT, what difference does it make? It only
> > affects the equivalent list elements, and SORT doesn't specify how
> > they're reordered in the first place.
> >
>
> Using complement is a bug: SORT may depend on predicate giving
> NIL for equal arguments and may do anything for wrong predicate.

True, anything is possible, although it seems like the implementation
would have to go out of its way to notice this and screw up. SORT
shouldn't really care what happens with equal arguments, since it
doesn't guarantee anything about their relative order in the result. As
long as the predicate defines a total ordering, the right thing should
happen.

STABLE-SORT could potentially be confused if the predicate returns true
for both (funcall predicate a b) and (funcall predicate b a). It has to
perform this test, and treat the elements as equal when they both return
NIL. Both returning true means that the predicate doesn't even define a
partial ordering.

--
Barry Margolin, barmar(a)alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
First  |  Prev  | 
Pages: 1 2 3 4 5
Prev: The Erik Naggum cll archive
Next: a defense of ad hoc software development