scheme - 为什么这个打印是反的？

Question

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items nil))

当我进入

(square-list (list 1 2 3 4))

它返回 (16 9 4 1) - 为什么会倒退？

Answer 1

您正在使用尾递归构造输出列表，为此，您answer通过附加到列表的头部来累积。自然地，这将产生一个反向列表。你有几个选项可以解决这个问题，一个是放弃尾递归：

(define (square-list items)
  (if (null? items)
      nil
      (cons (square (car items))
            (square-list (cdr items)))))

其他，在处理之前反转列表：

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter (reverse items) nil))

还有另一种选择：在末尾附加元素，而不是使用它们：

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (append answer
                      (list (square (car things)))))))
  (iter items nil))

但是，每个选项都有自己的取舍：

• 第一个选项不是尾递归（尽管它是尾递归模 cons）
• 第二个选项需要一个额外的遍历和一个额外的列表（当列表反转时会发生这种情况）
• 第三个选项是二次的，因为每个追加操作都会遍历列表以在末尾添加元素

考虑到所有因素，最好的尾递归选项将是第二个。

Answer 2

问题是你的cons陈述。如果您从以下位置切换订单：

(cons (square (car things)) answer)

到：

(cons answer (square (car things)))

您的列表将按照您想要的顺序出现。

我总是觉得这样写要容易得多：

(define (square-list2 items)
  (square-list-helper items '())
)

(define (square-list-helper items squares)
  (cond
    [(empty? items) squares]
    [else (append 
             squares 
             (square-list-helper (cdr items) (list (square (car items)))))]
    )
 )

Answer 3

看两个元素的简单案例：

(square-list '(2 3))

这导致：

(iter '(3)
      (cons (square 2) nil))

==

(iter '(3) '(4))

然后递归调用：

(iter '()
      (cons (square 3) '(4))

==

(iter '() '(9 4))

然后这将调用 的基本情况iter，它只返回answer。

所以它正向遍历列表，但是在处理每个元素时，正方形被放在列表的前面，answer所以结果是向后构建的。

简单的解决方法是更改(cons (square (car things)) answer)​​为：

(append answer (list (square (car things))))

这会将新结果放在末尾而不是开头。然而，这通常被认为是一种糟糕的方法，因为它每次都必须重建结果列表，复制 O(n) 个元素。

Answer 4

您的 cons-ing 顺序错误：首先是递归处理的列表的其余部分，然后是处理当前元素的结果。这将在处理它的同时反转您的列表。试试这个：

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
      answer
      (iter (cdr things)
            (append answer (list (square (car things)))))))
(iter items (list)))