クイックソート

Haskell で一番有名（？）なコードを OCaml で書いてみた。

# let rec qsort = function
[] -> []
| hd::tl -> qsort (List.filter (fun x -> x < hd) tl) @ [hd] @ qsort (List.filter  (fun y -> hd <= y) tl)
;;
val qsort : 'a list -> 'a list = <fun>
# qsort [1;5;3;2;6;7;4;9];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 9]

はじめ List.filter に与える関数を (>hd) みたいに書いたらだめだった。 OCaml ではセクションは使えないらしい。演算子を関数的に使って部分適用ならok。

# let rec qsort' = function
[] -> []
| hd::tl -> qsort' (List.filter ((>) hd) tl) @ [hd] @ qsort' (List.filter ((<=) hd) tl)
;;
val qsort' : 'a list -> 'a list = <fun>
# qsort' [1;5;3;2;6;7;4;9];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 9]