Re: MCL 2.0b1p3 sort problems

[William.Woods@East.Sun.COM (Bill Woods - Sun BOS)]

Bill,
I sent my previous note before seeing yours.  I'd forgotten that 1.3.2
did sorting in what I (and apparently Adnan Hamid) consider the "right"
way.  It'd be a shame to lose that nice feature in 2.0.  (It'd be much
nicer to get it into the common lisp standard.)  Your consing version
is an easy way to get the desired behavior at the expense of one cons
per sort (which is not too bad).  However, it is possible to get the
behavior with no consing at all.  One way to do this is to simply
retain a pointer to the root cell of the input list and keep track
of the cell whose cdr points to it as you proceed with the sort (this
will change as you move things around in the sort, so it costs a few
instructions to track it). You of course also keep track of the cell that
contains the first element of the resulting sorted list, which you would
otherwise return as the answer.  Call this the answer cell.  Then,
just before you exit the sort algorithm, you interchange the contents of
the root cell and the answer cell (using a local variable to hold the
temporary information needed during the exchange) and you change the cdr
of the cell that pointed to the root cell to point to the answer cell
(which now contains the root cell's contents).  The root cell, which now
contains the former contents of the answer cell, is returned as the answer.
(There are other ways to achieve the same effect, e.g., by always using
the root cell as the place to put the earliest element of the list as
the sorting algorithm proceeds.)

A user could do this himself using a dumb destructive sort only at the
cost of an extra pass through the resulting list to find the cell that
points to the root cell so he can change its cdr (probably a steep price
to pay to save one cons).  Hence, it's much nicer if the sort routine
does this for you.

If this removes your reluctance to do destructive sort the "right" way
(the other way is never useful, just simpler to implement), perhaps
it could be put back into 2.0.  If so, I would consider it a much nicer
product. (And it's not inconsistent with the common lisp standard, just
more useful than some of the less clever things that also fit the same
specification.)

Bill Woods



	From bill@cambridge.apple.com Wed Jul 10 10:46:45 1991
	From: Bill St. Clair <bill@cambridge.apple.com>
	To: Adnan Hamid <ahamid@clarity.Princeton.EDU>
	Cc: info-mcl@cambridge.apple.com
	Subject: Re: MCL 2.0b1p3 sort problems 
	
	   Date: Wed, 10 Jul 91 02:33:31 EDT
	   From: Adnan Hamid <ahamid@clarity.Princeton.EDU>
	   To: info-mcl@cambridge.apple.com
	   Subject: MCL 2.0b1p3 sort problems
	   
	   According to my copy of Steel, (sort <sequence> <predicate>) *distructively* 
	   sorts the sequence that it is given.  One presumes that the following behaviour
	   is incorrect:
	   
	   Welcome to Macintosh Common Lisp Version 2.0b1p3!
	   ? (setq foo '(1 2 3))
	   (1 2 3)
	   ? (sort foo #'>)
	   (3 2 1)
	   ? foo
	   (1)
	   ? 
	   
	CLtL Second Edition p. 408 states:
	
	"The sorting operation may be destructive in all cases.  In the case
	of an array argument, this is accomplished by permuting the elements
	in place.  In the case of a list, the list is destructively reordered
	in the same manner as for NREVERSE. Thus if the argument should not be
	destroyed, the user myst sort a copy of the argument."
	
	The SORT in MCL 1.3.2 preserved the initial cons when sorting so that
	it still pointed at the sorted list (the rest of whose conses were
	completely reordered).  It did this at the expense of consing, however.
	
	If you like this behavior, you can easily do it yourself:
	
	(defun consing-sort (sequence predicate &key key)
	 (if (and sequence (listp sequence))
	   (let ((first-cons sequence)
	         (res (sort (cons (car sequence) (cdr sequence)) predicate
	                    :key key)))
	     (setf (car first-cons) (car res)
	           (cdr first-cons) (cdr res))
	     first-cons)
	   (sort sequence predicate :key key)))