Lisp插入排序问题

Question

使用insert函数编写sort1函数，将整数列表按递增顺序排序。如果列表为nil，我们就完成了。否则，将列表的汽车插入到排序的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命名错误:key函数是一个接受列表项并返回一个键进行比较的函数(参见sort上的HyperSpec)。你这里所拥有的(一个比较两个项的函数)被称为"谓词"。
• 当你有(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参数给它，因为内部函数从封闭的上下文中获取绑定。