反向列表 - 方案

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)