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

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

これは、余分なコンス セルを 1 つ割り当てるだけでコードを大幅に簡素化する「ヘッド センチネル」トリックを使用して、末尾再帰モジュロ コンス最適化を手動で実装します。この回答の詳細。

于 2013-02-19T08:05:17.853 に答える