平整方案清单

Question

我正在尝试创建一种用于在方案中使用R5RS语言展平列表的函数，并且遇到了这样的问题，即我的函数仅返回输入列表而不删除括号。我认为这是由于额外的缺点所致，但是当我删除它时，输出将成为列表，其中没有括号中的元素。有人可以指出我正确的方向吗？

(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

这显示了如何将ÓscarLó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))))
通过有效地对堆栈进行尾部调用优化，从而消除了一些无用的cons。可以更进一步，优化对一个元素列表的处理。

Answer 3

上面的代码对我不起作用。