lisp - Lisp 中的快速排序奇怪的行为？

Question

我设法使我的快速排序功能正常工作，但我很困惑为什么代码的轻微更改会导致该功能表现异常。这是工作代码:

(defun low (mylist)
  (setq result (list))
  (loop
      for x in mylist
      do (if (< x (car mylist))
             (setq result (cons x result))))
  result)

(defun high (mylist)
  (setq result (list))
  (loop
      for x in mylist
      do (if (> x (car mylist))
             (setq result (cons x result))))
  result)

(defun qsort (mylist)
  (if (null mylist)
       nil
       (progn 
         ;(setq l1 (low mylist))
         ;(setq l2 (high mylist))
         (append (qsort (low mylist))
                 (list (car mylist))
                 (qsort (high mylist))))))

但是在 qsort 函数中，如果我尝试将分区存储在 l1 和 l2 中，然后调用 qsort 该函数不再有效:

(defun qsort (mylist)
  (if (null mylist)
      nil
      (progn 
        (setq l1 (low mylist))
        (setq l2 (high mylist))
        (append (qsort l1)
                (list (car mylist))
                (qsort l2)))))

用这个 (qsort (list -3 5 4 3 1 2)) 返回 (-3 1 2)

我知道事先存储分区不是必需的，但为什么这不起作用？

Answer 1

问题是您在 Common Lisp 中使用了不正确的变量——这在大多数实现中都会发出信号:

CL-USER> (defun low (mylist)
           (setq result (list))
           (loop for x in mylist do 
              (if (< x (car mylist)) 
                (setq result (cons x result))))
           result)
;Compiler warnings :
;   In LOW: Undeclared free variable RESULT
LOW

请注意，编译器会向您发出警告，而不是错误，原因有二:

1. 后面可以引入一个名为result的全局变量，函数执行就正确了；

2. (setq x y) 的语义是这样的，如果没有定义变量 x，则 y 的值是分配给符号 x，从某种意义上说，它是一种全局变量。

正是由于这第二个原因，您的函数无法正常工作，因为在您的递归定义中，您正在使用 l1 和 l2 就好像它们是局部变量一样，在每次递归调用时用不同的值实例化，而它们是在不同调用之间全局分配的，从而产生不正确的结果。

有关该主题的更详尽的讨论，例如参见 chapter on variables好书Practical Common Lisp .

解决方案

在使用局部变量之前，您应该使用 let 特殊形式引入局部变量。例如，您可以这样编写函数 low:

(defun low (mylist)
   (let ((result (list)))
     (loop for x in mylist  
        if (< x (car mylist)) 
        do (setq result (cons x result)))
     result))

let 引入了新变量，您稍后可以使用 setq 运算符对其进行赋值。例如，这里是 qsort 的正确版本:

(defun qsort (mylist)
    (if (null mylist) 
        nil
        (let ((l1 (low mylist))
              (l2 (high mylist)))
          (append (qsort l1) (list (car mylist)) (qsort l2)))))

最后，请注意，您可以用这种方式更简洁、更地道地编写函数 low(high 也类似):

(defun low (mylist)
  (loop for x in mylist
     when (< x (car mylist))
     collect x))

最后的说明

您的算法(和我的重写)没有正确排序列表，因为它消除了重复元素(例如尝试将其应用于列表 (7 3 2 2 4 9 1))。

纠正它的一种方法是修改两个辅助函数之一，以便获得所有元素，例如，小于或等于子列表的汽车。以下是生成正确算法的 low 函数的重写:

(defun low (mylist)
  (loop for x in (cdr mylist)
     when (<= x (car mylist))
     collect x))