反转列表 - Scheme

Question

我正在尝试将一个列表进行反转，这是我的代码：

(define (reverse list)
  (if (null? list) 
     list
      (list (reverse (cdr list)) (car list))))

如果我输入(reverse '(1 2 3 4))，我希望输出为(4 3 2 1)，但现在它没有给我想要的结果。我做错了什么，应该如何修复？

- tlauer

---

你的代码是否预计能够与循环列表和不规则列表中的任意一种或两种同时配合使用？ - GoZoner

请使用(append A (list B))代替(list A B)。 - Will Ness

Answer 1

对于递归列表的自然方式并不是解决这个问题的最佳方法。使用append，如@lancery所指出的被接受的答案建议的那样，也不是一个好主意 - 而且无论如何，如果你正在学习Scheme，最好尝试自己实现解决方案，我会告诉你该怎么做，但是首先有一个提示 - 不要使用list作为参数名，那是一个内置过程，你会覆盖它。使用其他名称，比如lst。

通过一个辅助程序来累积每个元素在结果的头部consing的结果更简单，这将导致反转列表 - 顺便说一下，辅助程序是尾递归的。这里是一般的想法，填写空白：

(define (reverse lst)
  (<???> lst '()))                       ; call the helper procedure

(define (reverse-aux lst acc)
  (if <???>                              ; if the list is empty
      <???>                              ; return the accumulator
      (reverse-aux <???>                 ; advance the recursion over the list
                   (cons <???> <???>)))) ; cons current element with accumulator

当然，在现实生活中，您不需要从零开始实现reverse函数，这里有一个内置的procedure可以使用。

- Óscar López

---

我不建议使用“list”作为参数名称 - Scheme的词法作用域是其美丽的一部分。我建议不要将参数与“全局”函数混淆; 这是提问者代码中的一个错误。 - GoZoner

Answer 2

这是一个递归过程，描述了Scheme中反转列表的迭代过程（尾递归）。

(define (reverse lst)
  (define (go lst tail)
    (if (null? lst) tail
        (go (cdr lst) (cons (car lst) tail))))
  (go lst ())))

使用代换模型来求解 (reverse (list 1 2 3 4))：

;; (reverse (list 1 2 3 4))                                                                                                                           
;; (go (list 1 2 3 4) ())                                                                                                                             
;; (go (list 2 3 4) (list 1))                                                                                                                         
;; (go (list 3 4) (list 2 1))                                                                                                                         
;; (go (list 4) (list 3 2 1))                                                                                                                         
;; (go () (list 4 3 2 1))                                                                                                                             
;; (list 4 3 2 1)

这里有一个递归过程，描述了在Scheme中反转列表的递归过程（非尾递归）。

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

(define (append l1 l2)
  (if (null? l1) l2
      (cons (car l1) (append (cdr l1) l2))))

使用代换模型来执行 (reverse2 (list 1 2 3 4))

;; (reverse2 (list 1 2 3 4))                                                                                                                          
;; (append (reverse2 (list 2 3 4)) (list 1))                                                                                                          
;; (append (append (reverse2 (list 3 4)) (list 2)) (list 1))                                                                                          
;; (append (append (append (reverse2 (list 4)) (list 3)) (list 2)) (list 1))                                                                          
;; (append (append (append (append (reverse2 ()) (list 4)) (list 3)) (list 2)) (list 1))                                                              
;; (append (append (append (append () (list 4)) (list 3)) (list 2)) (list 1))                                                                         
;; (append (append (append (list 4) (list 3)) (list 2)) (list 1))                                                                                     
;; (append (append (list 4 3) (list 2)) (list 1))                                                                                                     
;; (append (list 4 3 2) (list 1))                                                                                                                     
;; (list 4 3 2 1)

- Sergiu Starciuc

Answer 3

使用命名的 let 来实现尾递归：

(define (reverse lst)
  (let loop ([lst lst] [lst-reversed '()])
    (if (empty? lst)
        lst-reversed
        (loop (rest lst) (cons (first lst) lst-reversed)))))

这基本上与Oscar的答案中使用带有累加器参数的辅助函数的方法相同，其中在let之后的loop绑定使得let成为一个内部函数，您可以调用它。

- Jack

Answer 4

尾递归解决方案：

(define (reverse oldlist)
    (define (t-reverse oldlist newlist)
        (if (null? oldlist)
            newlist
            (t-reverse (cdr oldlist) (cons (car oldlist) newest))))
    (t-reverse oldlist '()))

- Tom el Safadi

---

这不就是和这个答案中的第一个解决方案一模一样吗，只是变量名改了一下。 :) - Will Ness

是的，看起来是一样的。 - Tom el Safadi

Answer 5

只需使用cons对列表进行左折叠：

(define (reverse list) (foldl cons null list))

这也很高效，因为foldl是尾递归的，并且不需要使用append。 这也可以使用curry（从racket中）进行点无关：

(define reverse (curry foldl cons null))

- twf

Answer 6

这个可以工作，但它不是一个尾递归过程：

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

- Nico Mkhatvari

Answer 7

这是一个使用 build-list 过程的解决方案:

(define reverse
  (lambda (l)
    (let ((len (length l)))
      (build-list len
                  (lambda (i)
                    (list-ref l (- len i 1)))))))

- kelly

Answer 8

我认为使用append而不是cons会更好

(define (myrev l)
  (if (null? l)
      '()
      (append (myrev (cdr l)) (list (car l)))
  )
)

这是使用尾递归的另一个版本

(define (myrev2 l)
  (define (loop l acc) 
    (if (null? l)
        acc
        (loop (cdr l) (append (list (car l)) acc ))
    )
  )
  (loop l '())
)

- Salvatore Rapisarda

Answer 9

实际上没有必要用一堆lambda来添加或填充函数体。

(define (reverse items)
  (if (null? items)
      '()
      (cons (reverse (cdr items)) (car items))))

- Ciro Costa

---

我认为你想用append而不是cons。运行(reverse '(1 2 3))会得到'(((() . 3) . 2) . 1)。 - Jack

没错，你说得对！@Salvatore Rapisarda 说得对。 - Ciro Costa

Answer 10

(define reverse?
  (lambda (l)
    (define reverse-aux?
      (lambda (l col)
        (cond 
          ((null? l) (col ))
          (else 
            (reverse-aux? (cdr l) 
                          (lambda () 
                            (cons (car l) (col))))))))
    (reverse-aux? l (lambda () (quote ())))))
(reverse? '(1 2 3 4) )

再补充一个与Oscar类似的答案。我刚开始学习Scheme，如果你发现问题，请原谅我：）。

- Jay Rajput