方案尾递归

Question

我想创建一个方案尾递归函数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)。 这里有什么错？

Answer 1

您正在将元素累积在列表的错误末尾。您可以追加它们在列表中正确的一端：

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

Answer 2

你更大的问题是，该功能是不尾递归在所有：不是每它自己调用它是在尾部位置。相反，这样做：

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

这实现用手tail recursion modulo cons优化，采用了“头哨兵”招大大简化了代码的分配只是一个额外的利弊电池的成本。 More in this answer.