メトロネットワーク最短路問題その２

d2.ml

(* --- 問題12.1 --- *)
(* 駅名・最短距離・最短距離を表すデータ型 *)
type eki_t = {
	namae : string; (* 漢字の駅名 *)
	saitan_kyori : float; (* 現在の最短距離 *)
	temae_list : string list; (* 漢字の駅名のリスト（最短経路） *)
}

# #use "eki_t.ml" ;;
type eki_t = {
  namae : string;
  saitan_kyori : float;
  temae_list : string list;
}

(* --- 問題12.2 --- *)
(* 目的 : ekimei_t型のリストから，eki_t型のリストを返す *)
(* make_eki_list : ekimei_t list -> eki_t list *)
let rec make_eki_list emlst  = match emlst with
	[] -> []
    | { kanji = kj; kana = kn; romaji = rm; shozoku = sz } :: rest -> 
    	{ namae = kj; saitan_kyori = infinity; temae_list = [] } :: ( make_eki_list rest )

# #use "metro.ml" ;;
# #use "eki_t.ml" ;;
# #use "make_eki_list.ml" ;;
val make_eki_list : ekimei_t list -> eki_t list = <fun>
# make_eki_list global_ekimei_list ;;
- : eki_t list =
[{namae = "代々木上原"; saitan_kyori = infinity; temae_list = []};
 {namae = "代々木公園"; saitan_kyori = infinity; temae_list = []};
 {namae = "明治神宮前"; saitan_kyori = infinity; temae_list = []};
 {namae = "表参道"; saitan_kyori = infinity; temae_list = []};
 {namae = "乃木坂"; saitan_kyori = infinity; temae_list = []};
...]

(* --- 問題12.3 --- *)
(* 目的 : eki_t型リストと起点（漢字の文字列）を受け取ったら，そのeki_t型の要素のみを初期化する *)
(* shokika : eki_t list -> string -> eki_t list *)
let rec shokika elst ktn  = match elst with
	[] -> []
    | ( { namae = n; saitan_kyori = sk; temae_list = tl } as first ):: rest -> 
    	if ( n = ktn )
        then { namae = ktn; saitan_kyori = 0.; temae_list = [ktn] } :: rest
        else first :: ( shokika rest ktn )

#use "metro.ml" ;;
#use "eki_t.ml" ;;
#use "make_eki_list.ml" ;;
#use "syokika.ml" ;;

amae = "池袋"; saitan_kyori = infinity; temae_list = ...}; ...]
# shokika (make_eki_list global_ekimei_list) "代々木上原" ;;
- : eki_t list =
[{namae = "代々木上原"; saitan_kyori = 0.; temae_list = ["代々木上原"]};
 {namae = "代々木公園"; saitan_kyori = infinity; temae_list = []};
 {namae = "明治神宮前"; saitan_kyori = infinity; temae_list = []};
 {namae = "表参道"; saitan_kyori = infinity; temae_list = []};
 {namae = "乃木坂"; saitan_kyori = infinity; temae_list = []};
(* 略 *)

# shokika (make_eki_list global_ekimei_list) "霞ヶ関" ;;
- : eki_t list =
[{namae = "代々木上原"; saitan_kyori = infinity; temae_list = []};
 {namae = "代々木公園"; saitan_kyori = infinity; temae_list = []};
 {namae = "明治神宮前"; saitan_kyori = infinity; temae_list = []};
 {namae = "表参道"; saitan_kyori = infinity; temae_list = []};
 {namae = "乃木坂"; saitan_kyori = infinity; temae_list = []};
 {namae = "赤坂"; saitan_kyori = infinity; temae_list = []};
 {namae = "国会議事堂前"; saitan_kyori = infinity; temae_list = []};
 {namae = "霞ヶ関"; saitan_kyori = 0.; temae_list = ["霞ヶ関"]};
 {namae = "日比谷"; saitan_kyori = infinity; temae_list = []};
 {namae = "二重橋前"; saitan_kyori = infinity; temae_list = []};
(* 略 *)

(* 問題12.5 *)
#use "metro.ml"

(* 目的 : あらかじめ昇順に並んでいるekimei_t型のリストlstとekimei_t型データnを受け取ったら，*)
(* 整数nをlstの昇順となる位置に挿入したリストを返す *)
(* insert : ekimei_t list -> ekimei_t -> ekimei_t list *)
let rec insert lst n  = match lst with 
	[] -> [n]
    | ( { kanji = kj_f; kana = kn_f; romaji = rm_f; shozoku = sz_f } as first ) :: rest -> 
        match n with 
            { kanji = kj; kana = kn; romaji = rm; shozoku = sz } -> 
                if ( kj_f = kj ) 
                then (insert rest n)
                else if ( kn_f > kn )
                     then n :: lst
                     else first :: (insert rest n)

(* 目的 : ekimei_t型のリストを受け取ったら，それを昇順に整列したリストを返す *)
(* seiretsu : ekimei_t lst -> ekimei_t lst *)
let rec seiretsu lst  = match lst with
	[] -> []
    | first :: rest -> ( insert (seiretsu rest) first )

let ekimei_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="丸ノ内線"} 
] 

(* テスト *) 
let test3 = seiretsu [] = [] 
let test4 = seiretsu ekimei_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="丸ノ内線"} 
]

val test3 : bool = true
val test4 : bool = true