如何在 Scheme 中反转列表？

Question

(define (list-without-last-pair items)
  (let ((s (cdr items)))
    (if (null? s)
    null
    (cons (car items)
          (list-without-last-pair s)))))

(define (only-last-pair items)
  (let ((s (cdr items)))
    (if (null? s)
        (car items)
        (only-last-pair s))))

(define (reverse items)
  (if (null? items)
       null
       (cons (only-last-pair items)
             (reverse (list-without-last-pair items)))))

我的主方法和辅助方法中有很多代码重复。如何避免这种情况并改进解决方案？

预期输出：(reverse (list 1 2 3)) => (3 2 1)

Answer 1

如果您使用通常的 car 和 cdr 过程处理列表，您可以从 从前到后 处理它。使用 cons 构建列表是从 从后到前 构建它。所以你可以结合这两种行为来反转列表；只需查看列表，然后 cons 将 car 放入累加器：

(define (reverse lst)
  (let loop ((lst lst) (acc null))
    (if (null? lst)
        acc
        (loop (cdr lst) (cons (car lst) acc)))))

请注意 loop 不是预定义过程或关键字（与 Common Lisp 相对），而只是我为内部过程选择的名称；以上代码与

相同

(define (reverse lst)
  (define (loop lst acc)
    (if (null? lst)
        acc
        (loop (cdr lst) (cons (car lst) acc))))
  (loop lst null))

或者，如果您想避免使用 2 个过程，您可以使用具有默认值的可选参数：

(define (reverse lst (acc null))
  (if (null? lst)
      acc
      (reverse (cdr lst) (cons (car lst) acc))))

Answer 2

很少将列表的 "back end" 用于任何事情，它既低效又容易导致相当复杂的代码（如您所见）。

为了反转列表，您可以保存第一个元素，反转其余元素，然后将旧的第一个元素放在 "reversed rest" 的后面。
（这与您正在做的相同，但在列表的另一端。）

即

(define (reverse lst)
    (if (null? lst)
        lst
        (append (reverse (cdr lst)) (list (car lst)))))

尽管这样效率很低，所以通常您会使用 tail-recursive 版本（SICP 中的 "iterative process"）。

如果将 tail-recursive 的实现分解为一个主函数和一个 "helper":

，那么它的实现可能最容易理解

(define (reverse-helper lst acc)
  (if (null? lst)
      acc
      (reverse-helper (cdr lst) (cons (car lst) acc))))

(define (reverse lst)
  (reverse-helper lst '()))

主要区别是在acc参数中构建结果意味着我们可以使用cons而不需要重复遍历结果在它后面添加东西（这是append 做什么）。

Answer 3

定义 reverse 就像使用 cons

将现有列表折叠到新的空列表一样简单

(define (reverse xs)
  (foldl cons '() xs))

要了解它的工作原理，请评估折叠

(reverse '(1 2 3)) ;; ⇒ ?

;; first iteration
(cons 1 '()) ;; ⇒ '(1)

;; second iteration
(cons 2 '(1)) ;; ⇒ '(2 1)

;; third iteration
(cons 3 '(2 1)) ;; ⇒ '(3 2 1)

在您的评论中，您询问了如何实施 foldl

(define (foldl f y xs)
  (if (empty? xs)
      y
      (foldl f
             (f (car xs) y)
             (cdr xs))))

如果您不熟悉折叠，我认为使用 sum 函数进行演示是最简单的。

如果你想对一列数字 1 2 3 4 求和，你会怎么做？大概是这样的

1 + 2 + 3 + 4

你看到每个之间的 + 了吗？让我们看看我们如何评价这个

((1 + 2) + 3) + 4
(3 + 3) + 4
6 + 4
⇒ 10

好吧，foldl 正是这样做的。它需要一个二进制过程、一个初始值和一个列表。在我们的例子中，我们将使用过程 + 和 0 的初始值进行演示。这次我们将使用 s-expressions（(+ x y) 而不是中缀 x + y）

来显示评估

(foldl + 0 '(1 2 3 4))
(+ 4 (+ 3 (+ 2 (+ 1 0))))
(+ 4 (+ 3 (+ 2 1)))
(+ 4 (+ 3 3))
(+ 4 6)
⇒ 10

这个初始值很重要，因为如果输入是一个空列表，我们需要知道返回什么样的值

(foldl + 0 '())
;; ⇒ 0

所以，让我们根据折叠

定义sum

(define (sum xs) (foldl + 0 xs))
(sum '(1 2 3 4)) ;; ⇒ 10
(sum '())        ;; ⇒ 0

我们很容易理解求和，因为它们对我们来说太熟悉了，但是 reverse 过程可能不太清楚。折叠减少为单个值，在我们的例子中，我们将输入列表减少为单个输出列表。

让我们快速回顾一下 sum 评估。记住我们折叠的过程是 + 并且初始值是 0

(foldl + 0 '(1 2 3 4))
(+ 4 (+ 3 (+ 2 (+ 1 0))))
(+ 4 (+ 3 (+ 2 1)))
(+ 4 (+ 3 3))
(+ 4 6)
⇒ 10

现在让我们看看写出的reverse评价。这里我们折叠的过程是 cons 并且初始值是 '() （空列表）

(foldl cons '() '(1 2 3))
(cons 3 (cons 2 (cons 1 '())))
(cons 3 (cons 2 '(1)))
(cons 3 '(2 1))
⇒ '(3 2 1)

如何在 Scheme 中反转列表？

How to reverse list in Scheme?

algorithm

scheme