如何用lisp编写“破坏性”的数字宏
我试图用通用Lisp (也适用于Emacs )编写一个简单的气泡排序，以一种最直观的方式：
(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和(car list)的值，而不是列表中的比较元素。跟踪结果如下：
>(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分配给迭代元素。类似于一个无名氏，这样我就可以做以下工作：
(setf a '(1 2 3))
(ndolist (x a)
(setf x (+ 1 x))) 将产生：(2，34)。
此外，如果你可以提供更直观的想法，使用lisp气泡排序，也请提供一个提示。
在红宝石中，类似的算法应该是：
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++样式的引用)交换。
回答 3
Stack Overflow用户
发布于 2011-04-17 12:53:17
关于您最初的问题:所以您需要一个dolist变量，它不只是将一个迭代变量绑定到提供的名称，而是将其作为一个位置。应该可以通过将该宏展开为symbol-macrolet上的一个循环来实现这一点，该循环将在每个迭代步骤中将名称展开为不同的place表单。
关于气泡排序的实现:不管怎么说，冒泡排序都是非常低效的，所以使用尾部递归是浪费精力。如果您完全考虑效率，那么您可以选择一个更好的算法，气泡排序只是为了演示目的，所以您应该尽可能地使用伪代码实现。下面是一个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))))此版本返回排序列表，不对原始列表进行变异。
Stack Overflow用户
发布于 2011-04-17 08:34:56
这有几个问题。这也不是那么容易。
我会给你一些提示：
- 变量指向值，而不是位置。修改一个变量永远不会改变另一个位置或另一个变量。
(rotatef (first list) (second list)) - Never这样的列表的第一项和第二项可以交换
- ，在代码中更改文字列表--这是一个常量。如果您破坏性地更改列表，请使用已解析的列表(例如，由复制列表或列表或.创建)。
- 有两个版本的气泡排序:一个是破坏性的，另一个不是。
- i还会用循环替换尾递归函数。在方案中，您将使用尾递归函数，在常见的Lisp中，通常不使用.
Stack Overflow用户
发布于 2011-04-24 13:10:30
最后，我发现了这个：
(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))))https://stackoverflow.com/questions/5691882
复制相似问题
腾讯云开发者
