scheme tail recursion

Question

我正在尝试创建一个scheme-tail递归函数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)))))))

这手动实现了尾部递归模cons优化，使用了"head-setinel"技巧，以只分配一个额外的cons单元为代价，极大地简化了代码。这个答案中有更多内容。