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

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

環境

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

第19章

Tree.resi

// ２分木を表すモジュールのシグネチャ
type t<'a, 'b> 
// キーが 'a 型、値が 'b 型の木の型。型の中身は非公開
 
let empty : t<'a, 'b>
// 使い方：empty
// 空の木
 
let insert: (t<'a, 'b>, 'a, 'b) => t<'a, 'b> 
// 使い方：insert tree key value
// 木 tree にキー key と値 value を挿入した木を返す
// キーが既に存在していたら新しい値に置き換える
 
let search: (t<'a, 'b>, 'a) => 'b 
// 使い方：search tree key
// 木 tree の中からキー key に対応する値を探して返す
// みつからなければ Not_found を raise する

Tree.res

// ２分木を表すモジュール
// ２分木を表す型
type rec t<'a, 'b> =
  | Empty 
  | Node(t<'a, 'b>, 'a, 'b, t<'a, 'b>)

// 空の木
let empty = Empty

// 目的：tree にキーが k で値が v を挿入した木を返す
// insert : ('a, 'b) t -> 'a -> 'b -> ('a, 'b) t
let rec insert = (tree, k, v) => switch tree {
| Empty => Node(Empty, k, v, Empty)
| Node(left, key, value, right) =>
    if k == key {Node(left, key, v, right)}
    else if k < key {Node(insert(left, k, v), key, value, right)}
    else {Node(left, key, value, insert(right, k, v))}
}

// 目的：tree の中のキー k に対応する値を探して返す
// みつからなければ例外 Not_found を起こす
// search : ('a, 'b) t -> 'a -> 'b
let rec search = (tree, k) => switch tree {
| Empty => raise(Not_found)
| Node(left, key, value, right) =>
    if k == key {value}
    else if k < key {search(left, k)}
    else {search(right, k)}
}

Ex19_01.res

open Ex08_7  //ekikan_t の定義
open Ex09_10  //ekikan_t, global_ekikan_list の定義
open Ex17_11  //assoc の定義

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

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

// 目的：受け取った ekikan のリストを ekikan_tree に挿入した木を返す
// inserts_ekikan : (string * (string * float) list) Tree.t ->
// 		     ekikan_t list ->
// 		    (string * (string * float) list) Tree.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) Tree.t -> float
let get_ekikan_kyori = (eki1, eki2, tree) =>
  assoc(eki2, (Tree.search(tree, eki1)))

// テスト
let global_ekikan_tree = inserts_ekikan(Tree.empty, global_ekikan_list)
Console.log(get_ekikan_kyori("茗荷谷", "新大塚", global_ekikan_tree) == 1.2)
// Console.log(get_ekikan_kyori("茗荷谷", "池袋", global_ekikan_tree))
  //Not_found を起こす
Console.log(get_ekikan_kyori("東京", "大手町", global_ekikan_tree) == 0.6)