Scheme中是否可以创建非尾递归反向列表函数？

Question

我正在尝试反转Scheme中的列表。我想出了这段代码：

(define (rev lst)
  (let loop ((lst lst) (result '()))
    (if (null? lst)
        result
        (loop (cdr lst) (cons (car lst) result)))))

它工作得很好，但我想看看（作为一个实验）我是否可以将其重写为非 TCO，因为非 TCO 通常更容易编写。

我进行了转储重新排列以摆脱累加器：

(define (rev lst)
  (if (null? lst)
      '()
      (cons (car lst) (cdr lst))))

但是这个只是复制列表，有没有一种简单的方法来创建反转列表的非 TCO 递归函数？

我问 ChatGPT，他向我展示了使用

append

的代码，这是正确的。但是你能在不添加遍历列表的情况下做到这一点吗？

这可能是一个愚蠢的问题，但我不知道是否可能，这就是我问的原因。

在写这个问题时，我想到了一个更基本的问题。 带有累加器的 TCO 算法是否总是反向创建列表，而非 TCO 总是以相同的顺序创建列表？ 或者您可以创建一个打破此规则的算法。到目前为止，当使用累加器对列表进行操作时，我总是使用

(revese result)

。

Answer 1

这不是最有效的方法，因为

append

是 O(n)，但它是：

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