クイッククイック、ソートソート

末尾再帰なクイックソートをschemeで書いてみたよ。

階乗とかフィボナッチを末尾再帰に書き換えるのはわかるのだけれど，クイックソートを末尾再帰に書き換えるのはどうすればよいのか?

末尾再帰のクイックソート - maoeのブログ

という話をみつけて、確かにあんまり考えたことなかったなと思って読んでいったら、結論としてはこうなってた。

最終的にqsortは次のようになる．

(define (qsort lst k)
  (if (null? lst)
      (k lst)
      (let ((x (car lst)) (xs (cdr lst)))
        (receive (lt ge) (partition (lambda (y) (< y x)) xs)
          (qsort lt
                 (lambda (v1)
                   (qsort ge
                          (lambda (v2)
                            (k (append v1 (cons x v2)))))))))))

末尾再帰のクイックソートつづき - maoeのブログ

真っ向からCPS変換、継続かわいいよ継続。でも継続使わなくても末尾再帰になるはずだよなー、と考えながらシャワーあびてたら思いついた。こんなの。

(define (qsort lst)
  (let qs ((stack '())
           (current lst)
           (acc '()))
    (if (not (pair? current))
        (let ((new_acc (if (list? current) acc (cons current acc))))
          (if (null? stack)
              new_acc
              (qs (cdr stack) (car stack) new_acc)))
        (let ((x (car current))
              (xs (cdr current)))
          (receive (lt ge) (partition (lambda (y) (< y x)) xs)
            (qs (cons x (cons lt stack)) ge acc))))))

末尾再帰化お決まりのアキュムレータを追加して、ソート済みのリストを格納していく。さらに、階乗のコードとは違って再帰呼び出しが二回あるのでその呼出し順序を管理するためのスタックもつけてある。ふつうは処理系がやってるスタック管理を(必要なデータだけ保持して)自前でやってるかんじ。
schemeは末尾再帰をループに最適化してくれるので、入力リストがいくら長くても処理系のスタックをくいつぶされることはないはずだけど、その代わり自分が管理してるスタック(stack)がものすごく長くなってしまうかもしれない。まあしょうがない。そう思うとこういう素直な再帰コードをがんばって末尾再帰に変換してもあんまり嬉しくないのかなあ。
ちなみにpartition関数を使うためにGaucheのパッケージを使っている。他の処理系で動くかどうかはよく知らない。あ、named-letというのをはじめて使ってみた。なかなか便利。