我有以下一段代码:
(defun list-append (L1 L2)
"Appending L1 by L2."
(if (null L1)
L2
(cons (car L1) (list-append (cdr L1) L2))))
(defun list-reverse (L)
"Create a new list containing the elements of L in reversed order."
(if (null L)
nil
(list-append (list-reverse (cdr L))
(list (car L)))))
当我运行以下命令时:
(list-reverse '(a (b c) ((l k (t)) h i)))
我得到的输出是:
(((L K (T)) H I) (B C) A)
然而，我正试图让它打印出列表及其子列表反向，如:
((I H ((T) K L)) (C B) A)
有什么建议，我将如何修改代码来做到这一点?
这是一种并不可怕的方法。特别是对前一个问题的公认解决方案在算法上是可怕的:任何倒转列表的方法都说:"要倒转一个(可能很长的列表)，首先倒转它的cdr，然后附加car应该会让你皮肤发痒:这种方法就是为什么"lisp很慢"。其他两个答案更好，但都显式地改变状态(这很好，但可能并不总是在教学上很好)。
所以这里有一个答案:是功能性的(不改变状态)，并使用一个不可怕的算法。
首先，假设我们有一个叫做reverse-thing的函数，它会对一个"东西"进行适当的反转，这意味着:如果它是一个列表，就反转它，如果它不是一个列表，就不要。有了这个函数，我们就可以算出一个算法，将一个列表倒转到另一个列表上:
将一个列表反转到另一个列表
- 如果列表为空，则返回要反转到 的列表
- 否则，将列表的其余部分反转到通过将列表的第一个
reverse-thing与我们正在反转到的列表连接而成的列表中。
转换成函数非常简单:
(defun reverse-onto (list onto)
(if (null list)
onto
(reverse-onto (rest list)
(cons (reverse-thing (first list))
onto))))
所以这个函数需要reverse-thing的定义，这样它才能做功。这是怎么实现的呢?
翻转一件事:
- 如果它是一个列表，那么使用
reverse-onto将其反转到()，空列表; - 如果它不是一个列表，则原样返回。
同样，这很容易变成一个函数:
(defun reverse-thing (thing)
(if (listp thing)
(reverse-onto thing '())
thing))
我们完成了:reverse-thing就是我们要写的函数。
注意，这些函数永远不会改变任何东西，也永远不会超越它们在每一步中反转的列表的第一个缺点:这里没有"将这个东西追加到这个大列表的(副本)"。还请注意，reverse-into是尾部递归的，因此在优化尾部调用的实现中(不是标准所要求的)，堆栈的数量将与嵌套深度成正比，而不是与列表长度成正比。