LISP - 反转序列

Lisp - 反转序列

反转序列中元素的顺序是一项常见任务。Common Lisp 为此提供了两个通用函数：reverse（非破坏性）和 nreverse（破坏性）。这些函数适用于各种序列类型，包括列表、向量和字符串。

安全反转：reverse 函数

reverse 创建并返回一个新序列，其中包含与原始序列相同的元素，但顺序相反。原始序列保持不变。

语法

(reverse sequence)

参数

• sequence：要反转的列表、向量或字符串。

返回值

一个与输入类型相同的新序列，包含按相反顺序排列的元素。

示例：反转不同序列类型

;; main.lisp
(let ((original-list '(a b c d e))
      (original-vector #(10 20 30 40 50))
      (original-string "LISP"))

  (format t "Original List: ~a~%" original-list)
  (format t "Reversed List: ~a~%~%" (reverse original-list))

  (format t "Original Vector: ~a~%" original-vector)
  (format t "Reversed Vector: ~a~%~%" (reverse original-vector))

  (format t "Original String: ~a~%" original-string)
  (format t "Reversed String: ~a~%~%" (reverse original-string))

  (format t "Original list is unchanged: ~a~%" original-list))

输出

Original List: (A B C D E)
Reversed List: (E D C B A)

Original Vector: #(10 20 30 40 50)
Reversed Vector: #(50 40 30 20 10)

Original String: "LISP"
Reversed String: "PSIL"

Original list is unchanged: (A B C D E)

破坏性反转：nreverse 函数

nreverse 通过原地修改序列来反转它。这可以更节省内存，但必须极其谨慎地使用，因为它会破坏原始序列结构。

语法

(nreverse sequence)

行为和最佳实践

• 对于列表：nreverse 效率很高。它通过改变每个 cons 单元格的 cdr 来指向前一个单元格。原始列表结构将变得无效。
• 对于向量：nreverse 原地修改向量。
• 对于字符串：你不应该对字符串使用 nreverse。字符串被指定为不可变的，尝试修改字符串会在现代 Lisp 实现中导致错误。
• 黄金法则：只对你刚刚创建且不会在其他任何地方被引用的序列使用 nreverse。一个经典的惯用方法是使用 push（速度很快）构建列表，然后在最后使用 nreverse 来获得所需的顺序。

示例：经典的 push/nreverse 惯用方法

;; main.lisp
(let ((result-list nil)) ; 从空列表开始

  ;; 通过 push 元素来构建列表。这很快，但会倒序构建列表。
  (dotimes (i 5)
    (push (* i i) result-list))

  (format t "List after pushing (reversed order): ~a~%" result-list)

  ;; 现在，使用 nreverse 来纠正顺序。这很安全，因为 `result-list` 是临时的。
  (let ((final-list (nreverse result-list)))
    (format t "Final list after nreverse: ~a~%" final-list)))

输出

List after pushing (reversed order): (16 9 4 1 0)
Final list after nreverse: (0 1 4 9 16)

何时选择 reverse vs. nreverse

• 使用 reverse（安全）：这应该是你的默认选择。它遵循函数式编程原则（无副作用），并防止了一整类 bug。性能开销通常可以忽略不计。
• 使用 nreverse（优化）：仅当你已在热点循环中识别出性能瓶颈，并且能够证明被反转的序列是临时的且未共享时才使用此方法。push/nreverse 惯用方法是最常见且被接受的使用场景。

测试与验证

要真正理解 nreverse 的破坏性，请尝试运行此代码：

(let ((my-list '(1 2 3)))
  (print (nreverse my-list))
  ;; 现在检查 my-list。它的结构已经被改变了！
  (print my-list))

潜在输出

(3 2 1)
(1) ; 原始绑定现在指向一个被破坏的列表片段！