2021-06-10 Thu. 再帰ヴァリアント型。木構造。

勉強

プログラミング in OCaml (–§ 6.4. 二分木)

二分木

木構造というデータ構造がある。 - ノード：データを格納する。 - ノードは0個以上の子ノードを持つ。

各ノードの子ノードの最大個数が $n$ のとき $n$ 分木という。

二分木は再帰的に定義できる： - データを持たない空の木(葉という)は二分木。 - ふたつの二分木の根を子ノードとする新しいノード(枝という)を付け加えたものは二分木。

二分木は再帰ヴァリアント型で表せる：

type 'a tree = Lf | Br of 'a * 'a tree * 'a tree

木の例

f:id:eternalletter:20210611013856p:plain — chartree のグラフ。

let chartree = Br ('a', Br ('b', Br ('d', Lf, Lf), Lf), Br ('c', Br ('e', Lf, Lf), Br('f', Lf, Lf)))

子のないノードは Br (..., Lf, Lf) 。

(* 木のノード数を計算する関数 size *)
let rec size = function
    Lf -> 0
  | Br (_, left, right) -> 1 + size left + size right

(* 木の深さを計算する関数 depth *)
let rec depth = function
    Lf -> 0
  | Br (_, left, right) -> 1 + max (depth left) (depth right)

完全二分木

完全二分木の例。

f:id:eternalletter:20210611013941p:plain — 完全二分木の例。

let comptree =
    Br (1,
        Br (2,
            Br (4, Lf, Lf),
            Br (5, Lf, Lf)),
        Br (3,
            Br (6, Lf, Lf),
            Br (7, Lf, Lf)))

木構造の要素を列挙してリスト化したい。つまり、木のノードをもれなく訪れて、ノードの要素を適当に順序付けて記録したい。順序の付け方として

行きがけ順 (preorder)
通りがけ順 (inorder)
帰りがけ順 (postorder)

が考えられる。

行きがけ順 (preorder)

訪れたノードを記録 -> 左の部分木 -> 右の部分木の順で列挙していく。

let rec preorder = function
    Lf -> []
  | Br (x, left, right) -> x :: (preorder left) @ (preorder right)

深さの割にサイズが小さい木に対して@は非効率。列挙済みの要素のリストを引数として追加して、各ノードではそのリストに要素を追加することによって@を使わずに済ませる。

let rec preord t l = (* l は列挙済み要素のリスト *)
  match t with
    Lf -> l
  | Br (x, left, right) -> x :: (preord left (preord right l))

通りがけ順 (inorder)

左の部分木 -> 親ノード -> 右の部分木

let rec inorder function
    Lf -> []
  | Br (x, left, right) -> (inorder left) @ (x :: inorder right)

帰りがけ順

部分木 -> 親ノード

let rec postorder = function
    Lf -> []
  | Br (x, left, right) -> (postorder left) @ (postorder right) @ [x]

二分探索木

f:id:eternalletter:20210611014046p:plain — 二分探索木。

f:id:eternalletter:20210611014111p:plain — 二分探索木の例。

Br (4,
    Br (2,
        Lf,
        Br (3, Lf, Lf)),
    Br (5, Lf, Lf))

二分探索木上で、ある要素が木の中にあるかを問い合わせるmem、要素を木に追加するaddは次のように書ける。

(* 木の中に要素があるかを調べる mem *)
let rec mem t x =
  match t with
    Lf -> false
  | Br (y, left, right) ->
      if x = y then true
      else
        if x < y then mem left x
        else mem right x

(* 木に要素を追加する add *)
let rec add t x =
  match t with
    Lf -> Br (x, Lf, Lf)
  | (Br (y, left, right) as whole) when x = y -> whole
  | Br (y, left, right) when x < y -> Br (y, add left x, right)
  | Br (y, left, right) -> Br (y, left, add right x)

バラの木

子ノードの数が決まっていない木構造のこと。

ノードの下の子ノードをリストで並べると、バラの木は次のようになる。

type 'a rosetree = RLf | RBr of 'a * 'a rosetree list

バラの木の例として XML (eXtensible Markup Language) がある。XML は、タグという特殊な文字列で装飾されたデータのこと。タグの対応が正しく取れているものを整形式 XML という。開きタグから閉じタグまでの部分を木だと思うとバラの木になっている。

<addressbook>
  <person>
    <name> Deady </name>
    <website> eternalletter </website>
  </person>
  <person>
    ...
  </person>
  <person>
    ...
  </persion>
</addressbook>

f:id:eternalletter:20210611014149p:plain — XML の例。

これをバラの木で表す。葉にデータを格納できるようにするので、次のような形式。

type ('a, 'b) xml =
    XLf of b' option (* 空の場合もあるので option 型 *)
  | XBr of 'a * ('a, 'b) xml list

上のアドレス帳はこう。

let addressbook =
  XBr ( "addressbook",
        [ XBr ("person",
               [ XBr ("name", [XLf (Some "Deady")]);
                 XBr ("website", [XLf (Some "eternalletter")])]);
          XBr ("person", [XLf None]);
          XBr ("person", [XLf None])])

この構造を文字列に変換する。

let rec string_of_xml = function
    XBr (tag, xml_list) -> "<" ^ tag ^ ">" ^ string_of_xmllist xml_list ^ "</" ^ tag ^ ">"
  | XLf None -> ""
  | XLf (Some s) -> s
  and string_of_xmllist = function
      [] -> ""
    | xml :: rest -> string_of_xml xml ^ string_of_xmllist rest

日記

断酒30日目。大台に乗ってしまった。最強。

プログラミング in OCaml は XML の処理の例まで来た。文字列の処理までわかりたいのでもっと読みすすめる。

OCamlの標準ライブラリのソースコードがopamのディレクトリ以下にあるので覗いてみたが、手書きは大変そうだった。

今日は早起きして、木構造のグラフを書きたくて graphviz というツールを導入した。

ここ1週間ほどOCamlの練習ばかりしているので他のこともやりたい。

週末デッドエンド

勉強と日記と怪文書