展平方案中的列表

Question

我试图在方案中创建一个用于在 R5RS 语言中展平列表的函数，但我遇到了一个问题，我的函数只是 returns 输入列表而不删除括号。我认为这是由于额外的缺点，但是当我删除它时，输出变成了没有括号中元素的列表。有人能指出我正确的方向吗？

(define (denestify lst)
  (cond ((null? lst)'())
        ((list? (car lst))(cons (denestify (cons (car (car lst))(cdr (car lst))))
                                (denestify (cdr lst))))
        (else (cons (car lst)(denestify (cdr lst))))))

Answer 1

如果你想扁平化一个列表的列表，那么你必须使用append来组合每个子列表。另外，你的实现过于复杂，试试这个：

(define (denestify lst)
  (cond ((null? lst) '())
        ((pair? (car lst))
         (append (denestify (car lst))
                 (denestify (cdr lst))))
        (else (cons (car lst) (denestify (cdr lst))))))

例如：

(denestify '(1 (2 (3 4 (5) (6 (7) (8)) (9))) 10))
=> '(1 2 3 4 5 6 7 8 9 10)

Answer 2

这显示了如何将 Óscar López 的答案转换为不使用 append 并且也是尾递归的答案：

(define (denestify-helper lst acc stk)
  (cond ((null? lst) 
         (if (null? stk) (reverse acc)
             (denestify-helper (car stk) acc (cdr stk))))
        ((pair? (car lst))
         (denestify-helper (car lst) acc (cons (cdr lst) stk)))
        (else 
         (denestify-helper (cdr lst) (cons (car lst) acc) stk))))

(define (denestify lst) (denestify-helper lst '() '()))

(denestify '(1 (2 (3 4 (5) (6 (7) (8)) (9))) 10))

请注意它如何使用累加器反向构建列表以及作为堆栈的列表。

这导致

'(1 2 3 4 5 6 7 8 9 10)

符合预期。

发布后我想到了这个变化：

(define (denestify-helper lst acc stk)
  (cond ((null? lst) 
         (if (null? stk) (reverse acc)
             (denestify-helper (car stk) acc (cdr stk))))
        ((pair? (car lst))
         (denestify-helper (car lst) acc (if (null? (cdr lst)) 
                                             stk 
                                             (cons (cdr lst) stk))))
        (else 
         (denestify-helper (cdr lst) (cons (car lst) acc) stk))))

这通过在我们的堆栈上有效地进行尾调用优化来消除一些无用的 consing。可以进一步优化对一个元素列表的处理。

展平方案中的列表

Flattening a list in scheme

scheme

list

flatten