quicksort in OCaml

(* qsort *)
let rec qsort lst = match lst with
  [] -> []
  | x::xs -> qsort (List.filter (fun y -> y <= x) xs) @ [x] @ qsort (List.filter (fun y -> y > x) xs);;

open Format;;
open Genlex;;

let fprint_list pr ppf = function
  | [] -> fprintf ppf "[]"
  | x :: xs ->
      let f ppf = List.iter (fun x -> fprintf ppf ";@ %a" pr x) xs in
      fprintf ppf "@[<1>[%a%t]@]" pr x f;;  
 
let lexer = make_lexer ["["; "]"; ";"]  ;;

let rec parse_U = parser
  | [< 'Kwd ";"; 'Int n; ns = parse_U >] -> n :: ns
  | [< >] -> []
  ;;

let parse_T = parser
  | [< 'Int n; ns = parse_U; >] -> n :: ns
  | [< >] -> []
  ;;

let parse_S = parser
  | [< 'Kwd "["; list = parse_T; 'Kwd "]" >] -> list

let parse = parse_S

let read_from_channel ch =
  parse (lexer (Stream.of_channel ch))

let sum list = List.fold_left (+) 0 list

let () =
  let in_channel = open_in Sys.argv.(1) in
  let list = read_from_channel in_channel in
  close_in in_channel;
  printf " %a \n" (fprint_list pp_print_int) (qsort list)

这个qsort与算法本身很接近，而且使用递归在OCaml中的效率很高。

编译这段代码：
ocamlc -o qsort.exe -pp camlp4o qsort.ml