方案尾遞歸

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.