Message from discussion Question about the sort function

Path: g2news2.google.com!news2.google.com!news.glorb.com!sn-xt-sjc-04!sn-xt-sjc-10!sn-xt-sjc-07!sn-post-sjc-01!supernews.com!corp.supernews.com!spamForbidden
From: rem6...@yahoo.com (Robert Maas, see http://tinyurl.com/uh3t)
Newsgroups: comp.lang.lisp
Subject: Re: Question about the sort function
Date: Thu, 11 Oct 2007 02:44:41 -0700
Organization: Nada. All alone here. I wish I ever had a friend for sharing thoughts and feelings.
Message-ID: <rem-2007oct11-003@yahoo.com>
Errors-To: ErrorsToH...@YahooGroups.Com
X-Spam-This: SpamCop...@YahooGroups.Com
References: <joswig-705ECB.00501509102007@news-europe.giganews.com> <1i5okn2.relv2w1mzvtecN%wrf3@stablecross.com> <ufy0lgf4b.fsf@nhplace.com> <1i5ow53.pskscln5nqbmN%wrf3@stablecross.com> <joswig-CF865C.07204209102007@news-europe.giganews.com>
X-Complaints-To: abuse@supernews.com
Lines: 99

> From: Rainer Joswig <jos...@lisp.de>
> It is not intuitive (at least for me) that one sorts a list and
> the variable pointing to that list is not updated to point to the
> sorted list.

In virtually any common programming language, even C, parameters
are passed by value. No assign-back ever occurs. If you write a
function call with a simple variable given in the syntax for a
parameter, what is passed is a copy of the value of that variable,
not a reference to the variable, so there is no way whatsoever that
the function called could update the variable even if it wanted to.

So when you pass a pointer to a structure, such as a sequence, what
is the *object* that is passed? In Java, when you pass a container
containing a whole sequence, generally you pass a toplevel
framework that encapsulates the whole sequence, and you can then
ask some function to rearrange elements, and the toplevel framework
now has the new sequence. But in lisp, when you pass a list to a
function, the thing you pass is just a pointer to a single CONS
cell, whose CAR is the first element of the list, with the rest o
the list daisy-chained onto the CDR of that single CONS cell. If a
function is called to rearrange the list and return a rearranged
list, that original pointer to that original CONS cell still points
to that CONS cell, not to some other CONS cell that is now at the
front of the returned list.

By comparison, an array is a whole object in Lisp, so any function
that rearranges the elements of the array in-place will probably
cause the original pointer-to-array to now point to that same array
which is in fact now in the new ordering.

Now if you encapulated a list in an extra level of structure, and
wrote a function that sorted the list and assigned it back to the
extra level, then you could have the effect you want, for example:
(defun make-encapsulated-list (l)
  (list :EL l))
(defun is-encapsulated-list (el)
  (eq :EL (car el)))
(defun check-encapsulated-list (el)
  (unless (is-encapsulated-list el)
    (error "Invalid argument, not an encapsulated-list: %S" el)))
(defun encapsulated-list-extract (el)
  (check-encapsulated-list el)
  (cadr el))
(defun encapsulated-list-sort (el sortfn)
  (check-encapsulated-list el)
  (setf (cadr el) (sort (cadr el) sortfn))
  el)
(setq l1 (list 3 7 5 1))
(setq el1 (make-encapsulated-list l1)) ;At this point l1 is garbage
(encapsulated-list-sort el1 #'<) ;Container is modified in place, no setq needed
(setq l2 (encapsulated-list-extract el1))

Normally it'd be easier to just remember to do a setq when you call
sort directly. But I can imagine a situation where there are
multiple pointers to a single sequence, and you want that single
sequence sorted once, and then all the references will
automatically share that newly-sorted sequence, especially if you
might want to sort the same sequence per several different sorting
functions and each time have all references immediately share that
newly-resorted sequence, where encapsulating as above (or using
CLOS to create a fullfledged OO-object) might be useful.

An alternative is to write a wrapper around sort which makes sure
the original CONS cell is still at the front of the list, by
swapping CARs between the old head and new head and also swapping
the CONS cells themselves. But the code for that would be *hairy*,
because you have to first find where the old CONS cell is within
the newly sorted list, but actually find the CONS cell just before
it in the sorted list so that its CDR can be modified, and deal
with lots of special cases as to whether the old head-CONS is now
in first or second or third-or-later position. Putting a wrapper
around the whole list and SETFing it inside the wrapper, as I did
above, is so much easier to code correctly, IMO.

But here's my attempt at the messy thing:
(defun sort-keeping-head-cell (oldhead sortfn)
  (let* ((tmphead (sort oldhead sortfn))
         (ix (position (car oldhead) tmphead)))
    (cond ((null tmphead)) ;Empty list, no patch needed
          ((= 0 ix)) ;Same old head, no patch needed
          ((= 1 ix)
           (rotatef (car tmphead) (car oldhead))
           (rplacd tmphead (cdr oldhead))
           (rplacd oldhead tmphead))
          (t (let ((preold (nthcdr (+ -1 ix) tmphead))
                   (postold (cdr oldhead)))
               (rotatef (car tmphead) (car oldhead))
               (rplacd oldhead (cdr tmphead))
               (rplacd preold tmphead)
               (rplacd tmphead postold))))
    oldhead))
(setq l1 (list 3 7 5 1))
(sort-keeping-head-cell l1 #'<) ;IX was 1
l1
(setq l1 (list 7 3 5 1))
(sort-keeping-head-cell l1 #'<) ;IX was 3
l1
;It works! But what a mess to show the person who has check your code for bugs!