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

[《プログラミングの基礎》](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
# 第11章
```ReScript:Ex11_1.res
// 目的：自然数 n の階乗を求める
// sum_of_square : int -> int
let rec sum_of_square = (n) =>
  if n == 0 {0}
  else {n * n + sum_of_square(n - 1)}
 
// テスト
Console.log(sum_of_square(0) == 0)
Console.log(sum_of_square(1) == 1)
Console.log(sum_of_square(2) == 5)
Console.log(sum_of_square(3) == 14)
Console.log(sum_of_square(4) == 30)
```
```ReScript:Ex11_2.res
// 目的：問題に与えられた漸化式の一般項を求める
// a : int -> int
let rec a = (n) =>
  if n == 0 {3} 
  else {2 * a(n - 1) - 1}
 
// テスト
Console.log(a(0) == 3)
Console.log(a(1) == 5)
Console.log(a(2) == 9)
Console.log(a(3) == 17)
Console.log(a(4) == 33)
```
# 第12章
ダイクストラ法が説明されます。
ダイクストラ法の頂点を表す`eki_t型`を問題12.1で定義します。
```ReScript:Ex12_1.res
// グラフの中の節（駅）を表す型
type eki_t = {
  namae        : string,      // 駅名（漢字）
  saitan_kyori : float,       // 最短距離
  temae_list   : list<string> // 手前の駅名（漢字）のリスト
}
```
```ReScript:Ex12_2.res
open Ex08_5
open Ex12_1

// 駅名リストの例
let ekimei_list = list{ 
  {kanji: "池袋", kana: "いけぶくろ", romaji: "ikebukuro", shozoku: "丸ノ内線"},
  {kanji: "新大塚", kana: "しんおおつか", romaji: "shinotsuka", shozoku: "丸ノ内線"}, 
  {kanji: "茗荷谷", kana: "みょうがだに", romaji: "myogadani", shozoku: "丸ノ内線"}, 
  {kanji: "後楽園", kana: "こうらくえん", romaji: "korakuen", shozoku: "丸ノ内線"},
  {kanji: "本郷三丁目", kana: "ほんごうさんちょうめ", romaji: "hongosanchome", shozoku: "丸ノ内線"},
  {kanji: "御茶ノ水", kana: "おちゃのみず", romaji: "ochanomizu", shozoku: "丸ノ内線"}
}

// 目的：ekimei list から eki list を作る
// make_eki_list : ekimei_t list -> eki_t list
let rec make_eki_list = (ekimei_list) => 
  switch ekimei_list {
  | list{} => list{}
  | list{{kanji: k, kana: _, romaji: _, shozoku: _}, ...rest} =>
      list{{namae: k, saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}}, ...make_eki_list(rest)}
  }

// テスト
Console.log(make_eki_list(list{}) == list{})
Console.log(make_eki_list(ekimei_list) == list{ 
{namae: "池袋", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "新大塚", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "茗荷谷", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "後楽園", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "本郷三丁目", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "御茶ノ水", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}}
})
```
```ReScript:Ex12_3.res
open Ex12_1

// 駅リストの例
let eki_list = list{
{namae: "池袋", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "新大塚", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "茗荷谷", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "後楽園", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "本郷三丁目", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "御茶ノ水", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}}
}

// 目的：eki_t型のリストを初期化する
// shokika : eki_t list -> string -> eki_t list
let rec shokika = (eki_list, kiten) =>
  switch eki_list {
  | list{} => list{}
  | list{{namae: k, saitan_kyori: s, temae_list: t}, ...rest} =>
      if k == kiten {list{{namae: k, saitan_kyori: 0., temae_list: list{k}}, ...shokika(rest, kiten)}}
      else {list{{namae: k, saitan_kyori: s, temae_list:t}, ...shokika(rest, kiten)}}
  }

// テスト
Console.log(shokika(list{}, "茗荷谷") == list{})
Console.log(shokika(eki_list, "茗荷谷") == list{ 
{namae: "池袋", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "新大塚", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "茗荷谷", saitan_kyori: 0., temae_list: list{"茗荷谷"}},
{namae: "後楽園", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "本郷三丁目", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}},
{namae: "御茶ノ水", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}}
})
```
```ReScript:Ex12_4.res
open Ex08_5

// 駅名リストの例
let ekimei_list = list{ 
{kanji: "池袋", kana: "いけぶくろ", romaji: "ikebukuro", shozoku: "丸ノ内線"},
{kanji: "新大塚", kana: "しんおおつか", romaji: "shinotsuka", shozoku: "丸ノ内線"},
{kanji: "茗荷谷", kana: "みょうがだに", romaji: "myogadani", shozoku: "丸ノ内線"},
{kanji: "後楽園", kana: "こうらくえん", romaji: "korakuen", shozoku: "丸ノ内線"},
{kanji: "本郷三丁目", kana: "ほんごうさんちょうめ", romaji: "hongosanchome", shozoku: "丸ノ内線"},
{kanji: "御茶ノ水", kana: "おちゃのみず", romaji: "ochanomizu", shozoku: "丸ノ内線"}
}
 
// 目的：昇順に並んでいる lst の正しい位置に ekimei を挿入する
//     ekimeiのkanaが重複した場合は、lstから削除する
// ekimei_insert : ekimei_t list -> ekimei_t -> ekimei_t list
let rec ekimei_insert = (lst, ekimei0) =>
  switch lst {
  | list{} => list{ekimei0}
  | list{{kanji: k, kana: a, romaji: r, shozoku: s}, ...rest} =>
    switch ekimei0 {
    | {kanji: _, kana: a0, romaji: _, shozoku: _} =>
        if a == a0 {ekimei_insert(rest, ekimei0)}
	      else if a < a0 {list{{kanji: k, kana: a, romaji: r, shozoku: s}, ...ekimei_insert(rest, ekimei0)}}
	      else {list{ekimei0, ...lst}}
    }
  }

// テスト
Console.log(ekimei_insert(list{}, {kanji: "茗荷谷", kana: "みょうがだに", romaji: "myogadani", shozoku: "丸ノ内線"})
	    == list{{kanji: "茗荷谷", kana: "みょうがだに", romaji: "myogadani", shozoku: "丸ノ内線"}})
Console.log(ekimei_insert(list{
	{kanji: "池袋", kana: "いけぶくろ", romaji: "ikebukuro", shozoku: "丸ノ内線"},
	{kanji: "御茶ノ水", kana: "おちゃのみず", romaji: "ochanomizu", shozoku: "丸ノ内線"},
	{kanji: "新大塚", kana: "しんおおつか", romaji: "shinotsuka", shozoku: "丸ノ内線"},
	{kanji: "本郷三丁目", kana: "ほんごうさんちょうめ", romaji: "hongosanchome", shozoku: "丸ノ内線"},
	{kanji: "茗荷谷", kana: "みょうがだに", romaji: "myogadani", shozoku: "丸ノ内線"}
}, 
	{kanji: "後楽園", kana: "こうらくえん", romaji: "korakuen", shozoku: "丸ノ内線"})
== list{
	{kanji: "池袋", kana: "いけぶくろ", romaji: "ikebukuro", shozoku: "丸ノ内線"},
	{kanji: "御茶ノ水", kana: "おちゃのみず", romaji: "ochanomizu", shozoku: "丸ノ内線"},
	{kanji: "後楽園", kana: "こうらくえん", romaji: "korakuen", shozoku: "丸ノ内線"},
	{kanji: "新大塚", kana: "しんおおつか", romaji: "shinotsuka", shozoku: "丸ノ内線"},
	{kanji: "本郷三丁目", kana: "ほんごうさんちょうめ", romaji: "hongosanchome", shozoku: "丸ノ内線"},
	{kanji: "茗荷谷", kana: "みょうがだに", romaji: "myogadani", shozoku: "丸ノ内線"}
})
Console.log(ekimei_insert(list{
{kanji: "池袋", kana: "いけぶくろ", romaji: "ikebukuro", shozoku: "丸ノ内線"},
{kanji: "池袋", kana: "いけぶくろ", romaji: "ikebukuro", shozoku: "有楽町線"}
},
{kanji: "池袋", kana: "いけぶくろ", romaji: "ikebukuro", shozoku: "副都心線"}) ==
list{{kanji: "池袋", kana: "いけぶくろ", romaji: "ikebukuro", shozoku: "副都心線"}})

// 目的：ekimei list をひらがなの順に整列しながら駅の重複を取り除く
// seiretsu : ekimei_t list -> ekimei_t list
let rec seiretsu = (ekimei_list) =>
  switch ekimei_list { 
  | list{} => list{}
  | list{first, ...rest} => ekimei_insert(seiretsu(rest), first)
  }

// テスト
Console.log(seiretsu(list{}) == list{})
Console.log(seiretsu(ekimei_list) == list{
{kanji: "池袋", kana: "いけぶくろ", romaji: "ikebukuro", shozoku: "丸ノ内線"},
{kanji: "御茶ノ水", kana: "おちゃのみず", romaji: "ochanomizu", shozoku: "丸ノ内線"},
{kanji: "後楽園", kana: "こうらくえん", romaji: "korakuen", shozoku: "丸ノ内線"},
{kanji: "新大塚", kana: "しんおおつか", romaji: "shinotsuka", shozoku: "丸ノ内線"},
{kanji: "本郷三丁目", kana: "ほんごうさんちょうめ", romaji: "hongosanchome", shozoku: "丸ノ内線"},
{kanji: "茗荷谷", kana: "みょうがだに", romaji: "myogadani", shozoku: "丸ノ内線"}
})
```