insert - Lisp 插入排序问题

Question

使用 insert 编写一个函数 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 内的本地函数.

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

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

无论如何，解决所有这些小问题，并使用 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它的参数，因为内部函数从封闭的上下文中获取绑定(bind)。