insert - 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 中的局部函数。

但是，关于您的代码还有其他几点要说:

• 您不必因为担心与函数 list 发生冲突而将变量重新拼写为 lst:在 Common Lisp 中，函数和变量位于不同的命名空间中。
• 通常的做法是将模式 (if (null list) list (...)) 简化为 (and list (...)) 因为 if (null list)为真，则list必须为nil!
• 您的参数 key 的命名有误:key 函数接受列表项并返回用于比较的键 (see the HyperSpec on sort)。这里的内容(比较两个项目的函数)称为“谓词”。
• 当您使用 (if ... (if ...)) 模式时，如果您使用 cond 通常会更清楚。
• 没有文档字符串!

无论如何，解决所有这些小问题，并使用标签，结果如下:

(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 参数传递给它，因为内部函数从封闭的上下文中获取绑定(bind)。