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

五十嵐 淳 (京都大学大学院情報学研究科 通信情報システム専攻)

2016年11月6日

[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]

under construction2017年版に向け改訂中

2分探索木 in OCaml (ocaml/bst/)

まず immutable な2分探索木を実装する．

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

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

1
2
3
4
5
6
7
8

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

コメント1にあるように 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 の擬似コードによく似た形になる．パターンマッチのおかげで部分木や整数の取り出しが簡潔に記述できている．

1
2
3
4
5
6
7
8

(* (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 {...} に入れて，新しい木を返している．

1
2
3
4
5
6
7
8
9

(* (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)}

削除

削除も，ここまでが理解できていれば簡単である．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

(* (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)}

パターンマッチに出てくる _ はワイルドカードパターンと呼ばれる「何でもマッチするが名前はつけない」というものである．右の部分木には興味がないので名前もつけずに捨てている．(実は，レコードの場合 right=_ そのものを書かなくてもよく，

  | Br {left=Lf; value=v} -> v

と書いてもよい．一方，Br _ の _ は省略できない．これは Br が引数を必要とすることを見落としているのはまずいという判断からである．(ここらへん，少し一貫していない気もするが，レコードのフィールドを省略できる方が例外的な感じがする．)

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

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


ここで一旦前の資料の参照に関する節を読むべし．

次は mutable な2分木である．

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

mutable な2分木は，mutable を使ってレコードの各フィールドを変更可能だと宣言するだけで表現することができる．(Java の場合は変更可能な場合は何も書かなくてよく，変更を禁止する時に final と書いたのに対し，OCaml は変更可能にするために追記が必要なところに，どういうプログラミングを推奨しているかが垣間見える．)

1
2
3
4
5
6
7
8

(* 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;
    }

具体的な2分木の作り方は immutable な場合と全く同じである．

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 な場合と全く変わらない．

1
2
3
4
5
6
7

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 フィールドに書き込んでいる部分が immutable 版との違いとなる(この違いは Java の場合と本質的に同じである)．

1
2
3
4
5
6
7
8
9

(* (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 の結合が強いために必要となっている．つまり，else 部の括弧がないと，

     else 
       (if n < br.value 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 が出てくるあたりで構文エラーになってしまう．
(OCaml の if は基本的に then と else の両方があるのが基本なのだが，

if ... then print_int 100
else ()

のような「条件が成立しない時には何もしない」プログラムを簡潔に書くために，else の省略を許している．else を省略した場合，
then 部の型は unit であることが求められる．

if ... then 2

のような式は型付けエラーとなる．

OCaml では ( と )の代わりに begin と end を使うことができ，式をセミコロンで並べる時には begin〜end で括るのを好む人もいる．例えば，

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

などと書ける．2

削除

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

(* (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)

これも，Java 版と比べてみるとよいだろう．

ちなみに，match も if と同じく場合分けの構文だが，match についてはセミコロンで切れるようなことはなく，できるだけ後ろに延ばして読むことができるので，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 -> ...

と括弧で括る必要がある．

[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]

  1. OCaml ではコメントを (* と *) の間に書く．Java の /* ... */ と同様，コメント中に改行があってもよい．Java の // のような一行コメントのための記法は用意されていない．↩

  2. Rubyっぽい？(歴史的には順序が逆ですが．)↩

Copyright 五十嵐 淳, 2016, 2017