在有一些限制的情况下反转Scheme中的列表

Question

我正在尝试反转Scheme中的列表，但我只能使用define、car、cdr、list?，<强>空？，<强>如果，<强>条件，<强>缺点，<强>显示，< strong>开始，以及任何运算符。我不能使用追加、循环（必须是纯递归）、lambda 和任何其他我没有提到的函数。我也不允许使用辅助函数。一切都应该在一个功能中。

现在已经过去几个小时了，我已经尝试了多种解决方案，但仍然无法解决这个问题。这是我得到的最接近的解决方案：

(define (my-reverse2 lis)
    (if (null? (cdr lis)) lis
        (cons (my-reverse2 (cdr lis)) (cons (car lis) '()))))

这是输出：

> (my-reverse2 '(3 2 1))
Output: (list (list (list 1) 2) 3)

输出应该类似于 (1 2 3)。我应该如何进行？

Answer 1

最简单的方法是使用累加器值：

(define (my-reverse the-list acc)
  (if (null? the-list)
      acc
      (my-reverse (cdr the-list)
                  (cons (car the-list) acc))))

您将其称为 (my-reverse '(1 2 3) '())。如果Scheme中有可选参数，您可以将acc设为可选，默认值为空列表。在我的代码中，我通常会对此进行包装，仅使用单个参数，然后使用空列表调用两个参数版本。

Answer 2

首先，反转 cdr 并获取其 car ——这将是......最后元素，对吗？ -- 其cdr 将是相反的core，即没有最后一个和第一个元素的原始列表。

然后，将原始carcons到反转的核心上，反转，从而按原始顺序获取列表中除最后一个元素之外的所有元素。那么现在我们可以反转那个，并将最后一个元素cons到结果上。

很简单，对吧？是的，没那么多。所以这里有一个例子：

a b c ...... m n                                         ; car, cdr:
  b c ...... m n                                         ; reversen-1:
|              n m ...... c b                            ; car, cdr:
|                m ...... c b                            ; reversen-2:
|              |            b c ...... m                 ; cons a:
a              |            b c ...... m                 ; reversen-1:
               |                       m ...... c b a    ; cons n:
               n                       m ...... c b a    ; =: reversen

所有这些需要的是 cdr, car, cons, null?, cond 和递归。 let/define 会有很大帮助，但并不是绝对必要的。不要忘记处理极端情况。

另请参阅：这个我的相关答案。

Answer 3

可能是有史以来效率最低的reverse，但它确实符合您问题中的标准。在本练习结束时，您应该能够相当轻松地纯粹从 car 和 cdr 角度思考 -

(define (reverse t)
  (if (null? t)
      t
      (if (null? (cdr t))
          t
          (cons (car (reverse (cdr t)))
                (reverse
                 (cons (car t) 
                       (reverse
                        (cdr (reverse (cdr t))))))))))

(reverse '(1 2 3 4 5 6 7 8 9))

'(9 8 7 6 5 4 3 2 1)

好吧，dangit，这基本上就是 @WillNess 写的 :D

If let 被允许，你可以删除两个 (reverse (cdr t)) 实例 -

(define (reverse t)
  (if (null? t)
      t
      (if (null? (cdr t))
          t
          (let ((q (reverse (cdr t))))
            (cons (car q)
                  (reverse (cons (car t)
                                 (reverse (cdr q)))))))))

如果允许 or，我们可以折叠两个 if -

(define (reverse t)
  (if (or (null? t) (null? (cdr t)))
      t
      (let ((q (reverse (cdr t))))
        (cons (car q)
              (reverse (cons (car t)
                             (reverse (cdr q))))))))

Answer 4

您可以使用可选参数吗？

(define (my-reverse lst [lst2 '()])
  (if (null? lst) lst2
      (my-reverse (cdr lst)
                  (cons (car lst) lst2))))

测试：

> (my-reverse '(3 2 1))
'(1 2 3)