Lisp中的Quicksort奇怪的行为？

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就好像它们是局部变量一样,在每次递归调用时使用不同的值进行实例化,而在不同的递归调用之间进行全局分配调用,产生不正确的结果.

有关该主题的更全面的讨论,请参阅优秀的书籍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))