Subscribed unsubscribe Subscribe Subscribe

末尾再帰のクイックソート

プログラミング

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

ナイーブな実装

Haskellではクイックソートは次のように書ける.

qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x]
            ++ [x]
            ++ qsort [y | y <- xs, y >= x]

SchemeではHaskellのリスト内包表記の部分をfilterで代用すればよい*1

(define (filter pred? lst)
  (if (null? lst)
      lst
      (let ((x (car lst)) (xs (cdr lst)))
        (if (pred? x)
            (cons x (filter pred? xs))
            (filter pred? xs)))))

このfilterを末尾再帰に書き直すと次のようになる.

(define (filter pred? lst)
  (define (iter lst acc)
    (if (null? lst)
      acc
      (let ((x (car lst)) (xs (cdr lst)))
        (iter xs
              (if (pred? x) (append acc (list x)) acc)))))
  (iter lst '()))

これを用いてクイックソートは次のように書ける.

(define (qsort lst)
  (if (null? lst)
      lst
      (let ((x (car lst)) (xs (cdr lst)))
        (let ((lt (filter (lambda (y) (< y x)) xs))
              (ge (filter (lambda (y) (>= y x)) xs)))
          (append (qsort lt) (list x) (qsort ge))))))

末尾再帰

このqsortを末尾再帰にしたい.が,頭がこんがらがってしまう.ということでGoogleに頼ることにした.見つけた

こう変換するらしい.

(define (qsort lst k)
  (if (null? lst)
      (k '())
      (let ((x (car lst)) (xs (cdr lst)))
        (let ((lt (filter (lambda (y) (< y x)) xs))
              (ge (filter (lambda (y) (>= y x)) xs)))
          (qsort lt
                 (lambda (lower)
                   (qsort ge
                          (lambda (upper)
                            (k (append lower (list x) upper))))))))))

よくわからない.突如出てきたlambdaは何なのか? qsort内でqsortを呼んでいるのに末尾再帰なのか? と疑問噴出.
そこで,とりあえず動かしてみた.qsortのkには何を入れるのかわからなかったので,一番簡単なものを入れた.

> (qsort '(3 8 2 7 8 1 0) (lambda (x) x))
(0 1 2 3 7 8 8)

うごいた.なんでだろう.継続なんだろうということはわかるけど,継続は難しい.ということで,肝心の評価ができないので,あとで書くメソッド発動.

追記 (以下のコードは誤り)

(再帰関数を末尾再帰関数に変換する)をちびちび弄っていたら以下の方法でもうまくいくことがわかった.こちらの方がしっくり来る.

(define (qsort lst k)
  (if (null? lst)
      (k lst)
      (let ((x (car lst)) (xs (cdr lst)))
        (let ((lt (filter (lambda (y) (< y x)) xs))
              (ge (filter (lambda (y) (>= y x)) xs)))
          (qsort lt
                 (lambda (a)
                   (k (append a (list x) ge))))))))

時間も時間なので,続きはあとで書く.

追記

この実装は間違っていた.

*1:Haskellと対応づけるためにcar部をx,cdr部をxsと置くことにする.