2019年度「プログラミング言語」配布資料 (6)

2分木の構造は menu のような再帰ヴァリアントを使うと簡単に定義することができる．

(* Defining the shape of trees *)
type tree =
    Lf       (* Leaf *)
  | Br of {  (* Branch *)
      left:  tree;
      value: int;
      right: tree;
    }

コメント¹にあるように Lf が葉を表すコンストラクタ，Br が分岐を表すコンストラクタとなっており，Br には2つの部分木と整数のレコードが付加される．具体的な2分木は例えば

let t1 = Br {left = Lf; value = 10; right = Lf}
let t2 = Br {left = Lf; value = 25; right = Lf}
let t3 = Br {left = t1; value = 15; right = t2}
let t4 = Br {left = Lf; value = 60; right = Lf}
let t5 = Br {left = Lf; value = 48; right = t4}
let t6 = Br {left = t3; value = 30; right = t5}

2分木に関する関数は基本的に，木を引数として，その構造で場合分けを行い，Br の場合では，部分木について再帰呼び出しを行うような形の関数定義になる．

let rec f(t, ...) = 
  match t with 
    Lf -> ...
  | Br {left=l; value=v; right=r} ->
      ... f(l, ...) ... f(r, ...)

探索

探索のための関数 find は 00-introduction.html の擬似コードによく似た形になる．パターンマッチのおかげで部分木や整数の取り出しが簡潔に記述できている．

(* (Recursive) function find, which returns whether given integer n exists in BST t *)
let rec find(t, n) =
  match t with
    Lf -> false
  | Br {left=l; value=v; right=r} ->
     if n = v then true
     else if n < v then find(l, n)
     else (* n > v *)   find(r, n)

挿入

挿入も既にみた擬似コードとほぼ同じである．葉の場合には新しい節点を Br {left=Lf; value=n; right=Lf} を使って作っている．再帰呼び出しを行う際にも，挿入して得られた部分木を Br {...} に入れて，新しい木を返している．

(* (Recursive) function insert, which, given BST t and a new element n, returns
   a new binary search tree with n *)
let rec insert(t, n) =
  match t with
    Lf -> Br {left=Lf; value=n; right=Lf}
  | Br {left=l; value=v; right=r} ->
     if n = v then t
     else if n < v then Br {left=insert(l, n); value=v; right=r}
     else (* n > v *)   Br {left=l;            value=v; right=insert(r, n)}

削除

削除も，ここまでが理解できていれば簡単である．まずは，木中の最小値を求める関数 min を定義する．

(* Function min, which, given BST t, returns the minimum value stored in t.
   If t is empty, it returns min_int. *)
let rec min t =
  match t with
    Lf -> min_int  (* The smallest representable integer, which is predefined *)
  | Br {left=Lf; value=v; right=_} -> v
  | Br {left=l ; value=_; right=_} -> min l

6行目のパターンは，t が Br であり， かつ，左の部分木が Lf であるような場合 を表している．また，ワイルドカードパターンを使って，右の部分木には興味がないことを示している．7行目のパターンは，6行目でマッチしなかった場合にのみ使われるので，必然的に l は Lf ではない，すなわち Br であることになる．

実は，レコードのパターンで right=_ のようにフィールドをまるごと捨てる場合は，そのフィールドを全く書かなくてもよく，

(* (Recursive) function delete, which, given BST t and an element n to
   be deleted, returns a new binary search tree without n.  If n is not
   stored in t, it returns t as it is. *)
let rec delete(t, n) =
  match t with
    Lf -> t
  | Br {left=l; value=v; right=r} ->
     if n = v then
       match l, r with
         Lf,   Lf   -> Lf
       | Br _, Lf   -> l
       | Lf,   Br _ -> r
       | Br _, Br _ ->
          let m = min r in
          Br {left=l; value=m; right=delete(r, m)}
     else if n < v then Br {left=delete(l, n); value=v; right=r}
     else (* n > v *)   Br {left=l;            value=v; right=delete(r, n)}

9行目からの match 式のように，ふたつ以上の値に対して同時に場合分けをしたい場合には，match ... with に式をコンマで並べることができる．パターンの方もそれに応じて式の数だけパターンを並べることになる．この機能のおかげで，左右の部分木が葉か節点かどうかの4通りの場合分けが，match を入れ子にすることなくすっきり書けている．

上で，レコードのパターンでフィールドを捨てる場合は，そのフィールドを全く書かなくてもよいことを説明したが，一方で，パターン Br _ の _ は，今回のように例え全フィールドが不要な場合でも，省略できない．これは Br が引数を必要とすることを見落としているのはまずいという判断からであろう．(ここらへん，少し設計が一貫していない気もするが，レコードのフィールドを省略できる方が例外的な感じがする．)

短命な2分探索木 in OCaml (ocaml/bstMutable/)

ヴァリアントを使った2分木の表現

短命な2分木は，mutable を使ってレコードの各フィールドを変更可能だと宣言するだけで表現することができる²．

(* Defining the shape of trees *)
type tree =
    Lf       (* Leaf *)
  | Br of {  (* Branch *)
      mutable left:  tree;  (* all fields are mutable *)
      mutable value: int;
      mutable right: tree;
    }

let t1 = Br {left = Lf; value = 10; right = Lf}
let t2 = Br {left = Lf; value = 25; right = Lf}
let t3 = Br {left = t1; value = 15; right = t2}
let t4 = Br {left = Lf; value = 60; right = Lf}
let t5 = Br {left = Lf; value = 48; right = t4}
let t6 = Br {left = t3; value = 30; right = t5}

探索

探索はもともと2分木データを読むだけで構造を変更するわけではないので定義は immutable な場合と全く変わらない．

let rec find(t, n) =
  match t with
    Lf -> false
  | Br {left=l; value=v; right=r} ->
     if n = v then true
     else if n < v then find(l, n)
     else (* n > v *)   find(r, n)

挿入

挿入については，再帰呼び出しをした結果得られた新しい2分木を，フィールド更新を使って left や right フィールドに書き込んでいる部分が永続版との違いとなる(この違いは Java の場合と本質的に同じである)．

(* (Recursive) function insert, which, given BST t and a new element n, returns
   a new binary search tree with n *)
let rec insert(t, n) =
  match t with
    Lf -> Br {left=Lf; value=n; right=Lf}
  | Br br ->
     if n = br.value then t
     else if n < br.value then (br.left <- insert(br.left, n); t)
     else (* n > br.value *)   (br.right <- insert(br.right, n); t)

木の種類についての場合わけで Br の場合に，部分木や格納された整数をパターンマッチで取り出さず，それらをまとめたレコードに br という名前をつけているが，これはフィールド変更式はレコードそのものを指定する必要があるためである．実はレコード全体とフィールドの値に同時に名前をつけることもできる．その場合は，

  match t with
   ...
  | Br ({left=l; value=v; right=r} as br) ->
     if n = v then t
     else if n < v then (br.left <- insert(l, n); t)
     else (* n > v *)   (br.right <- insert(r, n); t)

などと書くことができる．(... as br) の部分が as パターンと呼ばれる記法で，マッチ対象の値(ここではコンストラクタ Br に付加されたレコード)に対して ... の部分に書かれたパターンマッチをしつつ，全体には br という名前をつけて，-> の後を計算することができる．

最後の if の then部，else部に括弧がついているのは，セミコロンよりも if〜then〜else の結合が強いためである．(より詳しくはOCaml 爆速入門 (その3,制御構造)を参照のこと．)

つまり，例えば (br.right <- insert(r, n); t) の外側の括弧がないと，

     else (if n < v then (br.left <- insert(br.left, n); t)
                    else br.right <- insert(br.right, n));
     t

のように最後の t が if の一部とみなされなくなってしまう．その結果，then 部は t つまり tree 型の式が書かれているのに，else はフィールド変更式，すなわち unit 型の式になって分岐で型が違ってしまうため，

Error: This expression has type unit but an expression was expected of type tree

のようなエラーが出てくる．("This expression" は br.right <- ... を示している．)

一方，then 部の括弧を外すと，セミコロン直後で if が一旦切れるように解釈されてしまうため，else が出てくるあたりで構文エラーになってしまう．

削除

さて最後は削除関数 delete である．まず補助関数の min は全く変更する必要がないので省略する．

(* (Recursive) function delete, which, given BST t and an element n to
   be deleted, returns a new binary search tree without n.  If n is not
   stored in t, it returns t as it is. *)
let rec delete(t, n) =
  match t with
    Lf -> t
  | Br br ->
     if n = br.value then
       match br.left, br.right with
         Lf,   Lf   -> Lf
       | Br _, Lf   -> br.left
       | Lf,   Br _ -> br.right
       | Br _, Br _ ->
          let m = min br.right in
          br.value <- m;
          br.right <- delete(br.right, m);
          t
     else if n < br.value then (br.left <- delete(br.left, n); t)
     else (* n > br.value *)   (br.right <- delete(br.right, n); t)

ちなみに，match も if と同じく場合分けの構文だが，match についてはセミコロンで切れるようなことはなく，できるだけ後ろに延ばして読む，というのがOCamlの構文規則なので，14〜17行目は括弧や begin〜end で括る必要はない．一方，match が入れ子になるときは注意が必要で，

match ... with
  A -> ...
| B -> match ... with
         C -> ...
       | D -> ...
| E -> ...

と書いても，| E -> ... の部分は内側の match の一部だと解釈されてしまう(match はできるだけ後ろに延ばして読むため)．よって，内側の match を C と D の場合だけで終わらせたい場合には，

match ... with
  A -> ...
| B -> (match ... with
          C -> ...
        | D -> ...)
| E -> ...

OCaml ではコメントを (* と *) の間に書く．Java の /* ... */ と同様，コメント中に改行があってもよい．Java の // のような一行コメントのための記法は用意されていない．↩︎
Java の場合，変更可能なインスタンス変数については何も書かなくてよく，変更を禁止する時に final と書いたのに対し，OCaml は変更可能にするために mutable という追記が必要なところに，どういうプログラミングを推奨しているかが垣間見える．↩︎

2019年度「プログラミング言語」配布資料 (4)

2分探索木 in OCaml

永続的な2分探索木 in OCaml (ocaml/bst/)

ヴァリアントを使った2分木の表現

探索

挿入

削除

短命な2分探索木 in OCaml (ocaml/bstMutable/)

ヴァリアントを使った2分木の表現

探索

挿入

削除