如何在Common Lisp中用cons替换append实现列表及子列表反转？

你用append实现的revert能正确递归反转列表及所有子列表，但直接替换成cons后会产生多层嵌套结构，这是因为append和cons的行为本质不同：

• append是将两个列表的元素扁平拼接，比如(append '(a b) '(c))会得到(a b c)；
• cons是将第一个参数作为单个元素加到第二个参数的头部，比如(cons '(a b) '(c))会得到((a b) c)，这就是你看到嵌套结构的核心原因。

要想用cons实现原函数的效果，核心是模拟append将单个元素追加到列表末尾的行为——原逻辑中append的第二个参数始终是(list (revert (car l)))（单元素列表），因此我们只需要用cons递归完成“元素追加到列表末尾”的操作即可。

解决方案1：使用辅助函数 #

先定义一个用cons实现的追加函数，再替换原函数中的append：

;; 用cons实现：将元素elem追加到列表lst的末尾
(defun append-elem-to-end (lst elem)
  (if (null lst)
      (list elem)  ;; 列表为空时，直接返回包含elem的列表
      (cons (car lst)  ;; 否则递归处理cdr，把elem追加到后面
            (append-elem-to-end (cdr lst) elem))))

;; 改造后的revert函数
(defun revert (l)
  (cond
    ((atom l) l)
    (t (append-elem-to-end (revert (cdr l))  ;; 替换原append的位置
                           (revert (car l))))))

测试验证：

(write (revert '(2 3 5 6 7 8 9 (4 5 (6)))))
;; 输出：(((6) 5 4) 9 8 7 6 5 3 2)，与原函数结果一致

解决方案2：内联辅助逻辑（无额外函数） #

如果不想定义辅助函数，可以直接把追加逻辑内联到revert中：

(defun revert (l)
  (cond
    ((atom l) l)
    ((null (cdr l))  ;; 列表只剩一个元素时，返回反转后的单元素列表
     (list (revert (car l))))
    (t  ;; 递归处理cdr，将当前car的反转结果追加到cdr反转结果的末尾
     (cons (car (revert (cdr l)))
           (revert (cons (cdr (cdr l)) (list (car l))))))))

这个版本的核心是：每次递归时，先取(revert (cdr l))的第一个元素作为当前cons的car，再递归处理剩余的(cdr (cdr l))与当前car组成的新列表，最终实现将当前car的反转结果追加到末尾的效果。

原替换方式失效的原因 #

你直接把append换成cons后，代码变为：

(cons (revert (cdr l)) (list (revert (car l))))

这里(revert (cdr l))是一个完整列表，cons会把它当成单个元素放到新列表头部，而非展开元素进行拼接，因此每次递归都会新增一层嵌套，最终得到全嵌套的异常结果。

内容的提问来源于stack exchange，提问作者Leo