提取列表中的每个数字并重建列表？

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