Scheme:末尾再帰で木をトラバース

Scheme:末尾再帰で木をトラバース

Atsushi's Nazo-logに、「木構造の葉の数を末尾再帰でカウントする」という問題があった。 面白そうなので考えてみる。


上記ページに出ていた、非末尾再帰版

  (define (count-leaf t s)
    (cond ((null? t) s)
          ((pair? t) (count-leaf (cdr t) (count-leaf (car t) s)))
          (else (+ s 1))))

ちなみに、何が何でも末尾再帰にせにゃいかんということは無いと思います。こういう本質的に再帰的な問題は、例え末尾再帰に直したとしても代わりのスタックを自分で用意することになるわけで。


上の例に対し、nobsun算譜の記に出た例

  (define (count-leaf t)
    (define (count-leaf-iter count left right)
      (if (pair? left)
          (count-leaf-iter count (car left) (cons (cdr left) right))
          (if (pair? right)
              (count-leaf-iter (+ count 1) (car right) (cdr right))
              (+ count 1))))
    (if (not (pair? t))
        1
        (count-leaf-iter 1 (car t) (cdr t))))

これは末尾再帰版。スタックを使う代わりに、自分でトラバース途中の木の状態を リストにして持っている。


Shiroが考えた版。継続渡しスタイルです。

  (define (count-leaf t)
    (define (count-leaf-rec t cnt cont)
      (if (pair? t)
          (count-leaf-rec (car t) cnt
                          (lambda (cnt) (count-leaf-rec (cdr t) cnt cont)))
          (cont (+ cnt 1))))
    (count-leaf-rec t 0 values))

この場合、再帰に必要なステートがその都度lambdaで作られる継続の中に閉じこまれることになります。スタックは消費しないかわりに、ヒープを消費しまくっているという。


nobsunの版を、可変長引数を使ってちょっと整理してみました。

  (define (count-leaf t)
    (define (count-leaf-iter cnt left . right)
      (cond ((pair? left)
             (apply count-leaf-iter cnt (car left) (cdr left) right))
            ((pair? right)
             (apply count-leaf-iter (+ cnt 1) (car right) (cdr right)))
            (else
             (+ cnt 1))))
    (count-leaf-iter 0 t))

tail positionでの(apply proc ...)の呼び出しは、procへのtail callになります。 元の版とどちらが効率が良いかは処理系によります。 可変個引数の処理が賢ければ、こちらの方が速いかも。 Gaucheではapplyの実装があまりうまくないので、どうかな…

More ...