LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@sgigagaeru

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

Posted at

《プログラミングの基礎》はとても良い本です。
サンプルプログラムをReScriptで書いて、プログラミングの基礎とReScriptを学びます。

環境

  • macOS Sonoma(バージョン 14.4.1)
  • ReScript 11.1.0-rc.8
  • @rescript/core 1.2.0

第11章

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)
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で定義します。

Ex12_1.res
// グラフの中の節（駅）を表す型
type eki_t = {
  namae        : string,      // 駅名（漢字）
  saitan_kyori : float,       // 最短距離
  temae_list   : list<string> // 手前の駅名（漢字）のリスト
}
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{}}
})
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{}}
})
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: "丸ノ内線"}
})
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?