Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!ai.etl.army.mil!hoey
From: hoey@ai.etl.army.mil (Dan Hoey)
Newsgroups: comp.lang.lisp
Subject: Re: Kyoto Common LISP bug (SORT function)
Summary: Sort is destructive, but not predictably destructive on lists
Keywords: Nonbug, Nonbug, Nonbug
Message-ID: <116@ai.etl.army.mil>
Date: 10 Jun 88 20:19:03 GMT
References: <10988@cgl.ucsf.EDU>
Reply-To: hoey@ai.etl.army.mil (Dan Hoey)
Organization: Naval Research Lab, Washington, DC
Lines: 37

In article <10988@cgl.ucsf.EDU> yee@cgl.ucsf.edu (dave yee) writes:
>I think i've found a bug in KCL (Kyoto Common LISP).
It's not a bug.

>Suppose i have a structure...
The presence of a structure is irrelevant.

>     (setq sorted-boxes (sort unsorted-boxes #'< :key'box-item-code))

>well, the function returns the correct value, BUT the original
>list is not sorted, furthermore *elements of the list are missing*!!!

The definition of sort doesn't claim to sort the original list.
It might leave it sorted, but you can't count on it.

>Now, i'm still a beginner, but if this is a feature of KCL i would
>appreciate an explanation as to why.

During the course of any reasonably efficient sorting algorithm, we might
expect the sorted list to be formed, while the original list would not be
the sorted list.  Typically it would be a tail of the sorted list.  Since
it would take extra work to make the original list be the sorted list, KCL
does not waste time doing so.

> Oh, and i should add that i've
>tested this using SUN Common LISP and the problem does *not* exist.

Well, you haven't tested it with all possible lists.  Many sorting algorithms
only exhibit the behavior on large lists.

>Any suggestions?

(when (setq sorted-boxes (sort (copy-list unsorted-boxes) #'<
			       :key 'box-item-code))
  (setf (car unsorted-boxes) (car sorted-boxes)
	(cdr unsorted-boxes) (cdr sorted-boxes)))

Dan