how to write a 'destructive' dolist macro in lisp

I am trying to write a simple bubble sort in Common Lisp (also works in Emacs Lisp), in a most intuitive way:

(defun bubble-sort-long (list)
  (labels ((rec (list acc)
                (if (null list) (nreverse acc)
                    (progn
                      (dolist (x (cdr list))
                        (if (< x (car list))
                            (rotatef x (car list))))
                      (rec (cdr list) (push (car list) acc))))))
           (rec list nil)))

This doesn't work. Because rotatef only swap the value of temporary variable x and (car list), instead of the compared element in the list. Trace result goes as follows:

>(setf a '(1 3 2 5 4))
>(trace bubble-sort)
>(bubble-sort a)
  0: (BUBBLE-SORT-LONG (1 3 2 5 4))
  0: BUBBLE-SORT-LONG returned (1 2 2 4 4)

I guess the most direct way to tackle would be defining a 'destructive' dolist macro which assign a x which directly point to the iterated element in the list. Something like a ndolist, so that I can make the following work:

(setf a '(1 2 3))
(ndolist (x a)
  (setf x (+ 1 x)))  

would produce: (2 3 4).

In addition, if you can provid开发者_如何转开发e more intuitive thoughts on bubble sorting using lisp, please also give a hint.

In ruby, similar algorithm would be something like:

class Array
  def bubble_sort
    self.each_with_index do |a,j|
      i=j+1
      while i<self.length
        if (self[j]>self[i])
          self[j],self[i]=self[i],self[j]
        end
        i=i+1
      end
    end
  end

What is fun is I still have to use the "parallel assignment" to swap the value. Ruby doesn't support(encourage) swap using temporary variable through reference in C/C++ style.

Regarding your original question: so you want a dolist variant which doesn't just bind an iteration variable to the provided name, but instead makes it a place. It should be possible to do it by expanding that macro into a loop over a symbol-macrolet which will expand the name into a different place form for each iteration step.

Regarding the bubble sort implementation: bubble sort is terribly inefficient anyways, so bothering with tail recursion is a waste of energy. You could choose a better algorithm if you cared for efficiency at all, bubble sort is only for demonstration purposes, so instead you should stick to pseudo code implementations as close as possible. Here is a lisp implementation that does that:

(defun bubble-sort (seq)
  (loop for n from (length seq) downto 2 and swapped = nil
     do (dotimes (i (1- n))
          (when (> (elt seq i) (elt seq (1+ i)))
            (rotatef (elt seq i) (elt seq (1+ i)))
            (setf swapped t)))
     while swapped))

Another benefit of this implementation is that it's using the sequence protocol, so it will work with both lists and vectors (one-dimensional arrays).

EDIT: As discussed in the comments, using the random access operations of the sequence protocol on lists is very inefficient, so here's a version that avoids them (which has the drawback that it won't work on vectors any more):

(defun list-bubble-sort (list)
  (when list
    (loop with result = ()
       for swapped = nil
       do (let ((x (car list)))
            (setf list (loop for y in (cdr list)
                          when (> x y) collect y and do (setf swapped t)
                          else collect x and do (setf x y)))
            (push x result))
       unless (and list swapped) return (append list result))))

This version returns the sorted list and doesn't mutate the original one.

There are a few problems with this. It is also not that easy.

I'll give you a few hints:

• a variable points to a value, not a place. Modifying a variable will never change another place or another variable.

• You can exchange the first and second item of a list like this (rotatef (first list) (second list))

• Never change a literal list in code - that's a constant. If you destructively change lists, use a consed list (for example created by COPY-LIST or LIST or ...).

• There are two versions of BUBBLE-SORT we can think of: one is destructive and the other not.

• I would also replace the tail-recursive function with a loop. In Scheme you would use a tail recursive function, in Common Lisp mostly not.

Finally I found this:

(defmacro dolist* ((iterator list &optional return-value) &body body)
  "Like DOLIST but destructuring-binds the elements of LIST.

If ITERATOR is a symbol then dolist* is just like dolist EXCEPT
that it creates a fresh binding."
  (if (listp iterator)
      (let ((i (gensym "DOLIST*-I-")))
        `(dolist (,i ,list ,return-value)
           (destructuring-bind ,iterator ,i
             ,@body)))
      `(dolist (,iterator ,list ,return-value)
         (let ((,iterator ,iterator))
           ,@body))))