Lisp插入排序问题

Question

使用insert编写函数sort1，该函数将整数列表排序为递增顺序。如果名单是零，我们就完了。否则，将列表的car插入排序的cdr中。

这就是我所做的，我在一个名为sort1的函数中定义这两个函数时遇到了困难：

(defun insert (item lst &optional (key #'<))
  (if (null lst)
    (list item)
  (if (funcall key item (car lst))
          (cons item lst) 
          (cons (car lst) (insert item (cdr lst) key)))))
(defun insertion-sort (lst &optional (key #'<))
  (if (null lst)
    lst
    (insert (car lst) (insertion-sort (cdr lst) key) key)))

Answer 1

将所有内容都定义为一个函数定义的最简单方法是使用labels将函数insert定义为insertion-sort中的一个本地函数。

但是，关于您的代码还有其他几件事要说：

由于担心与函数namespaces.

• It's发生冲突，您不需要将变量作为lst来响应:在通用Lisp函数中，变量存在于不同的公共实践中，以将模式(if (null list) list (...))简化为(and list (...))，因为如果(null list)为真，那么list必须是
• 参数key是错误命名的：key函数是一个获取列表项并返回比较键的函数(see the HyperSpec on sort)。这里您所拥有的(比较两个项的函数)称为"predicate".
• When --您有模式(if ... (if ...)) --如果使用cond.
• No docstring!

，通常会更清楚

总之，修复所有这些小问题，并使用labels，结果如下：

(defun insertion-sort (list &optional (predicate #'<))
  "Return a sorted copy of list. Optional argument predicate must be a function
that takes two items and returns true if they are in order."
  (labels ((insert (item list)
                   (cond ((null list) (list item))
                         ((funcall predicate item (car list))
                          (cons item list))
                         (t (cons (car list) (insert item (cdr list)))))))
    (and list (insert (car list) (insertion-sort (cdr list) predicate)))))

注意，既然insert是insertion-sort的本地函数，我就不必将predicate参数传递给它，因为内部函数从封闭的上下文中获取绑定。