如何在Lisp代码中消除冗余？

Question

如何在Lisp代码中消除冗余？

6

我尝试在Common Lisp中实现快速排序，以下是我的成果：

(defun quick-sort (list)
  (if (cdr list)
    (let ((pivot (car list)))
      (append (quick-sort (remove-if-not (lambda (n) (< n pivot)) list))
              (remove-if-not (lambda (n) (= n pivot)) list)
              (quick-sort (remove-if-not (lambda (n) (> n pivot)) list))))
    list))

显然，它可以工作，但我认为这段代码中有太多的重复。基本上，我们有三次:

(remove-if-not (lambda (n) (< n pivot)) list)

唯一区别这三个调用的方法是使用 >、= 或者 <。

因此我的问题是：如何消除冗余并使代码更易读、更紧凑？

当然我可以将一些东西提取到一个函数中，例如：

(defun which (operator pivot list )
  (remove-if-not (lambda (n) (funcall operator n pivot)) list))

(defun quick-sort (list)
  (if (cdr list)
    (let ((pivot (car list)))
      (append (quick-sort (which #'< pivot list))
              (which #'= pivot list)
              (quick-sort (which #'> pivot list))))
    list))

但我并不确定这是否是最佳方法。反复交换 pivot 和 list 仍然感觉有些笨拙。

我还想使用 flet，它使函数的实际体更易读，但只是将复杂性转移到其他地方：

(defun quick-sort (list)
  (if (cdr list)
    (let ((pivot (car list)))
      (flet ((left () (remove-if-not (lambda (n) (< n pivot)) list))
             (middle () (remove-if-not (lambda (n) (= n pivot)) list))
             (right () (remove-if-not (lambda (n) (> n pivot)) list)))
        (append (quick-sort (left))
                (middle)
                (quick-sort (right)))))
    list))

有其他的方法吗？

- Golo Roden

看看肯特·皮特曼在Sheep Trick中描述的Lisp快速排序实现。 - Joshua Taylor

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rainer Joswig · Accepted Answer

如果你将它写成本地函数，你就不必传递额外的参数，因为它们在作用域内。

(defun quick-sort (list)
  (if (rest list)
      (let ((pivot (first list)))
        (flet ((filter (operator)
                 (remove-if-not (lambda (n) (funcall operator n pivot)) list)))
          (append (quick-sort (filter #'<))
                  (filter #'=)
                  (quick-sort (filter #'>)))))
    list))

稍微紧凑一些的版本：

(defun quick-sort (list &aux (pivot (first list)))
  (flet ((filter (operator)
           (remove-if-not (lambda (n) (funcall operator n pivot)) list)))
    (and list
         (nconc (quick-sort (filter #'<))
                (filter #'=)
                (quick-sort (filter #'>))))))

由于Common Lisp支持多值，因此您还可以在一个函数中一次性对列表进行分区，并将列表作为值返回：

(defun partition (list pivot)
  (loop for e in list
        when (< e pivot) collect e into smaller else
        when (> e pivot) collect e into larger else
        when (= e pivot) collect e into same
        finally (return (values smaller same larger))))

(defun quick-sort (list)
  (if (rest list)
      (multiple-value-bind (smaller same larger)
          (partition list (first list))
        (append (quick-sort smaller) same (quick-sort larger)))
    list))

当列表是新分配的时，就可以使用NCONC。由于REMOVE-IF-NOT是非破坏性的（与DELETE-IF-NOT相比），所以使用NCONC是可以的。由于LOOP收集新的列表，再次使用NCONC也是可以的。这是一个实际的向量原地快速排序算法。请注意，Quicksort确实是这样设计的。使用列表的版本并不真正是Quicksort。

(defun partition (array left right &aux (i (1- left))
                                        (j right)
                                        (v (aref array right)))
  (loop do (loop do (incf i) until (>= (aref array i) v))
           (loop do (decf j) until (or (zerop j)
                                       (<= (aref array j) v)))
           (rotatef (aref array i) (aref array j))
        until (<= j i))
  (rotatef (aref array j) (aref array i) (aref array right))
  i)

(defun quicksort (array &optional (left 0) (right (1- (length array))))
  (if (> right left)
    (let ((i (partition array left right)))
      (quicksort array left (1- i))
      (quicksort array (1+ i) right))
    array))

此版本基于Sedgewick的代码。