3

我正在尝试创建一个方案尾递归函数 flatten-tl-rec 来展平嵌套的列表列表。

(define flatten-tl-rec
  (lambda (xs)
    (letrec ([flatten-tl-rec-acc
              (lambda (xs acc)
                (cond ((empty? xs) acc)
                      ((list? (first xs)) (flatten-tl-rec-acc (rest xs) (append (flatten-tl-rec-acc (first xs) '()) acc)))
                      (else (flatten-tl-rec-acc (rest xs) (cons (first xs) acc))))
                )])
      (flatten-tl-rec-acc xs '()))))

(flatten-tl-rec '(1 2 3 (4 5 6) ((7 8 9) 10 (11 (12 13)))))

但我得到(13 12 11 10 9 8 7 6 5 4 3 2 1)的不是(1 2 3 4 5 6 7 8 9 10 11 12 13). 这里有什么问题？

4

2 回答 2

4

您在列表的错误末尾累积元素。您可以将它们附加到列表的正确末尾：

(define flatten-tl-rec
  (lambda (xs)
    (letrec ([flatten-tl-rec-acc
              (lambda (xs acc)
                (cond ((empty? xs) acc)
                      ((list? (first xs))
                       (flatten-tl-rec-acc
                        (rest xs)
                        (append acc (flatten-tl-rec-acc (first xs) '()))))
                      (else (flatten-tl-rec-acc
                             (rest xs)
                             (append acc (list (first xs)))))))])
      (flatten-tl-rec-acc xs '()))))

...或者只是在最后反转列表：

(define flatten-tl-rec
  (lambda (xs)
    (letrec ([flatten-tl-rec-acc
              (lambda (xs acc)
                (cond ((empty? xs) acc)
                      ((list? (first xs))
                       (flatten-tl-rec-acc
                        (rest xs)
                        (append (flatten-tl-rec-acc (first xs) '()) acc)))
                      (else (flatten-tl-rec-acc
                             (rest xs)
                             (cons (first xs) acc)))))])
      (reverse (flatten-tl-rec-acc xs '())))))
于 2013-02-19T02:11:37.047 回答
1

您更大的问题是该函数根本不是尾递归的：并非它对自身的每个调用都处于尾部位置。而是这样做：

(define (flatten xs)
  (let ((result (list 1)))
    (let loop ((xs xs) (p result))
      (cond 
        ((null? xs) 
          (cdr result))
        ((pair? (car xs))
          (loop (cons (caar xs) 
                  (cons (cdar xs) (cdr xs)))
                p))
        ((null? (car xs))
          (loop (cdr xs) p))
        (else
          (set-cdr! p (list (car xs)))
          (loop (cdr xs) (cdr p)))))))

这手动实现了尾递归模 cons优化，使用“head-sentinel”技巧极大地简化了代码，代价是仅分配一个额外的 cons 单元格。更多在这个答案中。

于 2013-02-19T08:05:17.853 回答