插入式通用插入句

Question

我想用此INSERT函数在common-lisp中实现排序功能R表示带有key（int）和value（任何类型）的cons单元格，L表示我要将R插入其中的列表。有了这个功能，我可以用（＆（1 AA）（10 1192）（20 CC））

创建一个带有键和值的cons-cell列表。

(defun INSERT (L R)  (IF (eq L nil) (cons (cons(car R)(cdr R)) nil)
    (IF  (eq (cdr L) nil)
          (IF (< (car R)(caar L))  (cons (cons(car R)(cdr R)) L)
            (cons (car L)  (cons (cons(car R)(cdr R)) (cdr L)) )
          )
        (cond 
            (    (eq (< (caar L) (car R)) (< (car R) (caadr L)) ) 
               (cons  (car L)  (cons (cons (car R) (cdr R))  (cdr L))  )   )
            (t (cons (car L) (INSERT (cdr L) R))  )))))

而我想要的是下面这个函数的代码。它只有一个参数L（非排序列表）

(defun Sort_List (L)(...this part...))

不使用（set，setq，setf）指令，也不使用INSERT函数

Answer 1

您的insert功能非常奇怪。实际上，我很难读懂，除了不需要检查列表是否为空和]其cdr为空之外，我什么都不做。它还会消耗掉很多不需要的东西，除非问题规范的某些部分要求您复制要插入的conses。

这里是一个版本，它更易于阅读，不需要时不会复制。请注意，这将其参数以与您的参数相反的顺序：

(defun insert (thing into)
  (cond ((null into)
         (list thing))
        ((< (car thing) (car (first into)))
         (cons thing into))
        (t (cons (first into)
                 (insert thing (rest into))))))
现在，插入排序的算法是什么？好吧，本质上是：

• 循环遍历要排序的列表：
  • 对于每个元素，将其插入排序列表中；
  • 最终返回排序后的列表。

而且我们不允许使用分配来执行此操作。

嗯，做这种事情有一个标准的技巧，那就是使用带有accumulator

参数的尾递归函数，该函数会累加结果。我们可以将此函数编写为显式辅助函数，也可以将其设置为局部函数。我将做后者，这是因为没有理由只在本地使用该函数才能全局可见，并且因为（因为我假设这是家庭作业）因此很难直接提交）。

所以这是此功能的版本：

(defun insertion-sort (l)
  (labels ((is-loop (tail sorted)
             (if (null tail)
                 sorted
               (is-loop (rest tail) (insert (first tail) sorted)))))
    (is-loop l '())))
此方法在Scheme中很自然，但在CL中不是很自然。至少不显式使用分配的一种替代方法是使用do。这是使用do的版本：

(defun insertion-sort (l)
  (do ((tail l (rest tail))
       (sorted '() (insert (first tail) sorted)))
       ((null tail) sorted)))
关于此版本有两个注释。

• 首先，虽然不是explicitly使用赋值，但显然可以隐式地这样做。我认为那可能是作弊。
• 其次它起作用的原因有些微妙：确切地，tail中(insert (first tail) sorted)的值是什么，为什么？

一个更清晰但使用loop的版本，您可能不打算知道它，是

(defun insertion-sort (l)
  (loop for e in l
        for sorted = (insert e '()) then (insert e sorted)
        finally (return sorted)))
但是，这也很明确地使用赋值。