pa_monadで遊んでみた

OCamlのモナド拡張、pa_monadで遊んでみました。

今回はリスト内の値を長さとする棒を組み合わせて三角形ができる場合に、その周長が最大になるものをpa_monadを使ってListモナドで求めてみました。

open List

(* Listモナド *)
module ListM = struct
  let return x = [x]
  let bind m f =
    List.flatten (List.map f m)
  let guard c =
    if c then
      return ()
    else
      []
end

(* リストから指定された値があれば一つだけ削除する *)
let remove i lst =
  match find_all (fun x -> x = i) lst with
      [_] -> filter (fun x -> not (x = i)) lst
    | _::rest -> (filter (fun x -> not (x = i)) lst) @ rest
    | _ -> lst

(* リストから最大の値を取り出す *)
let max lst =
  fold_right (fun x y -> if x > y then x else y) lst 0

(* 入れ子リストに対して、入れ子のリスト内の和が最大の値を取り出す *)
let max_value lst =
  max (map (fun x -> fold_right (fun y z -> y+z) x 0) lst)

(* i, j, k の長さを用いて三角形が作れるかを判定する *)
let triangle_judge i j k =
  let m = max [i; j; k] in
  if m = i then (i < j + k)
  else if m = j then (j < i + k)
  else (k < i + j)

(* 三角形が作れる組を返す *)
let triangle_length_list lst =
  perform with module ListM in
  i <-- lst;
  j <-- remove i lst;
  k <-- remove j (remove i lst);
  ListM.guard (triangle_judge i j k);
  ListM.return [i; j; k]

let _ = print_int (max_value (triangle_length_list [1; 2; 3; 4; 5; 10]))

でコンパイルは

ocamlc -pp 'camlp4of pa_monad.cmo' main.ml

でできます。

正直、効率がよくないので改良の余地大です。

でも結構楽しいですね。

ちなみに今回は
ocaml-nagoya/monad http://www.itpl.co.jp/ocaml-nagoya/index.php?OCaml%A5%C6%A5%AF%A5%CB%A5%C3%A5%AF/monad
pa_monad を通して camlp4 のコマンドラインを思い出す http://d.hatena.ne.jp/keigoi/20110225/1298605143
を参考にさせてもらいました。

コンパイルをする際に結構迷いました…なにせcamlp4ははじめてつかったので。