りはびり（Ordシグネチャーとファンクターを使って独自のTreeモジュールを作る）

久しぶりにOCamlでも書いてみようかと思ったら、全然書けなくなっていたのでリハビリをすることに。

お題は @osiire さんの
http://d.hatena.ne.jp/osiire/20101101
のレベル3。

といってもこれまでの経験上、最初の「Ordシグネチャーとファンクターを使って独自のTreeモジュールを作る」っぽいことしかやったことがないので、実はリハビリと称してやったことがないことに挑戦させる作戦。

まぁ、ファンクタの記法どころかシグネチャの書き方さえ忘れているので、まずは本当にリハビリ。Set.mlのコードとかをカンニングしつつ。

module type OrderedType = sig
  type t
  val compare : t -> t -> int
end

module MakeTree (Ord : OrderedType) = struct
  type t = Lf | Br of t * Ord.t * t

  let init () = Lf

  let rec add tree x =
    match tree with
    | Lf -> Br (Lf, x, Lf)
    | Br (left, v, right) ->
        if Ord.compare x v < 0
        then Br ((add left x), v, right)
        else Br (left, v, (add right x))

  let tree_of_list l =
    List.fold_left (fun a x -> add a x) (init ()) l

  let list_of_tree tree =
    let rec loop tree l =
      match tree with
      | Lf -> l
      | Br (left, v, right) ->
          loop right ((loop left l) @ [v])
    in
    loop tree []
end

module IntTree =
  MakeTree (
    struct
      type t = int
      let compare a b = a - b
    end
  )

module FloatTree =
  MakeTree (
    struct
      type t = float
      let compare a b =
        if a = b then 0 else (if a < b then -1 else 1)
    end
  )

let _ =
  let int_tree =
    IntTree.tree_of_list [8; 2; 6; 1; 9; 3; 7; 4; 5] in
  List.iter (fun x -> Printf.printf "%d " x)
    (IntTree.list_of_tree int_tree);
  print_newline ()

let _ =
  let float_tree =
    FloatTree.tree_of_list [1.0; 3.5; 1.5; 4.0; 0.5; 2.5; 2.0; 3.0] in
  List.iter (fun x -> Printf.printf "%f " x)
    (FloatTree.list_of_tree float_tree);
  print_newline ()

でけたようにみえる。

komamitsu@onion:~/lab/ocaml/tree$ ocaml tree.ml 
1 2 3 4 5 6 7 8 9 
0.500000 1.000000 1.500000 2.000000 2.500000 3.000000 3.500000 4.000000