■

Rubyのメタプログラミングを続けていると精神が荒れてくるので、家ではOCamlを書いて心の平穏を取り戻そうと思います。

今までマージソートを書いたことが無いことに気がついたので、この機会に書いてみようと思ったらOCamlの文法をちょこちょこ忘れていました。結構ショック…

let rec msort l =
  let rec _split l n lf ri =
    match l with
    | [] -> (lf, ri)
    | hd::tl ->
        if n > 0 then _split tl (n - 1) (hd::lf) ri
        else (hd::lf, tl)
  in
  let rec _merge lf ri =
    match lf, ri with
    | _, [] -> lf
    | [], _ -> ri
    | lhd::ltl, rhd::rtl ->
        if lhd < rhd then lhd::_merge ltl ri
        else              rhd::_merge lf rtl
  in
  match l with
  | [_] -> l
  | [a; b] -> if a < b then l else [b; a]
  | _ ->
      let lf, ri = _split l (List.length l / 2) [] [] in
      _merge (msort lf) (msort ri)

あいかわらず末尾再帰で書ききれないのが可愛いところ。