方案尾递归 [英] scheme tail recursion

问题描述

我正在尝试创建方案尾部递归函数flatten-tl-rec，以使嵌套的列表列表变得平坦.

I am trying to create a scheme tail recursive function flatten-tl-rec that flattens a nested list of lists.

(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). 怎么了?

But I am getting (13 12 11 10 9 8 7 6 5 4 3 2 1) instead of (1 2 3 4 5 6 7 8 9 10 11 12 13). Whats wrong here?

推荐答案

您正在将元素累积在列表的错误末端.您可以将它们附加在列表的正确末端:

You're accumulating the elements at the wrong end of the list. You can either append them at the correct end of the list:

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

...或者只是在末尾反转列表:

... Or simply reverse the list at the end:

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

这篇关于方案尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！