Lisp插入排序问题

Question

使用插入来编写一个函数sort1，它将整数列表按递增顺序排序。 [如果列表为零，我们就完成了。否则，插入目录的车开进了一个排序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内的本地函数。

还有一些其他的东西，说你的代码，但是：

• 你不需要respell变量作为lst生怕与功能list碰撞：在Common Lisp的函数和变量生活在不同的命名空间。
• 通常的做法是将(if (null list) list (...))的模式简化为(and list (...))，因为如果(null list)为true，那么list必须为nil！
• 您的论点key是错误的：key功能是一个需要列表项并返回一个用于比较的键（see the HyperSpec on sort）。你在这里（一个比较两个项目的函数）被称为“谓词”。如果您使用cond，则通常会更清晰。
• 没有文档字符串！

反正，修复所有那些次要的niggles，并使用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参数传递给它作为内部函数从封闭的上下文中获取绑定。