12.ml

#use "metro.ml"

(* 問題12.1 eki_t 型 *)
type eki_t = {
    namae: string;           (* 駅名 *)
    saitan_kyori: float;     (* 最短距離 *)
    temae_list: string list; (* 通過した駅名のリスト *)
  }

(* 問題12.2 ekimei_t list を受け取って、駅名から eki_t list を作る 
   namae: 駅名
   saitan_kyori: infinity
   temae_list: []
   として値をいれる 
*)

(* make_eki_list : ekimei_t list -> eki_t list *)
let rec make_eki_list_sub lst ret = 
  match lst with
    [] -> ret
  | first :: rest -> make_eki_list_sub rest ({namae=first.kanji; saitan_kyori=infinity; temae_list=[]} :: ret)
				       
let make_eki_list lst = make_eki_list_sub lst []


(* 問題12.3 eki_t list と起点の駅名を受け取って、起点のみ最短距離を初期化する *)
(* shokika: eki_t list -> string -> eki_t list *)
let rec shokika_sub lst start_name ret =
  match lst with
    [] -> ret
  | first :: rest -> shokika_sub rest start_name
				 ((if first.namae = start_name 
				   then {namae = first.namae; saitan_kyori = 0.; temae_list = [first.namae]}
				   else first):: ret)
let shokika lst start_name = shokika_sub lst start_name []



(* 同名の駅がなければ挿入する。あれば元のリストのまま返す *)
(* seiretsu_ins : ekime_t list -> ekimei_t -> ekimei_t list *)
let rec seiretsu_ins lst v = match lst with
    [] -> [v]
  | first :: rest -> if first.kana = v.kana
		     then lst
		     else (if first.kana < v.kana
			   then first :: (seiretsu_ins rest v)
			   else v :: lst)


(* 問題12.4 ekimei_t list からひらがな順に整列し、重複を取り除いた ekimei_t list を返す*)
(* seiretsu : ekimei_t list -> ekimei_t list *)
let rec seiretsu lst = match lst with
    [] -> []
  | first :: rest -> seiretsu_ins (seiretsu rest) first