撤消列表错误

Question

我正在学习DrRacket，我需要编写一个反转列表的程序。我有下面，它正在反转数字，但不知何故将它们嵌套在列表中或其他东西中。

(define (reverse-list lon)
  (if (empty? lon)
      empty
      (cons (reverse-list (rest lon))
            (cons (first lon)
                  empty))))

的输出(反向列表(列表 1 2 3 4((：

(list (list (list (list empty 4) 3) 2) 1)

有谁知道为什么输出不只是作为一个列表出现？

感谢您的帮助！

Answer 1

cons有两个单元格。 car和cdr.单元格可以显示为(a . b)其中a和b可以是任何内容。

对还有另一种表示形式。如果b是另一对或空列表，则可以将. b )替换为没有初始(的b。因此：

(a . ())             ; ==> (a)
(a . (b . c))        ; ==> (a b . c)
(a . (b . (c . ()))) ; ==> (a b c)

现在是您的代码。想象一下，你用(1 2 3 4)(或者准确地说是(1 . (2 . (3 . (4 . ()))))(尝试它。使用替换规则，我们准确计算您的程序的作用：

(reverse-list '(1 . (2 . (3 . (4 . ())))))                   ; ==>
(if (empty? '(1 . (2 . (3 . (4 . ())))))
    empty 
    (cons (reverse-list (rest '(1 . (2 . (3 . (4 . ()))))))
          (cons (first '(1 . (2 . (3 . (4 . ()))))) 
                empty)))                                      ; ==>
(if #f
    empty 
    (cons (reverse-list (rest '(1 . (2 . (3 . (4 . ()))))))
          (cons (first '(1 . (2 . (3 . (4 . ()))))) 
                empty)))                                      ; ==>
(cons (reverse-list '(2 . (3 . (4 . ()))))
      (cons 1 empty))                                      ; ==>
(cons (cons (reverse-list '(3 . (4 . ())))
            (cons 2 empty))
      (cons 1 empty))                                      ; ==>
(cons (cons (cons (reverse-list '(4 . ()))
                  (cons 3 empty))
            (cons 2 empty))
      (cons 1 empty))                                      ; ==>
(cons (cons (cons (cons (reverse-list '())
                        (cons 4 empty))
                  (cons 3 empty))
            (cons 2 empty))
      (cons 1 empty))                                      ; ==>
(cons (cons (cons (cons '()
                        (cons 4 empty))
                  (cons 3 empty))
            (cons 2 empty))
      (cons 1 empty))                                      ; ==>
((((() . (4 . ())) . (3 . ())) . (2 . ())) . (1 . ()))     ; ==>
((((() . (4)) . (3)) . (2)) . (1))                         ; ==>
((((() 4) 3) 2) 1)

现在。一个 True 反向列表在虚线表示法中看起来像这样：

(4 . (3 . (2 . (1 . ())))) ; ==> (4 3 2 1)

这是没有办法的。你需要与cons非常亲密，并知道如何展示构建它们的不同方式。一个提示是，几乎每个列表都是从结尾到开头创建的，并从开始到结束进行迭代。

Answer 2

很高兴看到你已经解决了自己的问题。但是我觉得我应该选择一点，因为反转列表实际上是在迭代的方式上建立一个列表。

(define (reverse-list lon)
  ;; iterative helper procedure
  (define (aux lon acc)
    (if (empty? lon)
        acc
        (aux (rest lon) 
             (cons (first lon) acc))))
  ;; use helper
  (aux lon empty))
(reverse-list '(1 2 3 4)) ; ==> (4 3 2 1)

如您所见，我们从头到尾进行迭代。当我们这样做时，我们将当前元素复制到到目前为止的累积列表中，并且该操作是从头到尾的。E.i. 最后添加的元素将是结果中的第一个元素。这样做的好处是，我们为每个处理的单元格使用一个新单元格，它成为最终结果的一部分。对于每次使用append，您都会复制第一个参数，以便n元素列表分配(apply + (range n))不必要的单元格。

更有经验的 Schemer 会使用命名let来执行本地过程并一次性调用：

(define (reverse-list lon)
  (let aux ((lon lon) (acc empty))
    (if (empty? lon)
        acc
        (aux (rest lon) 
             (cons (first lon) acc)))))

Answer 3

因此，最终有效的只是用附加替换第一个缺点以停止列表嵌套。

(define (reverse-list lon)
  (if (empty? lon) empty (append (reverse-list (rest lon)) (cons (first lon) empty))))

问题解决了，谢谢你的帮助。