反向列表 - 方案

Question

我试图扭转一个列表，这里是我的代码：

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

所以，如果我进入（反“（1 2 3 4）），我希望它出来为（ 4 3 2 1），但现在它没有给我。我做错了什么，我该如何解决它？

Answer 1

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

这是简单的由累积consing的结果，在结果的头每一个元素，这将有扭转名单的效果的辅助程序的手段来扭转名单 - 顺便说一句，助手程序尾巴-recursive。这里的总体思路，填充了空白：

(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了点。

Answer 2

下面是使用build-list程序的解决方案：

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

Answer 3

(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)) 

还有一个答案类似奥斯卡。我刚刚开始学习计划，所以如果你发现问题，请原谅:)。

Answer 4

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

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

Answer 5

实际上，有没有必要追加或与一群lambda表达式的填充体。使用

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

Answer 6

尾递归方法命名let：

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

这是基本相同的方法为具有蓄能器参数的辅助功能，如奥斯卡的答案，其中loop结合let，使后让你可以调用一个内部函数。

Answer 7

我认为这将是更好地使用追加，而不是缺点

(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 '()) 
) 

Answer 8

这里另一个版本是描述一个反复的过程递归过程（尾递归）方案

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

将替代模型用于（r EVERSE（列表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) 

这里是描述在方案

(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)