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