反转列表的方案函数

Question

对于我的编程语言课程，我应该在 Scheme 中编写一个函数来反转列表，而不使用预制的反转函数。到目前为止我得到的是

(define (reverseList lst)
(COND
((NULL? lst) '())
(ELSE (CONS (reverseList(CDR lst)) (CAR lst)))
))

我遇到的问题是，如果我输入一个列表，可以说它(a b c)给了我(((() . c) . b) . a).

我该如何获得一个没有多组括号和 的干净列表.？

Answer 1

您的实现的问题是cons没有接收列表作为其第二个参数，因此您正在构建的答案不是正确的列表，请记住：正确的列表是通过cons使用列表来构造元素，最后一个列表为空。

一种可能的解决方法是使用一个辅助函数，在累加器参数中构建答案，cons反向计算元素 - 顺便说一句，这个解决方案是尾递归的：

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

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

(reverse '(1 2 3 4 5))
=> '(5 4 3 2 1)