как написать «разрушительный» макрос dolist в lisp

Question

Я пытаюсь написать простую пузырьковую сортировку в Common Lisp (также работает в Emacs Lisp) наиболее интуитивным способом:

(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)))

Это не работает. Потому что rotatef заменяет только значение временной переменной x и (список автомобилей) вместо сравниваемого элемента в списке. Результат трассировки выглядит следующим образом:

>(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)

Полагаю, что самым прямым способом решения этой проблемы было бы определение «деструктивного» макроса dolist, который присваивает x, который непосредственно указывает , на повторяющийся элемент в списке. Что-то вроде ndolist, так что я могу сделать следующую работу:

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

даст: (2 3 4).

Кроме того, если вы можете дать более интуитивные мысли о сортировке пузырьков с помощью lisp, пожалуйста, дайте намек.

В ruby ​​подобный алгоритм будет выглядеть примерно так:

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

Что забавно, я все еще должен использовать «параллельное назначение», чтобы поменять значение. Ruby не поддерживает (поощряет) свопинг с использованием временной переменной через ссылку в стиле C / C ++.

Answer 1

Относительно вашего исходного вопроса: вам нужен вариант dolist, который не просто привязывает переменную итерации к предоставленному имени, но вместо этого делает его местом.Это должно быть возможно сделать, развернув этот макрос в цикле по symbol-macrolet, который расширит имя в другую форму места для каждого шага итерации.

Относительно реализации пузырьковой сортировки: пузырьковая сортировка ужаснав любом случае, неэффективно, поэтому использование хвостовой рекурсии - пустая трата энергии.Вы могли бы выбрать лучший алгоритм, если бы вообще заботились об эффективности, пузырьковая сортировка предназначена только для демонстрационных целей, поэтому вместо этого вам следует придерживаться реализаций псевдокода как можно ближе.Вот реализация lisp, которая делает это:

(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))

Другое преимущество этой реализации состоит в том, что она использует протокол последовательности, поэтому она будет работать как со списками, так и с векторами (одномерные массивы).

РЕДАКТИРОВАТЬ: Как обсуждалось в комментариях, использование операций произвольного доступа протокола последовательности в списках очень неэффективно, поэтому вот версия, которая их избегает (у которой есть недостаток, что она больше не будет работать с векторами):

(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))))

Эта версия возвращает отсортированный список и не изменяет первоначальный список.

Answer 2

Есть несколько проблем с этим. Это тоже не так просто.

Я дам вам несколько советов:

• переменная указывает на значение, а не на место. Изменение переменной никогда не изменит другое место или другую переменную.

• Вы можете обменять первый и второй элемент списка следующим образом: (rotatef (first list) (second list))

• Никогда не меняйте буквальный список в коде - это константа. Если вы деструктивно меняете списки, используйте ограниченный список (например, созданный с помощью COPY-LIST или LIST или ...).

• Есть две версии BUBBLE-SORT, о которых мы можем думать: одна разрушительна, а другая нет.

• Я бы также заменил хвостовую рекурсивную функцию на цикл. В Схеме вы бы использовали хвостовую рекурсивную функцию, в Common Lisp чаще всего нет.

Answer 3

Наконец я нашел это:

(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))))