<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, .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: 4.0vw;} .reveal h3 {font-size: 2.8vw;} .reveal h4 {font-size: 2.6vw;} .reveal h5 {font-size: 2.4vw;} .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: 4% 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+ */ } </style> <!-- --------------------------------------------------------------------------------------- --> # 第１３章　一般化と高階関数 --- ## 章に入る前に　一般化とは ### 同じプログラムをより多くの場面で使えるようにすること ### この章ではデータの一般化,関数一般化,型の一般化をそれぞれの章でやっていきます！ --- # １３.１　データの一般化 データ定義( 9.6 節) ```ocaml= (* 学生ひとり分のデータ(名前,点数,成績) を表す型　*) type gakusei_t = { name : string; (*名前*) tensuu : int; (*点数*) seiseki : string; (*成績*) } (* gakusei_t list　は -[] 空リスト,あるいは -first :: rest 最初の要素が first で残りのリストがrest (first gakusei_t 型, rest が自己参照のケース) ``` --- ### 一般化して 1ヶ所 に記述できるようにしたい！ 具体的には,2つの似た関数の共通部分をくくりだして一般化したい！ それにはまず、2つの関数の異なる部分を見つける 9.6節で示した関数 count_A , count_A をまねた count_B ```ocaml= (*目的：学生リスト lst のうち成績が A の人の数を返す*) (* count_A ： gakusei_t list -> int *) let rec count_A lst = match lst with [] -> 0 | {name = n; tensuu = t; seiseki = s} :: rest -> if s = "A" then 1 + count_A rest else count_A rest ``` ```ocaml= (* 目的：学生リスト lst のうち成績が B の人の数を返す *) (* count_B : gakusei_t list -> int *) let rec conut_B lst = match lst with [] -> 0 | {name = n; tensuu = t; seiseki = s} :: rest -> if s = "B" then 1 + count_B rest else count_B rest ``` --- ### 一般化を実際にやってみる 2行目 2つの関数の型を count_A , count_B から count に 2行目 string 型を受け取る 成績がAなのかBなのか 3,5行目　引数 seiseki0 を使って成績の人の数を返す ```ocaml= (* 目的：学生リスト lst のうち成績が seiseki0 の人の数を返す *) (* count : gakusei_t list -> string -> int *) let rec conut lst seiseki0 = match lst with [] -> 0 | {name = n; tensuu = t; seiseki = s} :: rest -> if s = seiseki0 then 1 + count rest seiseki0 else count rest seiseki0 ``` --- 9.6 節 ( p86 ) をもとに定義したデータ ```ocaml= let lst1 = [] let lst2 = [{name = "asano"; tensuu = 70; seiseki = "B"}] let lst3 = [{name = "asano"; tensuu = 70; seiseki = "B"}; {name = "miura"; tensuu = 85; seiseki = "A"}] let lst4 = [{name = "satou"; tensuu = 80; seiseki = "A"}; {name = "asano"; tensuu = 70; seiseki = "B"}; {name = "miura"; tensuu = 85; seiseki = "A"}] ``` --- ２つの関数を作らなくても "A"と"B" 渡す関数を変えるだけ ```ocaml= # count lst4 "A" ;; - : int = 2 # ``` ```ocaml= # count lst4 "B" ;; - : int = 1 # ``` --- プログラム中に count_A count_B を何回も使っている場合 関数 count を count_A と count_B で呼び出すだけ ```ocaml= (* 目的：学生リスト lst のうち成績が A の人の数を返す *) (* count_A : gakusei_t list -> int *) let conut_A lst = count lst "A" (* 目的：学生リスト lst のうち成績が B の人の数を返す *) (* count_B : gakusei_t list -> int *) let conut_B lst = count lst "B" ``` --- ### テスト ```ocaml= (* テスト *) let count lst1 "A" = 0 let count lst2 "A" = 0 let count lst2 "B" = 1 let count lst3 "A" = 1 let count lst3 "B" = 1 let count lst4 "A" = 2 let count lst4 "B" = 1 ``` --- ## 問題 1 (13章) 問題8.3で定義したperson_t型のリストを受け取ったら,その中から指定された血液型の人の数を返す関数 count_ketsueki をデザインレシピ(p82)にしたがって作れ。 --- #### データ定義 各人の名前,身長,体重,誕生日と血液型の情報を格納するレコード型 person_t ```ocaml= (* 人に関わる情報を格納するレコード型 *) type person_t = {name : string; (*名前*) shincho : float; (*身長*) taijuu : float; (*体重*) tsuki : int; (*月*) hi : int; (*日*) ketsueki : string; (*血液*) } (* person_t list は -[] 空リスト,あるいは -first :: rest 最初の要素が first で残りのリストがrest (first person_t 型, rest が自己参照のケース) *) ``` --- #### データ定義 その型を持つ三人のデータ(p64 問題 8.3)と person_t型のリスト lst ```ocaml= (* レコード型 person_t を持つ三人のデータ *) let person_1 = {name = "asano"; shincho = 1.74; taijuu = 59.5; tsuki = 5; hi = 30; ketsueki = "AB" } let person_2 = {name = "miura"; shincho = 1.81; taijuu = 78.0; tsuki = 11; hi = 10; ketsueki = "A" } let person_3 = {name = "satou"; shincho = 1.67; taijuu = 56.4; tsuki = 2; hi = 17; ketsueki = "A" } (* person_t 型のリスト lst *) let lst = [ person_1; person_2; person_3 ] ``` --- ### 本体 ```ocaml= (*目的 : person_t 型のリスト lst のうち,指定された血液型の人の数を返す*) (* count_k : person_t list -> string -> int *) let rec count_ketsueki lst ketsueki0 = match lst with [] -> 0 | {name = n; shincho = s; taijuu = ta; tsuki = ts; hi = h; ketsueki = k} :: rest -> if k = ketsueki0 then 1 + count_ketsueki rest ketsueki0 else count_ketsueki rest ketsueki0 ``` --- ### テスト ```ocaml= (* テスト *) let test1 count_ketsueki [] = 0 let test2 count_ketsueki lst "A" = 2 let test3 count_ketsueki lst "B" = 0 let test4 count_ketsueki lst "AB" = 1 let test4 count_ketsueki lst "O" = 0 ``` --- # １３.２ 関数の一般化とmap ### 13.2節では関数の一般化をしていきます map というのは関数のことで、章を進める過程で使っていきます --- 今回も 2つの似た関数の共通部分をくくりだして、一般化してみたい そのために,2つの関数の異なる部分を見つける --- 下記にあるのは実数のリスト lst を受け取って各要素の平方根のリストを返す関数 map_sqrt sqrt : 平方根を返す関数, float : 少数を多く表せる型 実数：数直線上に書ける数, 自然数 , 0 , 少数 , √ とか全ての数 ```ocaml= (* 目的 : 実数のリスト　lst を受け取り各要素の平方根のリストを返す　*) (* map_sqrt : float list -> float list *) let rec map_sqrt lst = match lst with [] -> [] | first :: rest -> sqrt first :: map_sqrt rest ``` --- もう一度 9.6 の gakusei_t 型 のデータを受け取る ```ocaml= (* 学生ひとり分のデータ(名前,点数,成績) を表す型　*) type gakusei_t = { name : string; (*名前*) tensuu : int; (*点数*) seiseki : string; (*成績*) } (* gakusei_t list　は -[] 空リスト,あるいは -first :: rest 最初の要素が first で残りのリストがrest (first gakusei_t 型, rest が自己参照のケース) ``` --- 8.6(p66)の成績を付ける関数 hyouka を受け取る ```ocaml= (* 目的 : 学生のデータ gakusei を受け取り成績を入れたリストを返す *) (* hyouka : gakusei_t -> gakusei_t *) let hyouka gakusei = match gakusei with {name = n; tensuu = t; seiseki = s} -> if t >= 80 then {name = n; tensuu = t; seiseki = "A"} else if t >= 70 then {name = n; tensuu = t; seiseki = "B"} else if t >= 60 then {name = n; tensuu = t; seiseki = "C"} else {name = n; tensuu = t; seiseki = "D"} } ``` --- この2つの gakusei_t 型 のリストと 関数 hyouka を使って map_hyouka を作成します ```ocaml= (* 目的 : 実数のリスト lst を受け取り成績を入れたリストを返す *) (* map_hyouka : gakusei_t list -> gakusei_t list *) let rec map_hyouka lst = match lst with [] -> [] | first :: rest -> hyouka first :: map_hyouka rest ``` --- 今回のポイントというのは13,1と同じように map_sqrt と map_hyouka 共通部分をくくって一般化したい！ そのために,異なる部分を見つける！ ```ocaml= (* 目的 : 実数のリスト　lst を受け取り各要素の平方根のリストを返す　*) (* map_sqrt : float list -> float list *) let rec map_sqrt lst = match lst with [] -> [] | first :: rest -> sqrt first :: map_sqrt rest ``` ```ocaml= (* 目的 : 実数のリスト lst を受け取り成績を入れたリストを返す *) (* map_hyouka : gakusei_t list -> gakusei_t list *) let rec map_hyouka lst = match lst with [] -> [] | first :: rest -> hyouka first :: map_hyouka rest ``` --- 3行目の関数 map_sqrt と map_hyouka から 関数 map に 5行目の first に対しての操作の違い( map_sqrt では sqrt を呼び出し,map_hyouka では hyouka を呼び出し) なので、5行目の first に対して、引数 f を適応する( 13.1 の seiseki0 と同様) ```ocaml= (* 目的 : 関数 f とリスト lst を受け取り f を施したリストを返す　*) (* map : ('a -> 'b) -> 'a list -> 'b list *) let rec map f lst = match lst with [] -> [] | first :: rest -> f first :: map f rest ``` --- 実際には5行目( | first :: rest -> f first :: map f rest ) の f first の f は first の関数として適応し、 その後に続く map f rest は map の引数として適用している ```ocaml= (* 目的 : 関数 f とリスト lst を受け取り f を施したリストを返す　*) (* map : ('a -> 'b) -> 'a list -> 'b list *) let rec map f lst = match lst with [] -> [] | first :: rest -> f first :: map f rest ``` 関数 f を一つ目の引数として受け取る関数 map --- 関数 map が 関数 sqrt を受け取って 関数 map はリストの各要素に対して sqrt を施したリストを返す ```ocaml= # map sqrt [2.0; 3.0] ;; - : float list = [1.41421356237309515; 1.73205080756887719] # ``` 関数 map が 関数 sin を受け取って 関数 map はリストの各要素に対して sin を施したリストを返す ```ocaml= # map sin [2.0; 3.0] ;; - : float list = [0.909297426825681709; 0.141120008059867214] # ``` --- 関数型言語では "関数" を整数や実数と同じように普通の "値" として 関数に渡すことができる。さらに関数を "結果" としても返すことができる。このことを ### 関数が first-class の値である という言い方をする。 --- map_sqrt では 関数 f の部分で実行したいから sqrt は関数 map の一つ目の引数として渡す ```ocaml= (* 目的 : 実数のリスト lst を受け取り各要素の平方根のリストを返す*) (* map_sqrt : float list -> float list *) let map_sqrt lst = map sqrt lst ``` --- また、もともと ocaml に定義されていた sqrt ではなくても ユーザが定義した関数を渡すこともできる map_hyouka では hyouka を map の引数として渡す ```ocaml= (* 目的 : 実数のリスト　lst を受け取り成績を入れたリストを返す *) (* map_hyouka : gakusei_t list -> gakusei_t list *) let map_hyouka lst = map hyouka lst ``` --- map のように 関数 を 引数 として受け取る関数のことを ### 高階関数 (higher-order function) と呼びます --- ## List.map ocaml にはあらかじめ List.map という今回,定義した map と同じ役割の関数が定義されているので、p124 の関数 map を確認しながら List.map を使うと、とても便利です！ --- ## 問題 2 (13章) 問題8.3で定義したperson_t型のリストを受け取ったら,その中に出てくる人の名前のリストを返す関数 person_name をデザインレシピにしたがって作れ --- ### データ定義 p64 問題 8.3 各人の名前,身長,体重,誕生日と血液型の情報を格納するレコード型 person_t とその型を持つ三人のデータ ```ocaml= (* 人に関わる情報を格納するレコード型 *) type person_t = {name : string; (*名前*) shincho : float; (*身長*) taijuu : float; (*体重*) tsuki : int; (*月*) hi : int; (*日*) ketsueki : string; (*血液*) } (* person_t list は -[] 空リスト,あるいは -first :: rest 最初の要素が first で残りのリストがrest (first person_t 型, rest が自己参照のケース) *) ``` --- ### データ定義 ```ocaml= (* レコード型 person_t を持つ三人のデータ *) let person_1 = {name = "asano"; shincho = 1.74; taijuu = 59.5; tsuki = 5; hi = 30; ketsueki = "AB" } let person_2 = {name = "miura"; shincho = 1.81; taijuu = 78.0 tsuki = 11; hi = 10; ketsueki = "A" } let person_3 = {name = "satou"; shincho = 1.67; taijuu = 56.4; tsuki = 2; hi = 17; ketsueki = "B" } (*person_t list 型のデータをリスト lst として定義する*) (*person_t list 型のデータ*) let lst = [ person_1 ; person_2 ; person_3 ;] ``` --- ### 本体 先に、person_t 型のデータのうち人の名前を返す 関数 name_hoge ```ocaml= (* 目的 : person_t 型のデータのうち人の名前を返す*) (* name_hoge : person_t -> string *) let name_hoge person = match person with {name = n; shincho = s; taiju = t; tsuki = ts; hi = h; ketsueki = k} -> n ``` --- ### テスト ```ocaml= (* テスト *) # let test1 = name_hoge person_1 ;; val test1 : string = "asano" # let test2 = name_hoge person_2 ;; val test2 : string = "miura" # let test3 = name_hoge person_3 ;; val test3 : string = "satou" # let test1 = name_hoge person_1 = "asano" let test2 = name_hoge person_2 = "miura" let test3 = name_hoge person_3 = "satou" ``` --- map を定義しないで、あらかじめ定義されていた List.map を使う ### 本体 ```ocaml= (* 目的：name_hoge lst に含まれる人の名前のリストを返す *) (* person_namae : person_t list -> string list *) let person_namae lst = List.map name_hoge lst ``` ### テスト ```ocaml= (* テスト *) let test1 = person_namae [] = [] let test2 = person_namae lst = ["asano"; "miura"; "satou"] ``` --- # １３.３ 多相型と多相関数 p124 の関数 map にも出てきた　'a (アルファ) と 'b (ベータ) ,この 'a 'b は ### 型変数 と呼ばれ、「どのような型でもよい」ということ表している --- 例えば、リストの長さを求める関数 length だと リストの長さを求めるだけならリストの要素の型は 何でもいいので引数として 'a list を受け取っている ```ocaml= (* 目的 : 受け取ったリスト　lst の長さを求める *) (* length : 'a list -> int *) let rec length lst = match lst with [] -> 0 | first :: rest -> 1 + length rest ``` lengthを let lst = [1; 2; 3] のような int list で呼び出せば 'a は 型変数なので int になる --- どのような型でもいい性質を ### 多相性(polymorphism) と呼び、型変数を含むものを ### 多相型 と呼ぶ --- 多相型を持つ関数のことを ### 多相関数(polymorphism function) と呼ぶ。逆に多相でない関数のことを 単相関数(monomorphic function)と呼ぶ --- int -> bool 型の関数 is_zero 引数が0かどうかを調べる関数で 'a (アルファ) は int になり、'b (ベータ)は bool になる ```ocaml= # let is_zero n = n = 0 ;; val is_zero : int -> bool = < fun > # ``` --- int -> bool 型の関数 is_zero 引数が0かどうかを調べる関数で 'a (アルファ) は int になり、'b (ベータ)は bool になる 関数 map で整数のリストを引数として渡すと 真偽値のリストが結果として返る ```ocaml= # map is_zero [2; 1; 0; -1; -2] ;; - : bool list = [false; false; true; false; false] # ``` ```ocaml= (* 目的 : 関数 f とリスト lst を受け取り f を施したリストを返す　*) (* map : ('a -> 'b) -> 'a list -> 'b list *) let rec map f lst = match lst with [] -> [] | first :: rest -> f first :: map f rest ``` --- # １３.４ 値としての関数 数字を関数の引数に渡すのと同じように、関数をほかの関数の引数として自由に渡すことができる。 --- 数字を入力するとその型と値を表示するように ```ocaml= # 3 ;; - : int = 3 # ``` 関数を入力するとその型と値を表示してくれる ```ocaml= # sqrt ;; - : float -> float = < fun > # ``` --- 関数 twice7 は引数として f を受け取り、 f を7に対して2回、適用するような関数 ```ocaml= # let twice7 f = f (f 7) ;; val twice7 : (int -> int) -> int = < fun > # ``` --- int -> int 型の関数 add3 は、引数 x に3を加える関数 ```ocaml= # let add3 x = x + 3 ;; val add3 : int -> int = < fun > # ``` --- 関数 add3 を関数 twice7 に渡すと 7 に 3 が 2回 適応されて 13 が返った 7 + (3 + 3) = 13 ```ocaml= # twice7 add3 ;; val int = 13 # ``` twice7 add3 (*twice7 add3 という関数呼び出しに、最初に f (f 7) に置き換わって *) add3 (add3 7) (* f が引数である add3 に置き換わる*) add3 10 (* add3 に 3 が適応され*) 13　(* 13 が返る *) ```ocaml= # let twice7 f = f (f 7) ;; val twice7 : (int -> int) -> int = < fun > # ``` --- 高階関数の型は複雑だが、強力な型チェック(p24)になっている。twice7 のように型を見れば関数を一つ受け取って、整数を返すことがわかる。 高階関数は受け取る関数の型は指定されているので、型チェックを取った後は型エラーが起きないようになっている 〇 (int -> int) -> int (* (int -> int) 型の値を一つ受け取ってintを返す関数の型 *) ✖ int -> bool (* int 型の値を受け取り bool を返す関数の型 *) f の型が int -> bool になってしまうと (f 7) は bool型になる f の引数は int 型でなければいけない ```ocaml= # let twice7 f = f (f 7) ;; val twice7 : (int -> int) -> int = < fun > # ``` --- # １３.５ 関数を返す関数 13.4では関数も普通の値として示せることや引数として受け取ってくることを説明しました。 それ以外にも関数を変数に入れることもできたり、関数のリストも作ることができる 13.5では関数を返す関数をやっていきます --- 13.4にでてきた高階関数 twice7 では 「その関数を 7 に対して 2回 適用させる」という関数でしたが　7 以外にも適用させた方が便利ということで「その関数を 2回 適用させる関数」twice を作りたい ```ocaml= # let twice7 f = f (f 7) ;; val twice7 : (int -> int) -> int = < fun > # ``` --- #### 「その関数を 2回 適用させる関数」twice の具体的な働きとは？ twice に13.4で定義した add3 (引数に 3 を加える関数)を受け取る ```ocaml= twice add3 ``` --- twice add3 に 7 を渡すと 7 に add3 2回 適用され 13 が返ってきます ```ocaml= (twice add3) 7 13 ``` 「その関数を 2回 適用させる関数」twice をそんなふうにしたい --- twice は 引数 として関数を受け取る その関数を f とすると ```ocaml= let twice f = ･･･ ``` --- 関数 twice が返す結果も関数なので twice が返す結果の関数を g とする ```ocaml= let twice f = let g ``` 関数 g は「引数に対して f を 2回 適用する関数」 ```ocaml= let twice f = let g x = f (f x) in ･･･ ``` 13.3で出てきた関数 twice7 と働きが似ている ```ocaml= (*引数として f を受け取り f を 7 に対して2回 適用するような関数*) # let twice7 f = f (f 7) ;; val twice7 : (int -> int) -> int = < fun > # ``` --- 最後に「引数に対して f を 2回 適用する関数」を返したいので 最後の行では g そのものを入れる ```ocaml= let twice f = let g x = f (f x) in g ``` twice は 引数として関数 f を受け取り g は引数 x を受け取ったら f (f x) を評価して返す関数に g という名前をつけている。 --- ##### ( twice add3 ) 7 がどのように評価されるかを見ていく 先に twice add3 が実行されると ```ocaml= let twice add3 = ``` g が返ってくる ```ocaml= let g x = add3 (add3 x) ``` g x に 7 が渡され ```ocaml= let g 7 = add3 (add3 7) ``` 13 が返る ```ocaml= in 13 ;; ``` --- ```ocaml= # let twice f = let g x = f (f x) in g ;; val twice : ('a -> 'a) -> 'a -> 'a = < fun > # ``` twice はまず 'a -> 'a 型を受け取る。なので f の型は 'a -> 'a 型 (* x の型が int 型 とは限らないから 'a -> 'a 型 *) twice が 'a -> 'a 型の f を受け取ると ,twice は 'a -> 'a 型の関数を返す。括弧を使うと ( 'a -> 'a ) -> ( 'a -> 'a ) です これが f を 2回 適用するような関数です --- 一方で、 twice には別に見方もあり、A -> 'a -> 'a という形にも見える。2引数関数 A -> B -> C の型は引数をひとつずつ 2回 受け取る関数である。twice add3 7 のように 'a -> 'a 型のものと 'a 型のものを受け取って 'a 型で返す　と見ることもできる。 --- 一度 twice を定義しておくことで、どのような値に関しても 2回 適用させることができる。2 回適用する関数を別の関数にすることもできる。 2 倍する関数を定義すると ```ocaml= # let times2 x = x * 2 ;; val times2 : int -> int = < fun > # ``` (twice times2 ) 7 で 28 が返る --- twice add3 は add3を2回行う関数、つまり、6を加える関数になるので add6 を変数に入れると ```ocaml= # let add6 = twice add3 ;; val add6 : int -> int = < fun > # ``` --- そうすれば、以後は add6 という名前で6を加えることができるようになる ```ocaml= # add6 8 ;; - : int = 14 ``` ```ocaml= # add6 9 ;; - : int = 15 # ``` --- ```ocaml= let add6 = twice add3 ``` は 「 add3 を 2回 行う関数を add6 とする」 という普通の定義で読むことができる --- ## 問題 3 (13章) 次の型を持つ関数を定義せよ。 ```ocaml= (1) 'a -> 'a let g x = x ;; val g : 'a -> 'a = <fun> (2) 'a -> 'b -> 'a let g x u = x ;; val g : 'a -> 'b -> 'a = <fun> (3) 'a -> 'b -> 'b let g x u = u ;; val g : 'a -> 'b -> 'b = <fun> (4) 'a ->('a -> 'b) -> 'b let g x u = u x ;; val g : 'a -> ('a -> 'b) -> 'b = <fun> (5) ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c let h g f x = f (g x) val h : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c = <fun> ``` --- ## 問題 4 (13章) 関数をふたつ受け取ったら,そのふたつの関数を合成した関数を返す関数 compose を作れ。例えば、( compose time2 add3 ) 4 とすると 2 * (3 + 4) = 14 が返ってくる。 compose の型はどうなるか。 ```ocaml= # let time2 n = n * 2 ;; val time2 : int -> int = <fun> ``` ```ocaml= # let add3 n = n + 3 ;; val add3 : int -> int = <fun> ``` --- ```ocaml= (* 目的 : 関数をふたつ受け取ったら、そのふたつの関数を合成した関数を返す *) (* compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b *) let compose f g = let z n = f (g n) in z let h f g n = f (g n) (*テスト*) let test1 = (compose time2 add3) 4 = 14 ``` --- ## 問題 5 (13章) 上で作った twice に twice 自身を渡して　twice twice とすることができる。ここで返ってくる関数はどのような関数か。その型は何か。 ```ocaml= let twice f = let g n = f (f n) in g let tt = twice twice let add3 x = x + 3 let hoge = tt add3 ``` --- ```ocaml= (*実行したときの関数の型*) val twice : ('a -> 'a) -> 'a -> 'a = <fun> val tt : (int -> int) -> int -> int = <fun> val add3 : int -> int = <fun> val hoge : int -> int = <fun> ``` ```ocaml= (* テスト *) # hoge 1 ;; - : int = 13 # ``` 関数 hoge 1 は 13 を返しているので、 よって、 twice twice は 受け取った関数を 4回 実行するような関数。 tt ( twice twice ) の型は (int -> int) -> int -> int --- # １３.６ 確定点に隣接する点の　　最短距離の更新 12.4節の問題12.3ではステップ1を行う、始点の最短距離を0にする shokika を作った。ステップ2では始点が U に、それ以外の点が V に入る。ステップ3は、V にまだ要素が残っているので、ここではステップ4を実装してみる。 --- ダイクストラのアルゴリズムのステップ4では、直前に確定した点 p につながるすべての点について(必要に応じて)最短距離を更新させる。「全ての点について最短距離を更新する」という部分から map が使えそうなことがわかる。しかし、全ての点で更新するわけではなく、直前に確定した点 p につながっている点を更新する。 --- 説明した文章を次のように解釈する。 V に入っているすべての点について,以下を行う。 ・点 P につながっているかを調べる。 ・つながっていなかったら,何も変更しないでそのまま返す。 ・つながっていたら (必要に応じて) 最短距離を更新する。 --- ## 問題 6 (13章) 直前に確定した駅 ｐ ( eki_t 型 ) と未確定の駅 ｑ ( eki_t 型 ) を受け取ったら, p と q が直接つながっているかどうかを調べ,つながっていたら q の最短距離と手前リストを必要に応じて更新したもの,つながっていなかったらもとの q をそのまま返す関数 koushin1 をデザインレシピにしたがって作れ。 --- ### データ定義 namae, saitan_kyori, temae_list の情報が入った駅を定義 ```ocaml= type eki_t = { namae : string; (* 駅名 (漢字) *) saitan_kyori : float; (* 最短距離 *) temae_list : string list; (* 手前の駅名 (漢字) のリスト *) } let eki1 = {namae="池袋"; saitan_kyori = infinity; temae_list = []} let eki2 = {namae="新大塚"; saitan_kyori = 1.2; temae_list = ["新大塚"; "茗荷谷"]} let eki3 = {namae="茗荷谷"; saitan_kyori = 0.; temae_list = ["茗荷谷"]} let eki4 = {namae="後楽園"; saitan_kyori = infinity; temae_list = []} ``` --- ### データ定義 8.7 節で定義した駅間の情報と 10.7 節の問題 10.11 で定義された get_ekikan_kyori ```ocaml= (* 駅間の情報を格納するレコード型 *) type ekikan_t = { kiten : string; (* 起点 *) shuten : string; (* 終点 *) keiyu : string; (* 経由路線名 *) kyori : float; (* 距離 *) jikan : int; (* 所要時間 *) } (* 目的：ふたつの駅の間の距離を求める *) (* get_ekikan_kyori : string -> string -> ekikan_t list -> float *) #use "metro.ml" global_ekikan_list の方 let rec get_ekikan_kyori eki1 eki2 lst = match lst with [] -> infinity | {kiten = k; shuten = s; keiyu = y; kyori = r; jikan = j} :: rest -> if (eki1 = k && eki2 = s) || (eki1 = s && eki2 = k) then r else get_ekikan_kyori eki1 eki2 rest (* テスト *) let test1 = get_ekikan_kyori "代々木上原" "乃木坂" global_ekikan_list = infinity let test2 = get_ekikan_kyori "代々木上原" "代々木公園" global_ekikan_list = 1. let test3 = get_ekikan_kyori "代々木上原" "表参道" global_ekikan_list = infinity let test4 = get_ekikan_kyori "代々木公園" "明治神宮前" global_ekikan_list = 1.2 ``` --- ### 本体 ```ocaml= (* p と q を受け取り、つながっていたら更新、つながっていなければそのまま q 返す*) (* koushin1 : eki_t -> eki_t -> eki_t *) let koushin1 p q = match (p, q) with ({namae = pn; saitan_kyori = ps; temae_list = pt}, {namae = qn; saitan_kyori = qs; temae_list = qt}) -> let kyori = get_ekikan_kyori pn qn global_ekikan_list in if kyori = infinity then q else if ps +. kyori < qs then {namae = qn; saitan_kyori = ps +. kyori; temae_list = qn :: pt} else q ``` 8行目の < は最短距離が p 経由の方が小さくなっていた場合を評価している +. は kyori が float 型なので 実数専用の　+. を使っている --- ### テスト ```ocaml= (* テスト *) let test1 = koushin1 eki3 eki1 = eki1 let test2 = koushin1 eki3 eki2 = eki2 let test3 = koushin1 eki3 eki3 = eki3 let test4 = koushin1 eki3 eki4 = {namae="後楽園"; saitan_kyori = 1.8; temae_list = ["後楽園"; "茗荷谷"]} let test5 = koushin1 eki2 eki1 = {namae="池袋"; saitan_kyori = 3.0; temae_list = ["池袋"; "新大塚"; "茗荷谷"]} let test6 = koushin1 eki2 eki2 = eki2 let test7 = koushin1 eki2 eki3 = eki3 let test8 = koushin1 eki2 eki4 = eki4 ``` --- ## 問題 7 (13章) 直前に確定した駅 ｐ ( eki_t 型)と未確定の駅のリスト v ( eki_t list 型)を受け取ったら, 必要な更新処理を行った後の未確定の駅のリストを返す関数 koushin をデザインレシピにしたがって作れ。 --- ### データ定義 namae, saitan_kyori, temae_list の情報が入った駅を定義 ```ocaml= let eki1 = {namae="池袋"; saitan_kyori = infinity; temae_list = []} let eki2 = {namae="新大塚"; saitan_kyori = 1.2; temae_list = ["新大塚"; "茗荷谷"]} let eki3 = {namae="茗荷谷"; saitan_kyori = 0.; temae_list = ["茗荷谷"]} let eki4 = {namae="後楽園"; saitan_kyori = infinity; temae_list = []} let lst = [eki1; eki2; eki3; eki4] ``` --- ### 本体 ```ocaml= (* 目的：未確定の駅のリスト v を必要に応じて更新したリストを返す *) (* koushin : eki_t -> eki_t list -> eki_t list *) let koushin p v = let f q = koushin1 p q in List.map f v ``` --- ### テスト ```ocaml= (* テスト *) let test1 = koushin eki2 [] = [] let test2 = koushin eki2 lst = [{namae="池袋"; saitan_kyori = 3.0; temae_list = ["池袋"; "新大塚"; "茗荷谷"]}; eki2; eki3; eki4] ```