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

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

環境

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

第21章

Ex21_1.res

open Ex08_5   // ekikan_t の定義
open Ex08_7   // ekikan_t の定義
open Ex09_9   // global_ekimei_list の定義
open Ex09_10  // global_ekikan_list の定義
open Ex12_1   // eki_t の定義
open Ex17_11  //　assoc の定義
open Ex17_16  // saitan_wo_bunri の定義
open Ex18_7   //　romaji_to_kanji の定義

open RedBlack 
// open Tree
// Tree モジュールを使う場合はこちらを使用する

// 目的：受け取った kiten, shuten, kyori を ekikan_tree に挿入した木を返す
// insert1 : (string * (string * float) list) t ->
//	      string -> string -> float -> 
//	     (string * (string * float) list) t
let insert1 = (ekikan_tree, kiten, shuten, kyori) => {
  let lst = try {
	  search(ekikan_tree, kiten)
  } catch {
	| Not_found => list{}
  }
  insert(ekikan_tree, kiten, list{(shuten, kyori), ...lst}) 
}

// 目的：受け取った ekikan 情報を ekikan_tree に挿入した木を返す
// insert_ekikan : (string * (string * float) list) t
//		    ekikan_t ->
//		   (string * (string * float) list) 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)
}

// 目的：受け取った ekikan のリストを ekikan_tree に挿入した木を返す
// inserts_ekikan : (string * (string * float) list) t -> 
//		     ekikan_t list -> 
//		    (string * (string * float) list) t *) 
let inserts_ekikan = (ekikan_tree, ekikan_list) =>
  Js.List.foldLeft(insert_ekikan, ekikan_tree, ekikan_list)

// 目的：ふたつの駅の間の距離を求める
// 見つからなかったら例外 Not_found を起こす
// get_ekikan_kyori : string -> string -> 
//		     (string * (string * float) list) t -> float *) 
let get_ekikan_kyori = (eki1, eki2, tree) =>
  assoc(eki2, (search(tree, eki1)))

// 目的：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: _} =>
		  try { 
		    let kyori = get_ekikan_kyori(pn, qn, ekikan_tree)
		    if ps +. kyori < qs 
		      {{namae: qn, saitan_kyori: ps +. kyori, temae_list: list{qn, ...pt}}}
		      else {q}
      } catch {
      | Not_found => 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(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)
}

// 目的：eki_t 型のレコードをきれいに表示する
// print_eki : eki_t -> unit
let print_eki = (eki) => switch eki {
| {namae: _, saitan_kyori: s, temae_list: lst} => switch lst {
  | list{} => assert false // この場合は起こりえない
  | list{a}=> Console.log(a ++ "（" ++ Float.toString(s) ++ "km）");
  | list{a, ...rest} => {Js.List.foldRight(
      (b, ()) => Console.log(b ++ "、"),
			rest,
      ())
	    Console.log(a ++ "（" ++ Float.toString(s) ++ "km）")}
  }
}

// メイン関数
// main : string -> string -> unit
let main = (romaji_kiten, romaji_shuten) => {
  let eki = dijkstra(romaji_kiten, romaji_shuten) 
  print_eki(eki)
}

// テスト
main("shibuya", "gokokuji")
// 渋谷、表参道、青山一丁目、永田町、麹町、市ヶ谷、飯田橋、江戸川橋、 
//    護国寺（9.8km）と表示される
main("myogadani", "meguro")
// 茗荷谷、後楽園、飯田橋、市ヶ谷、麹町、永田町、溜池山王、六本木一丁目、 
// 麻布十番、白金高輪、白金台、目黒（12.7km）と表示される

Ex21_2.res

// 目的：2 から n までの自然数を受け取り 2 から n までの素数を返す
// sieve : int list -> int list
let rec sieve = (lst) => {
  Console.log(List.length(lst))
  switch lst {
  | list{} => list{}
  | list{first, ...rest} =>
	    list{first, ...sieve(List.filter(rest, (x) => mod(x, first) != 0))}
  }
}

// テスト
Console.log(sieve(list{2, 3, 4, 5, 6, 7, 8, 9, 10}) == list{2, 3, 5, 7})
// 9, 4, 2, 1, 0 が順に表示される

// 目的：2 から受け取った自然数 n までの自然数のリストを返す
// two_to_n : int -> int list
let rec two_to_n = (n) => switch n {
| 2 => list{2}
| _ => List.concat(two_to_n(n-1), list{n}) 
}
 
// テスト
Console.log(two_to_n(10) == list{2, 3, 4, 5, 6, 7, 8, 9, 10})

// 目的：2 から受け取った自然数 n までの素数を返す
// prime : int -> int list
let prime = (n) => sieve(two_to_n(n))
 
// テスト
Console.log(prime(10) == list{2, 3, 5, 7})
// 9, 4, 2, 1, 0 が順に表示される

第22章

Ex22_1.res

// 文字列につける数字
let counter = ref(-1)

// 目的：文字列に毎回、異なる数字をつけて返す
// gensym : string -> string
let gensym = (str) => {
  counter.contents = counter.contents + 1
  str ++ Int.toString(counter.contents)
}

// テスト
Console.log(gensym("a") == "a0")
Console.log(gensym("a") == "a1")
Console.log(gensym("x") == "x2")

Ex22_2.res

// 目的：受け取った配列にフィボナッチ数を順に入れて返す
// fib_array : int array -> int array
let fib_array = (array) => {
  let n = Array.length(array)
  if n > 0 {Array.set(array, 0, 0)}
  if n > 1 {Array.set(array, 1, 1)}
  for i in 2 to n - 1 {
    Array.set(array, i, Array.getUnsafe(array, i - 1) + Array.getUnsafe(array,i - 2))
  }
  array 
}

// テスト
Console.log(fib_array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
  == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34])