Think Stitch
PRINCIPIA  最近の更新


累積変数

本格的に調子が悪くなってきたので軽い話題を。

継続渡し(CPS)を使うと、ふつうの再帰を末尾再帰に書き換えることができるという話をしました。 しかし末尾再帰にするだけなら自分でスタックを管理すればよいというコメントもしました。 これをかたづけて(?)おきます。

まずはよく知られた例から。リストを逆転します。

(define (reverse xs)
  (if (null? xs)
      '()
      (append (reverse (cdr xs)) (list (car xs)))))

まー、えらくぜいたくな定義ですけど、いちおう動きます。 これは次のように書き換える(?)ことができます。

(define (reverse xs)
  (define (rev2 xs rs)
    (if (null? xs)
        rs
        (rev2 (cdr xs) (cons (car xs) rs))))
  (rev2 xs '()))

パラメータをもう1つ用意して、そこに結果を積んでいきます。 このような変数のことを累積変数というのはご存知だと思います。 累積変数を使えば、再帰を末尾再帰に書き換えることができます。

樹状再帰の場合

樹状再帰の場合はもう少し手間がかかります。 例えば前に見た censor を考えます。 再帰版を再掲しておきます。

(define (censor x)
  (cond ((number? x) '*)
        ((pair? x)
         (cons (censor (car x))
               (censor (cdr x))))
        (else x)))

この場合、再帰から戻ってきたときにどちらの枝から戻ってきたのか識別できなければならないので、その情報も一緒に積んでおきます。 もはやこれは累積変数とはたぶん呼ばないのでしょう(スタックそのものを手動で管理しているだけです)。

(define (censor x st)
  (cond ((number? x)
         (cs2 '* st))
        ((pair? x)
         (censor (car x)
                 (cons (cons 'right (cdr x))
                       st)))
        (else
         (cs2 x st))))

(define (cs2 x st)
  (cond ((null? st) x)
        ((eq? (caar st) 'right)
         (censor (cdar st)
                 (cons (cons 'left x)
                       (cdr st))))
        (else ; left
         (cs2 (cons (cdar st) x)
              (cdr st)))))

ペアを見つけたら、とりあえず右側(cdr 側)はスタックに積んでおいて後回しにして、左側(car 側)を掘っていきます。 葉に達したら値を決め、次にスタックトップを見ます。 もしスタックが空なら計算は終わりですから値を返します。 空でない場合は left か right が調べます。 right の場合はノードをスタックから取り出し、次に左の値をスタックに保存してから、今度は右ノードを掘っていきます。 left の場合はノードの左右の値が求まったということですから、cons をして、再びスタックトップを調べます。

これで末尾再帰になりました。 木をたどる一般的な方法には preorder, inorder, postorder の3つがありますけど、これは postorder になります。 あとの2つの場合はもう少し簡単にできるんじゃないかと思います、たぶん。

制御の位置をデータで表しているってことなんですよね。 あと、CPS と同じように、途中で計算を放棄することもできます。 文字通り、スタックを捨ててしまえばいいわけですから。

2013/09/18
© 2013,2014,2015 PRINCIPIA Limited