《プログラミングの基礎》をReScriptで読む 第17章

[《プログラミングの基礎》](https://www.amazon.co.jp/dp/4781911609/ "Amazonへのリンク")はとても良い本です。
サンプルプログラムをReScriptで書いて、プログラミングの基礎とReScriptを学びます。
# 環境
* macOS Sonoma(バージョン 14.4.1)
* ReScript 11.1.0-rc.8
* @rescript/core 1.2.0
# 第17章
グラフの辺の情報をリストで保持していましたが、二分木で保持するようにして効率化をはかります。
```ReScript:Ex17_1.res
// 年号を表す型
type nengou_t =
  | Meiji(int)  //明治
  | Taisho(int) //大正 
  | Showa(int)  //昭和 
  | Heisei(int) //平成 
  | Reiwa(int)  //令和
 
// 目的：年号を受け取ったら対応する西暦年を返す
// to_seireki : nengou_t -> int
let to_seireki = (nengou) => switch nengou { 
| Meiji(n) => n + 1867 
| Taisho(n) => n + 1911 
| Showa(n) => n + 1925 
| Heisei(n) => n + 1988 
| Reiwa(n) => n + 2018 
}

// テスト
Console.log(to_seireki(Showa(42)) == 1967)
Console.log(to_seireki(Heisei(11)) == 1999)
Console.log(to_seireki(Meiji(41)) == 1908)

// 目的：生まれた年の年号と現在の年号を受け取ったら年齢を返す
// nenrei : nengou_t -> nengou_t -> int
let nenrei = (nengou1, nengou2) =>
  to_seireki(nengou2) - to_seireki(nengou1)
 
// テスト
Console.log(nenrei(Showa(42), Heisei(18)) == 39)
Console.log(nenrei(Heisei(11), Heisei(18)) == 7) 
Console.log(nenrei(Meiji(41), Heisei (17)) == 97)
```
```ReScript:Ex17_2.res
// 日付けを表す型
type year_t =
| January(int) 
| February(int)
| March(int)
| April(int)
| May(int)
| June(int)
| July(int)
| August(int)
| September(int)
| October(int)
| November(int)
| December(int)
```
```ReScript:Ex17_3.res
// 12 星座を表す型
type seiza_t =
  | Capricorus	//山羊座
  | Aquarius		//水瓶座
  | Pisces		  //魚座
  | Aries		    //牡羊座
  | Taurus		  //牡牛座
  | Gemini		  //双子座
  | Cancer		  //蟹座
  | Leo		      //獅子座
  | Virgo		    //乙女座
  | Libra		    //天秤座
  | Scorpius		//蠍座
  | Sagittarius	//射手座
```
```ReScript:Ex17_4.res
open Ex17_2
open Ex17_3

// 目的：日付けを受け取ってきたら星座を返す
// seiza : year_t -> seiza_t
let seiza = (year) => switch year { 
| January(hi) => if hi <= 19 {Capricorus} else {Aquarius}
| February(hi) => if hi <= 18 {Aquarius} else {Pisces}
| March(hi) => if hi <= 20 {Pisces} else {Aries}
| April(hi) => if hi <= 19 {Aries} else {Taurus}
| May(hi) => if hi <= 20 {Taurus} else {Gemini}
| June(hi) => if hi <= 21 {Gemini} else {Cancer}
| July(hi) => if hi <= 22 {Cancer} else {Leo}
| August(hi) => if hi <= 22 {Leo} else {Virgo}
| September(hi) => if hi <= 22 {Virgo} else {Libra}
| October(hi) => if hi <= 23 {Libra} else {Scorpius}
| November(hi) => if hi <= 21 {Scorpius} else {Sagittarius}
| December(hi) => if hi <= 21 {Sagittarius} else {Capricorus}
}

// テスト
Console.log(seiza(June(11)) == Gemini)
Console.log(seiza(June(30)) == Cancer)
Console.log(seiza(September(17)) == Virgo)
Console.log(seiza(October(7)) == Libra)
```
```ReScript:Ex17_5.res
// 木を表す型
type rec tree_t =
| Empty                     // 空の木
| Leaf(int)                 // 葉
| Node(tree_t, int, tree_t) // 節

// 木の例
let tree1 = Empty 
let tree2 = Leaf(3) 
let tree3 = Node(tree1, 4, tree2) 
let tree4 = Node(tree2, 5, tree3) 

// 目的：tree に含まれる整数をすべて 2 倍する
// tree_double : tree_t -> tree_t
let rec tree_double = (tree) => switch tree {
| Empty => Empty 
| Leaf(n) => Leaf (2 * n) 
| Node(t1, n, t2) => Node(tree_double(t1), 2 * n, tree_double(t2))
}

Console.log(tree_double(tree1) == Empty)
Console.log(tree_double(tree2) == Leaf(6))
Console.log(tree_double(tree3) == Node(Empty, 8, Leaf(6)))
Console.log(tree_double(tree4) == Node(Leaf(6), 10, Node(Empty, 8, Leaf(6)))) 
```
```ReScript:Ex17_6.res
// 木を表す型
type rec tree_t =
| Empty                     // 空の木
| Leaf(int)                 // 葉
| Node(tree_t, int, tree_t) // 節

// 木の例
let tree1 = Empty 
let tree2 = Leaf(3) 
let tree3 = Node(tree1, 4, tree2) 
let tree4 = Node(tree2, 5, tree3) 
 
// 目的：tree の各要素に f を適用した木を返す
// tree_map : (int -> int) -> tree_t -> tree_t *) 
let rec tree_map = (f, tree) => switch tree {
| Empty => Empty
| Leaf(n) => Leaf(f(n))
| Node(t1, n, t2) => Node(tree_map(f, t1), f(n), tree_map(f, t2))
}

// テスト
Console.log(tree_map((x) => x, tree1) == Empty)
Console.log(tree_map((x) => x + 1, tree2) == Leaf(4))
Console.log(tree_map((x) => x * 3, tree3) == Node(Empty, 12, Leaf(9)))
Console.log(tree_map((x) => x * 2, tree4) ==
  Node(Leaf(6), 10, Node(Empty, 8, Leaf(6)))) 
```
```ReScript:Ex17_7.res
// 木を表す型
type rec tree_t =
| Empty                     // 空の木
| Leaf(int)                 // 葉
| Node(tree_t, int, tree_t) // 節

// 木の例
let tree1 = Empty 
let tree2 = Leaf(3) 
let tree3 = Node(tree1, 4, tree2) 
let tree4 = Node(tree2, 5, tree3) 
 
// 目的：tree に含まれる節と葉の数の合計を返す
// tree_length : tree_t -> int
let rec tree_length = (tree) => switch tree {
| Empty => 0
| Leaf(_) => 1
| Node(t1, _n, t2) => tree_length(t1) + 1 + tree_length(t2) 
}

// テスト
Console.log(tree_length(tree1) == 0)
Console.log(tree_length(tree2) == 1)
Console.log(tree_length(tree3) == 2)
Console.log(tree_length(tree4) == 4)
```
```ReScript:Ex17_8.res
// 木を表す型
type rec tree_t =
| Empty                     // 空の木
| Leaf(int)                 // 葉
| Node(tree_t, int, tree_t) // 節

// 木の例
let tree1 = Empty 
let tree2 = Leaf(3) 
let tree3 = Node(tree1, 4, tree2) 
let tree4 = Node(tree2, 5, tree3) 
 
// 目的：tree に含まれる節と葉の数の合計を返す
// tree_depth : tree_t -> int
let rec tree_depth = (tree) => switch tree {
| Empty => 0
| Leaf(_) => 0 
| Node(t1, _, t2) => 1 + Js.Math.max_int(tree_depth(t1), tree_depth(t2)) 
}

// テスト
Console.log(tree_depth(tree1) == 0)
Console.log(tree_depth(tree2) == 0)
Console.log(tree_depth(tree3) == 1)
Console.log(tree_depth(tree4) == 2)
```
```ReScript:Ex17_9.res
// 多相の木を表す型
type rec tree_t<'a> =
| Empty     // 空の木
| Leaf('a)  //葉
| Node(tree_t<'a>, 'a, tree_t<'a>)  // 節

// ２分探索木の例
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) 

// 目的：data が２分探索木 tree に含まれているかを調べる
// search : tree_t -> int -> bool
let rec search = (tree, data) => switch tree {
| Empty => false
| Leaf(n) => data == n
| Node(t1, n, t2) =>
    if data == n {true} 
    else if data < n {search(t1, data)}
    else {search(t2, data)}
}

// テスト
Console.log(search(tree1, 3) == false)
Console.log(search(tree2, 3) == true)
Console.log(search(tree2, 4) == false)
Console.log(search(tree5, 6) == true)
Console.log(search(tree5, 2) == true)
Console.log(search(tree5, 1) == true)
Console.log(search(tree5, 4) == false)
Console.log(search(tree5, 7) == true)
Console.log(search(tree5, 8) == false)

// 木の例
let tree1 = Empty
let tree2 = Leaf(3)
let tree3 = Node(tree1, 4, tree2)
let tree4 = Node(tree2, 5, tree3)

// 目的：tree に含まれる整数をすべて加える
// sum_tree : int tree_t -> int
let rec sum_tree = (tree) => switch tree {
| Empty => 0 
| Leaf(n) => n 
| Node(t1, n, t2) => sum_tree(t1) + n + sum_tree(t2)
}

// テスト
Console.log(sum_tree(tree1) == 0)
Console.log(sum_tree(tree2) == 3)
Console.log(sum_tree(tree3) == 7)
Console.log(sum_tree(tree4) == 15)
```
```ReScript:Ex17_10.res
// 最短路問題で使う木を表す型
type rec ekikan_tree_t = 
| Empty // 空の木
| Node(ekikan_tree_t, string, list<(string, float)>, ekikan_tree_t)
        // 節
```
```ReScript:Ex17_11.res
// 目的：受け取った ekimei0 までの距離を lst から探して返す
// assoc : string -> (string * float) list -> float
let rec assoc = (ekimei0, lst) => switch lst {
| list{} => Float.Constants.positiveInfinity
| list{(ekimei, kyori), ...rest} =>
    if ekimei == ekimei0 {kyori}
    else {assoc(ekimei0, rest)}
}

// テスト
Console.log(assoc("後楽園", list{}) == Float.Constants.positiveInfinity)
Console.log(assoc("後楽園", list{("新大塚", 1.2), ("後楽園", 1.8)}) == 1.8)
Console.log(assoc("池袋", list{("新大塚", 1.2)}) == Float.Constants.positiveInfinity)
```
```ReScript:Ex17_12.res
open Ex08_7  // ekikan_t
open Ex17_10 // ekikan_tree_t の定義

// 目的：受け取った kiten, shuten, kyori を ekikan_tree に挿入した木を返す
// insert1 : ekikan_tree_t -> string -> string -> float -> ekikan_tree_t
let rec insert1 = (ekikan_tree, kiten, shuten, kyori) => switch ekikan_tree {
| Empty => Node(Empty, kiten, list{(shuten, kyori)}, Empty)
| Node(left, ekimei, lst, right) => 
  if kiten < ekimei {Node(insert1(left, kiten, shuten, kyori), ekimei, lst, right)}
  else if ekimei < kiten {Node(left, ekimei, lst, insert1(right, kiten, shuten, kyori))}
  else {Node(left, ekimei, list{(shuten, kyori), ...lst}, right)}
}

// 目的：受け取った ekikan 情報を ekikan_tree に挿入した木を返す
// insert_ekikan : ekikan_tree_t -> ekikan_t -> ekikan_tree_t
let insert_ekikan = (ekikan_tree, ekikan) => switch ekikan {
| {kiten: k, shuten: s, keiyu: _, kyori: r, jikan: _} =>
  insert1(insert1(ekikan_tree, s, k, r), k, s, r)
}

// 駅間の例
let ekikan1 = 
  {kiten: "池袋", shuten: "新大塚", keiyu: "丸ノ内線", kyori: 1.8, jikan: 3}
let ekikan2 = 
  {kiten: "新大塚", shuten: "茗荷谷", keiyu: "丸ノ内線", kyori: 1.2, jikan: 2} 
let ekikan3 = 
  {kiten: "茗荷谷", shuten: "後楽園", keiyu: "丸ノ内線", kyori: 1.8, jikan: 2}
 
// テスト
let tree1 = insert_ekikan(Empty, ekikan1)
Console.log(tree1 ==
  Node(Empty, "新大塚", list{("池袋", 1.8)},
  Node(Empty, "池袋", list{("新大塚", 1.8)}, Empty)))
let tree2 = insert_ekikan(tree1, ekikan2)
Console.log(tree2 ==
  Node(Empty, "新大塚", list{("茗荷谷", 1.2), ("池袋", 1.8)}, 
  Node(Empty, "池袋", list{("新大塚", 1.8)},
  Node(Empty, "茗荷谷", list{("新大塚", 1.2)}, Empty))))
let tree3 = insert_ekikan(tree2, ekikan3)
Console.log(tree3 == 
  Node(Node(Empty, "後楽園", list{("茗荷谷", 1.8)}, Empty),
    "新大塚", list{("茗荷谷", 1.2), ("池袋", 1.8)}, 
    Node(Empty, 
	      "池袋", list{("新大塚", 1.8)},
	      Node(Empty, 
		    "茗荷谷", list{("後楽園", 1.8), ("新大塚", 1.2)}, 
		    Empty))))
```
```ReScript:Ex17_13.res
open Ex17_12 // insert_ekikan の定義
open Ex17_10

// 目的：受け取った ekikan のリストを ekikan_tree に挿入した木を返す
// inserts_ekikan : ekikan_tree_t -> ekikan_t list -> ekikan_tree_t
let inserts_ekikan = (ekikan_tree, ekikan_list) =>
  Js.List.foldRight((ekikan, tree) => insert_ekikan(tree, ekikan), 
	  ekikan_list, ekikan_tree)
 
// テスト
let ikebukuro = Node(Empty, "池袋", list{("新大塚", 1.8)}, Empty)
let shinootsuka = Node(Empty, "新大塚", list{("池袋", 1.8), ("茗荷谷", 1.2)}, ikebukuro)
let myougadani = Node(shinootsuka, "茗荷谷", list{("新大塚", 1.2), ("後楽園", 1.8)}, Empty)
let kourakuen = Node(Empty, "後楽園", list{("茗荷谷", 1.8)}, myougadani)
Console.log(inserts_ekikan(Empty, list{ekikan1, ekikan2, ekikan3}) == kourakuen)
```
```ReScript:Ex17_14.res
open Ex09_10  //ekikan_t, global_ekikan_list の定義
open Ex17_10  //ekikan_tree_t の定義
open Ex17_11  //assoc の定義
open Ex17_13  //inserts_ekikan の定義

// 目的：ふたつの駅の間の距離を求める
// get_ekikan_kyori : string -> string -> ekikan_tree_t -> float
let rec get_ekikan_kyori = (eki1, eki2, tree) => switch tree {
| Empty => Float.Constants.positiveInfinity
| Node(left, k, lst, right) => 
    if eki1 < k {get_ekikan_kyori(eki1, eki2, left)}
    else if k < eki1 {get_ekikan_kyori(eki1, eki2, right)}
    else {assoc(eki2, lst)}
}
 
// テスト
let global_ekikan_tree = inserts_ekikan(Empty, global_ekikan_list)
Console.log(get_ekikan_kyori("茗荷谷", "新大塚", global_ekikan_tree) == 1.2)
Console.log(get_ekikan_kyori("茗荷谷", "池袋", global_ekikan_tree) == Float.Constants.positiveInfinity)
Console.log(get_ekikan_kyori("東京", "大手町", global_ekikan_tree) == 0.6)
```
```ReScript:Ex17_15.res
open Ex08_5  // ekimei_t の定義
open Ex09_9  // global_ekimei_list の定義
open Ex09_10  // ekimei_t, ekikan_t, global_ekimei_list, global_ekikan_list の定義
open Ex10_10  // romaji_to_kanji
open Ex12_1   // eki_t の定義
open Ex15_5   //saitan_wo_bunri の定義
open Ex17_13  //inserts_ekikan の定義
open Ex17_14  //get_ekikan_kyori の定義

// Ex14_12.res を読み込むと ekimei_t 型、eki_t 型の定義が２度、読み込まれて
// しまうので make_initial_eki_list の定義を以下に直接、展開

// 目的：ekimei list から eki list を作る
// make_initial_eki_list : ekimei_t list -> string -> eki_t list
let make_initial_eki_list = (ekimei_list, kiten) => List.map(ekimei_list, ekimei => switch ekimei {
  | {kanji: k, kana: _, romaji: _, shozoku: _} => 
    if k == kiten {{namae: k, saitan_kyori: 0., temae_list: list{k}}}
    else {{namae: k, saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}}}
  }
)

// 目的：未確定の駅のリスト v を必要に応じて更新したリストを返す
// koushin : eki_t -> eki_t list -> ekikan_tree_t -> eki_t list
let koushin = (p, v, ekikan_tree) => switch p {
| {namae: pn, saitan_kyori: ps, temae_list: pt} =>
    List.map(v, (q) => switch q { 
	  | {namae: qn, saitan_kyori: qs, temae_list: _} => {
		  let kyori = get_ekikan_kyori(pn, qn, ekikan_tree)
  		if kyori == Float.Constants.positiveInfinity {q}
		  else if ps +. kyori < qs {{namae: qn, saitan_kyori: ps +. kyori, temae_list: list{qn, ...pt}}}
		  else {q}
    }
  })
}

// 目的：未確定駅のリストと駅間リストから、各駅への最短路を求める
// dijkstra_main : eki_t list -> ekikan_tree_t -> eki_t list
let rec dijkstra_main = (eki_list, ekikan_tree) => switch eki_list {
| list{} => list{}
| list{first, ...rest} => {
    let (saitan, nokori) = saitan_wo_bunri(list{first, ...rest})
    let eki_list2 = koushin(saitan, nokori, ekikan_tree)
    list{saitan, ...dijkstra_main(eki_list2, ekikan_tree)
  }
}
}

// 目的：受け取った eki_list から shuten のレコードを探し出す
// find : string -> eki_t list -> eki_t
let rec find = (shuten, eki_list) => switch eki_list {
| list{} => {namae: "", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}}
| list{{namae: n, saitan_kyori: s, temae_list: t}, ...rest} =>
    if n == shuten {{namae: n, saitan_kyori:s, temae_list: t}}
    else {find(shuten, rest)}
}
 
// 目的：始点と終点を受け取ったら、最短路を求め、終点のレコードを返す
// dijkstra : string -> string -> eki_t
let dijkstra = (romaji_kiten, romaji_shuten) => {
  let kiten = romaji_to_kanji(romaji_kiten, global_ekimei_list)
  let shuten = romaji_to_kanji(romaji_shuten, global_ekimei_list)
  let eki_list = make_initial_eki_list(global_ekimei_list, kiten)
  let global_ekikan_tree = inserts_ekikan(Empty, global_ekikan_list)
  let eki_list2 = dijkstra_main(eki_list, global_ekikan_tree)
  find(shuten, eki_list2)
}

// テスト
Console.log(dijkstra("shibuya", "gokokuji") ==
  {namae: "護国寺", saitan_kyori: 9.8,
   temae_list:
     list{"護国寺", "江戸川橋", "飯田橋", "市ヶ谷", "麹町", "永田町", 
      "青山一丁目", "表参道", "渋谷"}})
Console.log(dijkstra("myogadani", "meguro") ==
  {namae: "目黒", saitan_kyori: 12.7000000000000028, 
   temae_list:
     list{"目黒", "白金台", "白金高輪", "麻布十番", "六本木一丁目", "溜池山王",
      "永田町", "麹町", "市ヶ谷", "飯田橋", "後楽園", "茗荷谷"}})
```
```ReScript:Ex17_16.res
open Ex12_1

// 目的：受け取った駅のリストを、最短距離最小の駅とそれ以外に分離する
// saitan_wo_bunri : eki_t -> eki_t list -> eki_t * eki_t list
let saitan_wo_bunri = (eki, eki_list) =>
  Js.List.foldRight((first, (p, v)) =>
		switch(first, p) {
		| ({namae: _, saitan_kyori: fs, temae_list: _},
			 {namae: _, saitan_kyori: ss, temae_list: _}) =>
			 if fs < ss {(first, list{p, ...v})}
			 else {(p, list{first,  ...v})}
    },
		eki_list, 
		(eki, list{})
  )

// 駅の例
let eki1 = {namae: "池袋", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}}
let eki2 = {namae: "新大塚", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{"新大塚", "茗荷谷"}}
let eki3 = {namae: "茗荷谷", saitan_kyori: 0., temae_list: list{"茗荷谷"}}
let eki4 = {namae: "後楽園", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}}

// 駅リストの例
let lst = list{eki2, eki3, eki4}
 
// テスト
Console.log(saitan_wo_bunri(eki1, lst) == (eki3, list{eki2, eki1, eki4}))
```
```ReScript:Ex17_17.res
// 目的：受け取った lst の中の最小値を返す
// minimum : int -> int list -> int 
let rec minimum = (n, lst) => switch lst {
| list{} => n
| list{first, ...rest} =>
    if first <= n {minimum(first, rest)}
    else {minimum(n, rest)}
}

// テスト
Console.log(minimum(3, list{}) == 3)
Console.log(minimum(1, list{2}) == 1)
Console.log(minimum(3, list{2}) == 2)
Console.log(minimum(3, list{2, 6, 4, 1, 8}) == 1)
```