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

[《プログラミングの基礎》](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
# 第16章
最初の完動プログラムができあがります。
```ReScript:Ex16_1.res
// 目的：先頭からリスト中の各整数までの合計を計算する
// sum_list : int list -> int list
let sum_list = (lst) => {
  // 目的：先頭からリスト中の各整数までの合計を計算する
  // ここで total0 はこれまでの整数の合計
  // hojo : int list -> int -> int list
  let rec hojo = (lst, total0) => switch lst {
  | list{} => list{}
  | list{first, ...rest} => list{first + total0, ...hojo(rest, first + total0)}
  }
  hojo(lst, 0)
}
 
// テスト
Console.log(sum_list(list{}) == list{})
Console.log(sum_list(list{1, 2, 3}) == list{1, 3, 6})
Console.log(sum_list(list{3, 2, 1, 4}) == list{3, 5, 6, 10})
```
```ReScript:Ex16_2.res
// 目的：init から始めて lst の要素を左から順に f を施し込む
// fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
let rec fold_left = (f, init, lst) => switch lst { 
| list{} => init
| list{first, ...rest} => fold_left(f, f(init, first), rest)
}
 
// テスト
Console.log(fold_left((a, b) => a - b, 0,  list{}) == 0)
Console.log(fold_left((a, b) => a - b, 10, list{4, 1, 3}) == 2)
Console.log(fold_left((lst, a) => list{a, ...lst}, list{}, list{1, 2, 3, 4}) == list{4, 3, 2, 1})
```
```ReScript:Ex16_3.res
open Ex09_10	// global_ekikan_list の定義
open Ex10_11	// get_ekikan_kyori
open Ex12_1		//eki_t の定義

// 目的：未確定の駅のリスト v を必要に応じて更新したリストを返す
// koushin : eki_t -> eki_t list -> ekikan_t list -> eki_t list
let koushin = (p, v, ekikan_list) => 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_list) 
		 	if kyori == Float.Constants.positiveInfinity {q}
			else if ps +. kyori < qs {{namae: qn, saitan_kyori: ps +. kyori, temae_list: list{qn, ...pt}}}
			else {q}
		}
	}) 
}

// 駅の例
let eki1 = {namae: "池袋", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}}
let eki2 = {namae: "新大塚", saitan_kyori: 1.2, 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{eki1, eki2, eki3, eki4}

// テスト
Console.log(koushin(eki2, list{}, global_ekikan_list) == list{})
Console.log(koushin(eki2, lst, global_ekikan_list) == 
 list{{namae: "池袋", saitan_kyori: 3.0, temae_list: list{"池袋", "新大塚", "茗荷谷"}}, 
  eki2, eki3, eki4})
```
```ReScript:Ex16_4.res
open Ex09_10 // global_ekikan_list の定義
open Ex10_11  // get_ekikan_kyori
open Ex12_1   // eki_t の定義
open Ex15_5   // saitan_wo_bunri の定義

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

// 目的：未確定の駅のリスト v を必要に応じて更新したリストを返す
// koushin : eki_t -> eki_t list -> ekikan_t list -> eki_t list
let koushin = (p, v, ekikan_list) => 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_list) 
		 	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_t list -> eki_t list
let rec dijkstra_main = (eki_list, ekikan_list) => switch eki_list {
| list{} => list{}
| _ => {
    let (saitan, nokori) = saitan_wo_bunri(eki_list)
    let eki_list2 = koushin(saitan, nokori, ekikan_list)
    list{saitan, ...dijkstra_main(eki_list2, ekikan_list)}
  }
}

// 駅の例
let eki1 = {namae: "池袋", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}}
let eki2 = {namae: "新大塚", saitan_kyori: 1.2, 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{eki1, eki2, eki3, eki4}
 
// テスト
Console.log(dijkstra_main(list{}, global_ekikan_list) == list{})
Console.log(dijkstra_main(lst, global_ekikan_list) == 
  list{{namae: "茗荷谷", saitan_kyori: 0., temae_list: list{"茗荷谷"}},
  {namae: "新大塚", saitan_kyori: 1.2, temae_list: list{"新大塚", "茗荷谷"}},
  {namae: "後楽園", saitan_kyori: 1.8, temae_list: list{"後楽園", "茗荷谷"}},
  {namae: "池袋", saitan_kyori: 3., temae_list: list{"池袋", "新大塚", "茗荷谷"}}})
```
```ReScript:Ex16_5.res
open Ex08_5   // ekimei_t の定義
open Ex09_9   // global_ekimei_list
open Ex09_10  // global_ekikan_list
open Ex10_10  // romaji_to_kanji
open Ex12_1   // eki_t の定義
open Ex16_4   // dijkstra_main の定義
 
// 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{}}}
  }
)
 
// 目的：受け取った 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 eki_list2 = dijkstra_main(eki_list, global_ekikan_list)
  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{"目黒", "白金台", "白金高輪", "麻布十番", "六本木一丁目", "溜池山王", 
      "永田町", "麹町", "市ヶ谷", "飯田橋", "後楽園", "茗荷谷"}})
```