<style> /* basic design */ .reveal h1, .reveal h2, .reveal h3, .reveal h4, .reveal h5, .reveal h6, .reveal section, .reveal table, .reveal li, .reveal blockquote, .reveal th, .reveal td, .reveal p { font-family: 'Meiryo UI', 'Source Sans Pro', Helvetica, sans-serif, 'Helvetica Neue', 'Helvetica', 'Arial', 'Hiragino Sans', 'ヒラギノ角ゴシック', YuGothic, 'Yu Gothic'; text-align: left; line-height: 1.8; letter-spacing: normal; text-shadow: none; word-wrap: break-word; color: #444; } .reveal h1, .reveal h2, .reveal h3, .reveal h4, .reveal h5 {font-weight: normal;}, .reveal h6 {font-weight: bold;} .reveal h1, .reveal h2, .reveal h3 {color: #2980b9;} .reveal th {background: #DDD;} .reveal section img {background:none; border:none; box-shadow:none; max-width: 95%; max-height: 95%;} .reveal blockquote {width: 90%; padding: 0.5vw 3.0vw;} .reveal table {margin: 1.0vw auto;} .reveal code {line-height: 1.2;} .reveal p, .reveal li {padding: 0vw; margin: 0vw;} .reveal .box {margin: -0.5vw 1.5vw 2.0vw -1.5vw; padding: 0.5vw 1.5vw 0.5vw 1.5vw; background: #EEE; border-radius: 1.5vw;} /* table design */ .reveal table {background: #f5f5f5;} .reveal th {background: #444; color: #fff;} .reveal td {position: relative; transition: all 300ms;} .reveal tbody:hover td { color: transparent; text-shadow: 0 0 3px #aaa;} .reveal tbody:hover tr:hover td {color: #444; text-shadow: 0 1px 0 #fff;} /* blockquote design */ .reveal blockquote { width: 90%; padding: 0.5vw 0 0.5vw 6.0vw; font-style: italic; background: #f5f5f5; } .reveal blockquote:before{ position: absolute; top: 0.1vw; left: 1vw; content: "\f10d"; font-family: FontAwesome; color: #2980b9; font-size: 3.0vw; } /* font size */ .reveal h1 {font-size: 5.0vw;} .reveal h2 {font-size: 3.0vw;} .reveal h3 {font-size: 2.8vw;} .reveal h4 {font-size: 2.6vw;} .reveal h5 {font-size: 1.8vw;} .reveal h6 {font-size: 2.2vw;} .reveal section, .reveal table, .reveal li, .reveal blockquote, .reveal th, .reveal td, .reveal p {font-size: 2.2vw;} .reveal code {font-size: 1.6vw;} /* new color */ .red {color: #EE6557;} .blue {color: #16A6B6;} /* split slide */ #right {left: -18.33%; text-align: left; float: left; width: 50%; z-index: -10;} #left {left: 31.25%; text-align: left; float: left; width: 50%; z-index: -10;} </style> <style> /* specific design */ .reveal h1 { margin: 0% -100%; padding: 2% 100% 4% 100%; color: #fff; background: #fffa5e; /* fallback for old browsers */ background: linear-gradient(-45deg, #f7f439, #54ffa4, #23A6D5, #238ed5); background-size: 200% 200%; animation: Gradient 60s ease infinite; } @keyframes Gradient { 0% {background-position: 0% 50%} 50% {background-position: 100% 50%} 100% {background-position: 0% 50%} } .reveal h2 { text-align: center; margin: -5% -50% 2% -50%; padding: 3% 10% 1% 10%; color: #fff; background: #fffa5e; /* fallback for old browsers */ background: -webkit-linear-gradient(to right, #c74646, #fffa5e); /* Chrome 10-25, Safari 5.1-6 */ background: linear-gradient(to right, #c74646, #fffa5e); /* W3C, IE 10+/ Edge, Firefox 16+, Chrome 26+, Opera 12+, Safari 7+ */ } .reveal h4 { text-align: center; } </style> <!-- --------------------------------------------------------------------------------------- --> # 第１７章 <br>再帰的なデータ構造 <br> <br> ### 201803407 有田健一郎 ### 201803451 吉野友貴 --- ## 17.1 バリアント型 ８章ではレコードを学びました。レコードはフィールドの集まりで、いろいろな要素がどれも存在するときに使います。 ```ocaml= # {name = "asai"; tensuu = 70; seiseki = 'B'};; - : gakusei_t = {name = "asai"; tensuu = 70; seiseki = 'B'} # ``` --- ## 17.1 バリアント型 一方、要素がすべて存在するのではなく、どれかひとつしか存在しない場合もあります。例えば、運動会で赤組か白組かを表すデータを考えてみましょう。各選手は赤組か白組のどちらか一方にのみ属します。このようなときには、どれかひとつを表す**バリアント型**のデータを使います。 --- ## 17.1 バリアント型 バリアント型のデータを作るときには、まずその型を宣言しなくてはなりません。赤組か白組かを表す型 team_t は type文を使って次のように宣言します。 ```ocaml= # type team_t = Red | White;; type team_t = Red | White # ``` --- ## 17.1 バリアント型 ここで宣言した新しい型 team_t は、赤組を表す Red か、白組を表す White のどちらかを値としてとります。 Red あるいは White と書くだけで team_t 型の値になります。 ```ocaml= # Red;; - : team_t = Red # White;; - : team_t = White # ``` Red や White は team_t 型の値を作るものという意味で **構成子(constructor)** と呼ばれます。 バリアント型の宣言では、使用する構成子を順に縦棒で区切って並べます。型宣言の中に出てくる縦棒"|"は match 文のときと同じく「または」と読みます。 --- ## 17.1 バリアント型 OCaml では大文字で始まるものは構成子は必ず大文字で始まらなくてはならないという規則があります。 ```ocaml= # let A = 3;; Unbound Constructor A # ``` OCaml では大文字で始まるものは構成子、小文字で始まるものは変数という使い分けをしています。 --- ## 17.1 バリアント型 バリアント型のデータを受け取ったとき match 文を使って中身にアクセスします。受け取った種類にしたがった場合分けを行います。 例えば team_t 型のデータに対応して何組かを文字列で返す関数 team_string は次のようになります。 ```ocaml= (* 目的 : 受け取ったチーム名を文字列で返す関数 *) (* team_string : team_t -> string *) # let team_string team = match team with Red -> "赤組" | White -> "白組" ``` --- ## 17.1 バリアント型 リストを match 文を使って場合分けをする時には、空リストのケースとそうでないケースを両方、きちんと書かないと警告が出ました。これはユーザの定義したバリアント型でも同じです。 例えば、次のように Red の場合分けしか書かないと White の場合を忘れているよと警告が出ます。 ```ocaml= (* 目的 : 受け取ったチーム名を文字列で返す関数 *) (* team_string : team_t -> string *) # let team_string team = match team with Red -> "赤組" Warning 8: this pattern-matching is not exhaustive. Here is an example of a case that is not matched: White # val team_string : team_t -> string = <fun> ``` --- ## 17.1 バリアント型 バリアント型の選択肢である構成子には、引数を持たせることができます。構成子に引数を持たせるには of というキーワードを使って、選択肢を「構成子 of 型」という形にします。 例えば、生まれた年を年号で表すバリアント型 nengou_t を考えてみましょう。 ```ocaml= (* 年号を表す型 *) # type nengou_t = Meiji of int (* 明治 *) | Taisho of int (* 大正 *) | Showa of int (* 昭和 *) | Heisei of int (* 平成 *) | Reiwa of int (* 令和 *) ``` ```ocaml= (* 例 : 昭和42年 *) # Showa (42);; - : nengou_t = Showa 42 # ``` --- ## 17.1 バリアント型 当然のことながら、構成子の引数には正しい型の引数を与えなければなりません。また、引数の個数にも注意しましょう。 ```ocaml= # Meiji (true);; This expression has type bool but is here was expected of type int # Taisho;; The constructor Taisho expects 1 argument(s), but is applied here to 0 argument(s) ``` --- ## 17.1 バリアント型 OCaml では、関数呼び出しをする時には、引数は単に並べて書くだけで括弧は使いません。しかし構成子に引数を与えるときには必ず括弧を使うと思っておくと間違いが減ります。引数が整数など単純な型の場合はなくてもよいのですが、引数が組の場合は必ず必要になってくるので、いつでも括弧を使うと思っておくのがよいでしょう。 --- ## 17.1 バリアント型 構成子が引数を持つときも、場合分けには match 文を使います。 例えば、年号を受け取ったら、対応する西暦年を返す関数 toseireki は次のようになります。 ```ocaml= (* 目的 : 年号を受け取ったら対応する西暦年を返す *) (* to_seireki : nengou_t -> int *) # let to_seireki nengou = match nengou with Meiji (n) -> n + 1867 | Taisho (n) -> n + 1911 | Showa (n) -> n + 1925 | Heisei (n) -> n + 1988 | Reiwa (n) -> n + 2018 ``` ```ocaml= # to_seireki (Reiwa (3));; - : int = 2021 # ``` --- ## 問題 １７.１ 誕生年と現在の年を nengou_t 型の値として受け取ってきたら、年齢を返す関数 nenrei をデザインレシピにしたがって作れ。 ```ocaml= (* 目的 : 誕生年と現在の年を受け取ってたら、年齢を返す *) (* nenrei : nengou_t -> nengou_t -> int *) let nenrei nengou1 nengou2 = 0;; (* テスト *) let test1 = nenrei (Heisei 11) (Reiwa 3) = 22 let test2 = nenrei (Showa 1) (Reiwa 3) = 95 let test3 = nenrei (Reiwa 1) (Reiwa 3) = 2 val test1 : bool = false val test2 : bool = false val test3 : bool = false ``` --- ## 問題 １７.１ ```ocaml= (* 目的 : 誕生年と現在の年を受け取ってたら、年齢を返す *) (* nenrei : nengou_t -> nengou_t -> int *) let nenrei nengou1 nengou2 = to_seireki nengou2 - to_seiseki nengou1;; val test1 : bool = true val test2 : bool = true val test3 : bool = true ``` --- ## 問題 １７.２ 1月から12月までを表す構成子 Jnuary、・・・ December を持つ型 year_t を宣言せよ。構成子には日を示す引数を取るようにせよ。 ```ocaml= type year_t = January of int (* １月 *) | February of int (* ２月 *) | March of int (* ３月 *) | April of int (* ４月 *) | May of int (* ５月 *) | June of int (* ６月 *) | July of int (* ７月 *) | August of int (* ８月 *) | September of int (* ９月 *) | October of int (* １０月 *) | November of int (* １１月 *) | December of int (* １２月 *) ``` --- ## 問題 １７.３ １２星座を示す型 seiza_t を宣言せよ。 ```ocaml= type seiza_t = Yagiza (* 12/22 - 1/19 *) | Mizugameza (* 1/20 - 2/18 *) | Uoza (* 2/19 - 3/20 *) | Ohitsuziza (* 3/21 - 4/19 *) | Ousiza (* 4/20 - 5/20 *) | Futagoza (* 5/21 - 6/21 *) | Kaniza (* 6/22 - 7/22 *) | Shishiza (* 7/23 - 8/22 *) | Otomeza (* 8/23 - 9/22 *) | Tenbinza (* 9/23 - 10/23 *) | Sasoriza (* 10/24 - 11/22 *) | Iteza (* 11/23 - 12/21 *) ``` --- ## 問題 １７.４ year_t 型の値を受け取ってきたら、 seiza_t 型の星座を返す関数 seiza をデザインレシピにしたがって作れ。 --- ## 問題 １７.４ ```ocaml= (* 目的：月と日を受け取ったら星座を返す関数 *) (* seiza : year_t -> seiza_t *) let seiza year = match year with January (n) -> Yagiza | February (n) -> Yagiza | March (n) -> Yagiza | April (n) -> Yagiza | May (n) -> Yagiza | June (n) -> Yagiza | July (n) -> Yagiza | August (n) -> Yagiza | September (n) -> Yagiza | October (n) -> Yagiza | November (n) -> Yagiza | December (n) -> Yagiza ``` --- ## 問題 １７.４ ```ocaml= (* テスト *) let test1 = seiza (February (18)) = Mizugameza;; let test2 = seiza (February (22)) = Uoza;; let test3 = seiza (December (1)) = Iteza;; let test4 = seiza (June (25)) = Kaniza;; val test1 : bool = false # val test2 : bool = false # val test3 : bool = false # val test4 : bool = false ``` --- ## 問題 １７.４ ```ocaml= let seiza year = match year with January (n) -> if n < 20 then Yagiza else Mizugameza | February (n) -> if n < 19 then Mizugameza else Uoza | March (n) -> if n < 21 then Uoza else Ohitsuziza | April (n) -> if n < 20 then Ohitsuziza else Ousiza | May (n) -> if n < 21 then Ousiza else Futagoza | June (n) -> if n < 22 then Futagoza else Kaniza | July (n) -> if n < 23 then Kaniza else Shishiza | August (n) -> if n < 23 then Shishiza else Otomeza | September (n) -> if n < 23 then Otomeza else Tenbinza | October (n) -> if n < 24 then Tenbinza else Sasoriza | November (n) -> if n < 23 then Sasoriza else Iteza | December (n) -> if n < 22 then Iteza else Yagiza ``` ```ocaml= val test1 : bool = true # val test2 : bool = true # val test3 : bool = true # val test4 : bool = true ``` --- ## 17.2 木 前節でみてきたバリアント型は、いずれも単に選択肢を提供しているだけです。しかし、バリアント型の威力は自己参照を許すところにあります。ここでは代表的な例として **木** を考えてみましょう。 木というのは空の木、葉、あるいは節からなるデータ構造です。 例 図１７.１ (p.180) 。 --- ## 17.2 木 **空の木** というのは文字通り空の木です。ここではそれを **Empty** という構成子で表すことにします。 **葉** というのは木の一番先っぽのことで何かひとつデータを持っているものです。ここではそのデータを整数とし、葉は **Leaf (n)** で表すことにします。nが葉に格納されている整数です。 **節** というのは木の幹が分かれているところです。幹が2本に分かれた先はぞれぞれがまた木になっています。ここで自己参照が使われるわけです。節にもひとつ整数のデータを格納することにすると、節は **Node (left, n, right)** と表すことができます。節は、引数として木と整数と木の３つ組を受け取っています。ここでの left と right はそれぞれ分かれた先の木を表しています。 節における子の数が必ずふたつであるような木のことを２分木と呼びます。 --- ## 17.2 木 木の型を tree_t と名付けることにしましょう。 ```ocaml= (* 木を表す型 *) type tree_t = Empty (* 空の木 *) | Leaf of int (* 葉 *) | Node of tree_t * int * tree_t (* 節 *) ``` 最後の行で Node の引数は tree_t * int * tree_t という組になっています。その中に今、定義しようとしている tree_t が入っていてそこで自己参照しているわけです。 --- ## 17.2 木 空の木や葉は直接、作ることができます。 ```ocaml= # Empty;; - : tree_t = Empty # Leaf (3);; - : tree_t = Leaf 3 # Leaf (24);; - : tree_t = Leaf 24 # ``` --- ## 17.2 木 節はすでに作成ずみの木をふたつ使います。例えば、左の木が空で右の木がLeaf (3) で値が7であるような節は次のようになります。 ```ocaml= # Node (Empty, 7, Leaf (3));; - : tree_t = Node (Empty, 7, Leaf 3) # ``` --- ## 17.2 木 一度、木ができると、それを使ってさらに大きな木を作ることができます。例えば、左の木がここで作った節で右の木がLeaf (24) で値が17であるような木は次のようになります。 ```ocaml= # Node (Node (Empty, 7, Leaf (3)), 17, Leaf (24));; - : tree_t = Node (Node (Empty, 7, Leaf 3), 17, Leaf 24) # ``` --- ## 17.2 木 ここで試しに木の定義に自己参照していないケースがなかったらどうなるのかを考えてみましょう。つまり木の定義が次のような定義だったらどうなるかを考えてみます。 ```ocaml= (* 節のみの木を表す型 *) # type tree_t = Node of tree_t * int * tree_t (* 節 *) ``` Ocamlに入力することができるがこの型を持つデータを具体的に作ることはできません。以下略(p.182) --- ## 17.2 木 ここで定義した木の型の再帰構造を明示しておきましょう。 ```ocaml= (* tree は - Empty 空の木、あるいは - Leaf (n) 値が n の葉、あるいは - Node (t1, n, t2) 左の木が t1、値が n、右の木が t2 であるような節 ( t1 と t2 が自己参照のケース ) という形 *) ``` --- ## 17.3 再帰的なデータ構造に対するデザインレシピ 再帰的なデータ構造を扱う関数を作ります。 以下に再帰的なデータ構造特有のことをまとめてデザインレシピの形で示します。 --- ## 17.3 再帰的なデータ構造に対するデザインレシピ **データ定義** <div class="box"> 入力データや出力データの型が再帰的なデータ構造になるときは、まずその型を定義します。その際、自己参照しないケースがあることを確認します。また、どこに自己参照が含まれているかを確認し、それをコメントとして明示しておきます。この時点でデータの例を作成しておくと、後で楽にテストを作ることができるようになります。 </div> **テンプレート** <div class="box"> 入力データが再帰的なデータ構造の場合は、対応する match 文を作成します。match 文の形は、再帰的データ構造の定義と１対１に対応したものになります。特に、自己参照するケースが再帰呼び出しのケースに対応します。そこにはコメントとして再帰呼び出しを書いておきましょう。再帰呼び出しは自己参照する回数だけ書かれます。 </div> --- ## 17.3 再帰的なデータ構造に対するデザインレシピ ここでは木に格納されている整数をすべて加える関数 sum_tree を作ります。まずデータ定義です。 ```ocaml= (* 木を表す型 *) type tree_t = Empty (* 空の木 *) | Leaf of int (* 葉 *) | Node of tree_t * int * tree_t (* 節 *) (* tree は - Empty 空の木、あるいは - Leaf (n) 値が n の葉、あるいは - Node (t1, n, t2) 左の木が t1、値が n、右の木が t2 であるような節 ( t1 と t2 が自己参照のケース ) という形 *) ``` --- ## 17.3 再帰的なデータ構造に対するデザインレシピ 木のデータの例を作る ```ocaml= (* 木の例 *) let tree1 = Empty let tree2 = Leaf (3) let tree3 = Node (tree1, 4, tree2) let tree4 = Node (tree2, 5, tree3) ``` tree4 は ```ocaml= Node (Leaf (3), 5, Node (Empty, 4, Leaf (3))) ``` を表しています。 --- ## 17.3 再帰的なデータ構造に対するデザインレシピ 目的と例 ```ocaml= (* 目的 : tree に含まれる整数をすべて加える *) (* sum_tree : tree_t -> int *) let rec sum_tree tree = 0 (* テスト *) let test1 = sum_tree tree1 = 0 let test2 = sum_tree tree2 = 3 let test3 = sum_tree tree3 = 7 let test4 = sum_tree tree4 = 15 ``` --- ## 17.3 再帰的なデータ構造に対するデザインレシピ テンプレート ```ocaml= (* 目的 : tree に含まれる整数をすべて加える *) (* sum_tree : tree_t -> int *) let rec sum_tree tree = match tree with Empty -> 0 | Leaf (n) -> 0 | Node (t1, n, t2) -> 0 (* sum_tree t1 *) (* sum_tree t2 *) ``` --- ## 17.3 再帰的なデータ構造に対するデザインレシピ 本体 ```ocaml= (* 目的 : tree に含まれる整数をすべて加える *) (* sum_tree : tree_t -> int *) let rec sum_tree tree = match tree with Empty -> 0 | Leaf (n) -> n | Node (t1, n, t2) -> sum_tree t1 + n + sum_tree t2 ``` --- ## 問題１７.５～問題１７.８ ```ocaml= (* 木を表す型 *) type tree_t = Empty (* 空の木 *) | Leaf of int (* 葉 *) | Node of tree_t * int * tree_t (* 節 *) (* tree は - Empty 空の木、あるいは - Leaf (n) 値が n の葉、あるいは - Node (t1, n, t2) 左の木が t1、値が n、右の木が t2 であるような節 ( t1 と t2 が自己参照のケース ) という形 *) ``` --- ## 問題１７.５ tree_t 型の木を受け取ったら、節や葉に入ってる値をすべて２倍にした木を返す関数 tree_double をデザインレシピにしたがって作れ。 ```ocaml= (* 木の例 *) let tree1 = Empty;; let tree2 = Leaf (10);; let tree3 = Leaf (0);; let tree4 = Node (tree1, 2, tree3);; let tree5 = Node (tree2, 5, tree4);; ``` --- ## 問題１７.５ 目的と例 ```ocaml= (* 目的 : 木を受け取ったら、節や葉に入っている値をすべて2倍にした木を返す *) (* tree_double : tree_t -> tree_t *) let rec tree_double tree = Empty;; (* テスト *) let test1 = tree_double tree1 = Empty;; let test2 = tree_double tree2 = Leaf (20);; let test3 = tree_double tree3 = Leaf (0);; let test4 = tree_double tree4 = Node (Empty, 4, Leaf (0));; let test5 = tree_double tree5 = Node (Leaf (20), 10, Node (Empty, 4, Leaf (0)));; ``` --- ## 問題１７.５ テンプレート ```ocaml= (* 目的 : 木を受け取ったら、節や葉に入っている値をすべて2倍にした木を返す *) (* tree_double : tree_t -> tree_t *) let rec tree_double tree = match tree with Empty -> Empty | Leaf (n) -> Empty | Node (t1, n, t2) -> Empty (* tree_double t1 *) (* tree_double t2 *) ``` --- ## 問題１７.５ 本体 ```ocaml= (* 目的 : 木を受け取ったら、節や葉に入っている値をすべて2倍にした木を返す *) (* tree_double : tree_t -> tree_t *) let rec tree_double tree = match tree with Empty -> Empty | Leaf (n) -> Leaf (n * 2) | Node (t1, n, t2) -> Node (tree_double t1, n * 2, tree_double t2) ``` ```ocaml= # val tree_double : tree_t -> tree_t = <fun> # val test1 : bool = true # val test2 : bool = true # val test3 : bool = true # val test4 : bool = true # val test5 : bool = true ``` --- ## 問題１７.６ int -> int 型の関数 f と tree_t 型の木を受け取ったら、節や葉に入っている値すべてに f を適用した木を返す関数 tree_map をデザインレシピにしたがって作れ。 ```ocaml= (* 木の例 *) let tree1 = Empty;; let tree2 = Leaf (10);; let tree3 = Leaf (0);; let tree4 = Node (tree1, 2, tree3);; let tree5 = Node (tree2, 5, tree4);; ``` --- ## 問題１７.６ 目的と例 ```ocaml= (* 目的 : 関数 f と木を受け取ったら、節や葉に入っているすべてに f を適用した木を返す *) (* tree_map : (f : (int -> int)) -> tree_t -> tree_t *) let f n = n * n;; let rec tree_map f tree = Empty;; (* テスト *) let test1 = tree_map f tree1 = Empty;; let test2 = tree_map f tree2 = Leaf (100);; let test3 = tree_map f tree3 = Leaf (0);; let test4 = tree_map f tree4 = Node (Empty, 4, Leaf (0));; let test5 = tree_map f tree5 = Node (Leaf (100), 25, Node (Empty, 4, Leaf (0)));; ``` --- ## 問題１７.６ テンプレート ```ocaml= (* 目的 : 関数 f と木を受け取ったら、節や葉に入っているすべてに f を適用した木を返す *) (* tree_map : (f : (int -> int)) -> tree_t -> tree_t *) let rec tree_map f tree = match tree with Empty -> Empty | Leaf (n) -> Empty | Node (t1, n, t2) -> Empty (* tree_map f t1 *) (* tree_map f t2 *) ``` --- ## 問題１７.６ 本体 ```ocaml= (* 目的 : 関数 f と木を受け取ったら、節や葉に入っているすべてに f を適用した木を返す *) (* tree_map : (f : (int -> int)) -> tree_t -> tree_t *) let rec tree_map f tree = match tree with Empty -> Empty | Leaf (n) -> Leaf (f n) | Node (t1, n, t2) -> Node (tree_map f t1, f n, tree_map f t2) ``` ```ocaml= # val tree_map : (int -> int) -> tree_t -> tree_t = <fun> val test1 : bool = true # val test2 : bool = true # val test3 : bool = true # val test4 : bool = true # val test5 : bool = true ``` --- ## 問題１７.７ tree_t 型の木を受け取ったら、節と葉が合計いくつあるかを返す関数tree_length をデザインレシピにしたがって作れ。 ```ocaml= (* 木の例 *) let tree1 = Empty;; let tree2 = Leaf (10);; let tree3 = Node (tree1, 1, tree2);; let tree4 = Node (tree1, 2, tree3);; let tree5 = Node (tree2, 5, tree4);; ``` --- ## 問題１７.７ 目的と例 ```ocaml= (* 目的木を受け取ったら、節と葉が合計いくつあるかを返す *) (* tree_length : tree_t -> int *) let rec tree_length tree = 0;; (* テスト *) let test1 = tree_length tree1 = 0;; let test2 = tree_length tree2 = 1;; let test3 = tree_length tree3 = 2;; let test4 = tree_length tree4 = 3;; let test5 = tree_length tree5 = 5;; ``` --- ## 問題１７.７ テンプレート ```ocaml= (* 目的木を受け取ったら、節と葉が合計いくつあるかを返す *) (* tree_length : tree_t -> int *) let rec tree_length tree = match tree with Empty -> 0 | Leaf (n) -> 0 | Node (t1, n ,t2) -> 0 (* tree_length t1 *) (* tree_length t2 *) ``` --- ## 問題１７.７ 本体 ```ocaml= (* 目的木を受け取ったら、節と葉が合計いくつあるかを返す *) (* tree_length : tree_t -> int *) let rec tree_length tree = match tree with Empty -> 0 | Leaf (n) -> 1 | Node (t1, n ,t2) -> tree_length t1 + 1 + tree_length t2 # val tree_length : tree_t -> int = <fun> val test1 : bool = true # val test2 : bool = true # val test3 : bool = true # val test4 : bool = true # val test5 : bool = true ``` --- ## 問題１７.８ tree_t 型の木を受け取ったら、木の深さを返す関数 tree_depth をデザインレシピにしたがって作れ。ここで木の深さは根から葉、または空の木に至る最長の道に含まれる節の数と定義される。ふたつの大きい方を返す関数 max を使ってもよい。 ```ocaml= (* 木の例 *) let tree1 = Empty;; let tree2 = Leaf (10);; let tree3 = Node (tree1, 1, tree2);; let tree4 = Node (tree1, 2, tree3);; let tree5 = Node (tree2, 5, tree4);; ``` --- ## 問題１７.８ 目的と例 ```ocaml= (* 目的 : 木を受け取ったら、木の深さを返す *) (* tree_depth : tree_t -> int *) let rec tree_depth tree = 0;; (* テスト *) let test1 = tree_depth tree1 = 1;; let test2 = tree_depth tree2 = 1;; let test3 = tree_depth tree3 = 2;; let test4 = tree_depth tree4 = 3;; let test5 = tree_depth tree5 = 4;; ``` --- ## 問題１７.８ テンプレート ```ocaml= (* 目的 : 木を受け取ったら、木の深さを返す *) (* tree_depth : tree_t -> int *) let rec tree_depth tree = match tree with Empty -> 0 | Leaf (n) -> 0 | Node (t1, n, t2) -> 0 (* tree_depth t1 *) (* tree_depth t2 *) ``` --- ## 問題１７.８ 本体 ```ocaml= (* 目的 : 木を受け取ったら、木の深さを返す *) (* tree_depth : tree_t -> int *) let rec tree_depth tree = match tree with Empty -> 1 | Leaf (n) -> 1 | Node (t1, n, t2) -> max (tree_depth t1) (tree_depth t2) + 1 # val tree_depth : tree_t -> int = <fun> val test1 : bool = true # val test2 : bool = true # val test3 : bool = true # val test4 : bool = true # val test5 : bool = true ``` --- ## 17.4 ２分探索木 木を使った応用として**２分探索木**を考えてみる。 ２分探索木は２分木のうちすべての節について以下のふたつの条件が成り立っているもののことである。 <br> <div class="box"> * 節の左側の木に格納されているデータは、どれもその節に格納されているデータよりも小さい。 * 節の右側の木に格納されているデータは、どれもその節に格納されているデータよりも大きい。 </div> <br> このようにデータの間に大小関係があると、その木の中にあるデータの探索を２分探索で高速に行うことができます。 --- ## 17.4 ２分探索木(search編) ２分探索を行う関数searchを作成する。 ```ocaml= (* 目的：dataが２分探索木treeに含まれているかを調べる *) (* search : tree_t -> int -> bool *) let rec search tree data = false ``` :::warning :zap:ひとつ目の引数treeは２分探索木の条件を満たす木でなくてはならない。 ::: ```ocaml= (* ２分探索木の例 *) let tree1 = Empty let tree2 = Leaf (3) let tree3 = Node (Leaf (1), 2, Leaf (3)) let tree4 = Node (Empty, 7, Leaf (9)) let tree5 = Node (tree3, 6, tree4) ``` これらの例はいずれも２分探索木の条件を満たしています。 --- ## 17.4 ２分探索木(search編テスト) これらを使うと、テストの例をこのように作成できます。 ```ocaml= (* テスト *) let test1 = search tree1 3 = false let test2 = search tree2 3 = true let test3 = search tree2 4 = false let test4 = search tree5 6 = true let test5 = search tree5 2 = true let test6 = search tree5 1 = true let test7 = s2arch tree5 4 = false let test8 = s3arch tree5 7 = true let test9 = s4arch tree5 8 = false ``` --- ## 17.4 ２分探索木（search編テンプレート） ```ocaml= (* 目的：dataが２分探索木treeに含まれているかを調べる *) (* search : tree_t -> int -> bool *) let rec search tree data = match tree with Empty -> false | Leaf (n) -> false | Node (t1, n, t2) -> false (* search t1 data *) (* search t2 data *) ``` --- ## 17.4 ２分探索木（search編本体） ```ocaml= (* 目的：dataが２分探索木treeに含まれているかを調べる *) (* search : tree_t -> int -> bool *) let rec search tree data = match tree with Empty -> false | Leaf (n) -> data = n | Node (t1, n, t2) -> if data = n then true else if data < n then search t1 data else search t2 data ``` #### 完成♡ --- ## 17.4 ２分探索木（search編テスト） ```ocaml= val test1 : bool = true val test2 : bool = true val test3 : bool = true val test4 : bool = true val test5 : bool = true val test6 : bool = true val test7 : bool = true val test8 : bool = true val test9 : bool = true ``` --- ## 17.4 ２分探索木（insert_tree編） ##### ２分探索木に新しい要素を追加する関数insert_treeを考える。 ##### 目的と例は次のようになります。 ```ocaml= (* 目的：２分探索木treeにdataを追加した２分探索木を返す *) (* insert_tree : tree_t -> int -> tree_t *) let rec insert_tree tree data = Empty (* テスト *) let test1 = insert_tree Empty 3 = Leaf (3) let test2 = insert_tree (Leaf (3)) 2 = Node (Leaf (2), 3, Empty) let test3 = insert_tree (Leaf (3)) 3 = Leaf (3) let test4 = insert_tree (Leaf (3)) 4 = Node (Empty, 3, Leaf (4)) let test5 = insert_tree tree5 4 = Node (Node (Leaf (1), 2, Node (Empty, 3, Leaf (4))), 6, Node (Empty, 7, Leaf (9))) ``` ##### test3はすでに木に含まれている要素を挿入した場合であり、今回は重複させず、元の木をそのまま返すことにする。 --- ## 17.4 ２分探索木（insert_tree編テンプレート） ```ocaml= (* 目的：２分探索木treeにdataを追加した２分探索木を返す *) (* insert_tree : tree_t -> int -> tree_t *) let rec insert_tree tree data = match tree with Empty -> Empty | Leaf (n) -> Empty | Node (t1, n, t2) -> Empty (* insert_tree t1 data *) (* insert_tree t2 data *) ``` --- ## 17.4 ２分探索木（insert_tree編本体） ```ocaml= (* 目的：２分探索木treeにdataを追加した２分探索木を返す *) (* insert_tree : tree_t -> int -> tree_t *) let rec insert_tree tree data = match tree with Empty -> Leaf (data) | Leaf (n) -> if data = n then Leaf (n) else if data < n then Node (Leaf (data), n, Empty) else Node (Empty, n, Leaf (data)) | Node (t1, n, t2) -> if data = n then Node (t1, n, t2) else if data < n then Node (insert_tree t1 data, n, t2) else Node (t1, n, insert_tree t2 data) ``` --- ## 17.4 ２分探索木（insert_tree編本体） ```ocaml= (* テスト *) let test1 = insert_tree Empty 3 = Leaf (3) let test2 = insert_tree (Leaf (3)) 2 = Node (Leaf (2), 3, Empty) let test3 = insert_tree (Leaf (3)) 3 = Leaf (3) let test4 = insert_tree (Leaf (3)) 4 = Node (Empty, 3, Leaf (4)) let test5 = insert_tree tree5 4 = Node (Node (Leaf (1), 2, Node (Empty, 3, Leaf (4))), 6, Node (Empty, 7, Leaf (9))) ``` ```ocaml= val test1 : bool = true val test2 : bool = true val test3 : bool = true val test4 : bool = true val test5 : bool = true ``` --- ## 17.4 ２分探索木（まとめ） このように２分探索木を使った探索や２分探索木への挿入は、木の構造に従った再帰をするだけで簡単に実現可能である。同様の探索や挿入はリストを使っても行うことができるが、探索の**効率**が大きく異なる。 ２分探索木は挿入の順番によっては出来上がる木のバランスが悪くなってしまう場合があるが、それでも平均的にはリストを使った探索よりもずっと速くなる。大量のデータに対して探索する必要があるときには２分探索木の使用を考えるといいだろう。 --- ## 17.5 多相型の宣言 ##### これまでに定義した木は、内部に整数しか持つことができない。これは ```ocaml= (* 木を表す型 *) type tree_t = Empty (* 空の木 *) | Leaf of int (* 葉 *) | Node of tree_t * int * tree_t (* 節 *) ``` ##### のように木を表す型 tree_t の定義の中にintが直接、書き込まれてしまっているからである。リストの型が 'a list という多相型で int list にも string list にも使えるようになっていたのと同じように、木の型も多相型になっている方が使える範囲が広がる。多相の型を宣言するには次のようにする。 ```ocaml= (* 多相の木を表す型 *) type 'a tree_t = Empty (* 空の木 *) | Leaf of 'a (* 葉 *) | Node of 'a tree_t * 'a * 'a tree_t (* 節 *) ``` --- ## 17.5 多相型の宣言 この定義を使うと、要素の型が整数ではない木も作ることができるようになる。<br> 例えば<br> Node (Empty, "a", Leaf ("b")) なら string tree_t型になり、 Node (Leaf (false), true, Empty) なら bool tree_t型になる。 --- ## 17.5 多相型の宣言 木の型を多相型に変更しても、これまでにこの章で作成してきたsearchやinsert_treeはそのまま使える。これらの関数はこれまで ```ocaml= # search ;; val search : tree_t -> int -> bool = <fun> # insert_tree ;; - : tree_t -> int -> tree_t = <fun> # ``` という型だったが、多相の木の型を使って同じ関数を定義すると ```ocaml= # search ;; - : 'a tree_t -> 'a -> bool = <fun> # insert_tree ;; - : 'a tree_t -> 'a -> 'a tree_t = <fun> # ``` という型になる。 --- ## 17.5 多相型の宣言 リストと同様、木のようなデータ構造を定義するときには、なるべく多相にしておくと使える範囲が広がる。 先ほど定義したtree_t ```ocaml= (* 多相の木を表す型 *) type 'a tree_t = Empty (* 空の木 *) | Leaf of 'a (* 葉 *) | Node of 'a tree_t * 'a * 'a tree_t (* 節 *) ``` は引数としてひとつしか受け取らなかったが、引数は複数にすることもできる。例えば ```ocaml= (* 多相の木を表す型(引数が複数) *) type ('a, 'b) tree_t = Empty (* 空の木 *) | Leaf of 'a * 'b (* 葉 *) | Node of ('a, 'b) tree_t * 'a * 'b * ('a, 'b) tree_t (* 節 *) ``` とすれば('a, 'b)というふたつの型の組を引数にとることができる。これは、キーの型が'aで値の型が'bであるような **連想木(association tree)** の型と捉えることができる。 --- ## 問題 17.9 多相の木の型を使って17.3節で作った関数sum_treeを定義せよ。この関数の型は何になるか。なぜ、この関数が受け取る木の要素は多相にならないのか。17.3節で作った関数sum_treeを以下に示す。 ```ocaml= (* 木を表す型 *) type tree_t = Empty (* 空の木 *) | Leaf of int (* 葉 *) | Node of tree_t * int * tree_t (* 節 *) (* 目的：treeに含まれる整数をすべて加える *) (* sum_tree : tree_t -> int *) let rec sum_tree tree = match tree with Empty -> 0 | Leaf (n) -> n | Node (t1, n, t2) -> sum_tree t1 + n + sum_tree t2 ``` --- ## 問題 17.9 多相の木の型を使って17.3節で作った関数sum_treeを定義すると以下のようになる。 ```ocaml= (* 多相の木を表す型 *) type 'a tree_t = Empty (* 空の木 *) | Leaf of 'a (* 葉 *) | Node of 'a tree_t * 'a * 'a tree_t (* 節 *) (* 目的：treeに含まれる整数をすべて加える *) (* sum_tree : int tree_t -> int *) let rec sum_tree tree = match tree with Empty -> 0 | Leaf (n) -> n | Node (t1, n, t2) -> sum_tree t1 + n + sum_tree t2 ``` さらに、関数を実行する。 ```ocaml= # sum_tree ;; - : int tree_t -> int = <fun> ``` --- ## 17.6　停止性 p.81の第２段落およびp.191の下半分を各自読んでみてください。