昨日の続き(二分木とバラの木)

木構造の定義

# type 'a tree = Lf | Br of 'a * 'a tree * 'a tree;;
type 'a tree = Lf | Br of 'a * 'a tree * 'a tree
# type 'a rosetree = RLf | RBr of 'a * 'a rosetree list;;
type 'a rosetree = RLf | RBr of 'a * 'a rosetree list
# let rtree =
    RBr ("a", [
      RBr ("b", [
        RBr ("c", [RLf]);
        RLf;
        RBr ("d", [RLf])]);
      RBr ("e", [RLf]);
      RBr ("f", [RLf])]);;
val rtree : string rosetree =
  RBr ("a",
   [RBr ("b", [RBr ("c", [RLf]); RLf; RBr ("d", [RLf])]); RBr ("e", [RLf]);
    RBr ("f", [RLf])])

複数の枝を持つrosetreeを定義した。
rosetree -> tree の変換

# let rec tree_of_rtree = function
    RLf -> Br (None, Lf, Lf)
  | RBr (a, rtrees) -> Br (Some a, tree_of_rtreelist rtrees, Lf)
  and tree_of_rtreelist = function
    [] -> Lf
  | rtree :: rest -> let Br (a, left, right) = tree_of_rtree rtree in
                     Br (a, left, tree_of_rtreelist rest);;
            Characters 201-220:
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Lf
    | rtree :: rest -> let Br (a, left, right) = tree_of_rtree rtree in
                           ^^^^^^^^^^^^^^^^^^^
val tree_of_rtree : 'a rosetree -> 'a option tree = <fun>
val tree_of_rtreelist : 'a rosetree list -> 'a option tree = <fun>
# let ctree = tree_of_rtree rtree;;
- : string option tree =
Br (Some "a",
 Br (Some "b",
  Br (Some "c", Br (None, Lf, Lf),
   Br (None, Lf, Br (Some "d", Br (None, Lf, Lf), Lf))),
  Br (Some "e", Br (None, Lf, Lf), Br (Some "f", Br (None, Lf, Lf), Lf))),
 Lf)
# 

tree -> rosetree の変換

# let rec rtree_of_tree = function
    Lf -> RLf
  | Br (None, _, _) -> RLf
  | Br (Some a, left, _) -> RBr (a, rtreelist_of_tree left)
  and rtreelist_of_tree = function
    Lf -> []
  | Br (_, left, right) as t -> rtree_of_tree t :: rtreelist_of_tree right;;
val rtree_of_tree : 'a option tree -> 'a rosetree = <fun>
val rtreelist_of_tree : 'a option tree -> 'a rosetree list = <fun>
# rtree_of_tree ctree;;
- : string rosetree =
RBr ("a",
 [RBr ("b", [RBr ("c", [RLf]); RLf; RBr ("d", [RLf])]); RBr ("e", [RLf]);
  RBr ("f", [RLf])])

テスト

# rtree_of_tree (tree_of_rtree rtree);;
- : string rosetree =
RBr ("a",
 [RBr ("b", [RBr ("c", [RLf]); RLf; RBr ("d", [RLf])]); RBr ("e", [RLf]);
  RBr ("f", [RLf])])
# tree_of_rtree (rtree_of_tree ctree);;
- : string option tree =
Br (Some "a",
 Br (Some "b",
  Br (Some "c", Br (None, Lf, Lf),
   Br (None, Lf, Br (Some "d", Br (None, Lf, Lf), Lf))),
  Br (Some "e", Br (None, Lf, Lf), Br (Some "f", Br (None, Lf, Lf), Lf))),
 Lf)