lisp - 如何在 LISP 中反转列表及其子列表的元素？

问题描述

我有以下代码：

(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)

关于如何修改代码来做到这一点的任何建议？

标签： lispcommon-lispclisp

这是一种不可怕的方法。特别是上一个问题的公认解决方案在算法上是可怕的：任何反转列表的方法都说：'反转一个（可能很长的列表），首先反转它的 cdr 然后将汽车附加到应该让你的皮肤痒：这种方法就是为什么“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是尾递归的，因此在优化尾调用的实现中（标准不要求），堆栈的数量将与嵌套深度而不是列表长度成正比。

lisp - 如何在 LISP 中反转列表及其子列表的元素？

问题描述

解决方案

推荐阅读