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

Question

我需要创建这个函数 flat ，它应该从输入列表中重新收缩一个新列表（但在这里，输入列表内部可以有一个嵌套列表）

： (A (B (C) D) A) 的平铺是 (ABCDA)

我的算法如下，不确定是否正确：

1. 检查列表是否为空：如果不是，则继续；如果是，done -- 返回空列表
2. 如果列表长度为 1，done -- 返回列表
3. 如果列表长度大于 1，我现在该怎么办？ （我可以使用 car 和 cdr 来提取列表，但无论哪种情况，我怎样才能让它递归地将列表提取到最后，我正在考虑使用追加以在之后重新构建列表。）

任何帮助/提示将不胜感激。

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

但如果 lst 的 car 不是列表，则它将不起作用。您需要第三种情况，使用 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))