提取列表中的每個數字並重建列表？

Question

我需要創建這個函數flat這應該從輸入列表重新收縮新列表（但在這裏，輸入列表可以有一個嵌套列表裏面）：

ex。平（A（B（C）d）A）是（ABCDA）的

我的算法是下面的，不知道這是否是正確的：

1. 檢查列表爲空：如果沒有，去上;如果是，完成 - 返回空列表
2. 如果列表長度爲1，完成 - 返回列表
3. 如果列表長度超過1，我現在該做什麼？ （我可以使用car和cdr來提取列表，但是無論哪種情況，我怎樣才能使它遞歸地提取列表到最後，並且我在考慮使用append來重新構建列表。）

任何幫助/提示，​​將不勝感激。

Answer 1

的提示是，如果列表不null?，你不應該着眼於中flat通過列表的長度，而是請檢查列表的car是否是列表本身或只是一個原子。如果它本身就是一個列表，那麼你想要將它變平，並且將列表中的cdr弄平。

編輯：好，考慮兩種不同的情況，一個在您使用cons和一個在您使用append會發生什麼：

(append '(a b c) '(d e f)) => (a b c d e f) 

(cons '(a b c) '(d e f)) => '((a b c) d e f) 

在第一種情況下，你會得到一個平坦的列表回來，在第二種情況下，你沒有得到一個平面列表。然後，您可以嘗試

(define (bad-flatten lst) 
    (if ((null? lst) 
     '() 
     (append (car (flatten lst)) (cdr (flatten lst))))) 

但如果的carlst不是列表將無法正常工作。您需要第三個案例，使用cond，如下所示：

(define (incomplete-flatten lst) 
    (cond ((null? lst) 
     '()) 
     ((list? (car lst)) 
     (append (flatten (car lst)) (flatten (cdr lst)))) 
     (else 
     ;; you need to do something different here. I can 
     ;; think of at least two options. 
     ))) 

Answer 2

可能不是最優化的解決方案。也許你可以進一步改進：

(define (list-flatten lst) 
    (if (not (null? lst)) 
     (let loop ((args lst) (ret (list)) (c null)) 
     (if (not (null? args)) 
      (begin 
      (set! c (car args)) 
      (cond ((list? c) (loop (cdr args) (append ret (list-flatten c)) c)) 
      (else (loop (cdr args) (append ret (list c)) c)))) 
      ret)) 
     #f))