読者です 読者をやめる 読者になる 読者になる

穴日記

どうだ明るくなったろう

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

http://d.hatena.ne.jp/maoe/20060130
というCPS変換を使ったSchemeによるクイックソートの末尾再帰実装を見つけたので、OCamlで再実装してみました。

let rec qsort lst cont =
  match lst with
    | [] -> cont []
    | x::xs ->
        let left  = filter (fun a -> a <= x) xs in
        let right = filter (fun a -> a > x) xs in
          qsort left (fun lower -> qsort right
                        (fun upper -> cont (lower @ [x] @ upper)))

filterは適当に実装してください。
あと、@演算子によるリスト結合は実は末尾再帰じゃかったりするので、厳密には末尾再帰じゃない気もしますが、まあいいですよね(ぇ。