プログラミングの基礎 第12章

本当はglobal_ekimei_listを使うらしいので、その部分の書き換え
getDistanceAndStationに関しては、今までの動きをしてもらわないと困るので、変更せず
引数のリストを変えたけど、これの方がわかりにくい…

(* 各駅から最短距離のリストを作る関数 *)
(* make_eki_list -> ekimei_t list -> eki_t list*)
let rec make_saitan_eki_list xs = match xs with
[] -> []
| { kanji   = knj;
    kana    = kn;
    romaji  = rmj;
    shozoku = shzk }::rest 
   -> let stations = getDistanceAndStation global_ekikan_list knj in
      let min = getMinimumOf stations in match stations with
      [] -> []
      | (start, goal, distance)::station_rest 
         -> { namae = start; 
              saitan_kyori = distance;
              temae_list = filter_stations min stations} ::make_saitan_eki_list rest

let test_saitan_eki_list = make_saitan_eki_list global_ekimei_list

そして残りの問題。関数が他言語の悟りを得たい…汚いorz

(* global_eki_listからeki_tのリストを生成する *)
(* eki_t = { name = 駅名; saitan_kyori = 無限大; temae_list = 空のリスト *)

let rec make_eki_list xs = match xs with
[] -> []
| {kanji   = knj;
   kana    = kn;
   romaji  = rmj;
   shozoku = shzk }::rest
   -> { namae = knj; 
        saitan_kyori = infinity; 
        temae_list = [] }::make_eki_list rest  

let eki_list = make_eki_list global_ekimei_list

(* ダイクストラのアルゴリズムの一ステップ目を行う *)
(* shokika : string -> eki_t list -> eki_t list *)
let rec shokika station xs = match xs with 
[] -> []
| ({ namae = name;
     saitan_kyori = distance;
     temae_list = eki_list; } as first)::rest
    -> if name = station then { namae = name;
                                saitan_kyori = 0.0; 
                                temae_list = [name] }::rest
                         else first::shokika station rest

(* testing これはfragileなテストなので良くない*)
let test_shokika = match (shokika "代々木上原" eki_list) with
[] -> false
| { namae = name; 
    saitan_kyori = distance;
    temae_list   = eki_list }::rest 
   -> distance = 0. && eki_list = [name]

(* 昇順に並んでるekimei_tのリストに対して、
 * 適切な場所に、ekiを挿入する*)
(* insert_eki : ekimei_t list -> ekimei_t list *)
let rec insert_eki eki xs = match (eki, xs) with
(eki ,[]) -> eki::[]
| ({ kanji   = e_knj;
     kana    = e_kn;
     romaji  = e_rmj;
     shozoku = e_shzk; }, 
   ( { kanji   = knj;
       kana    = kn;
       romaji  = rmj;
       shozoku = shzk; } as first)::rest)
  ->  if e_kn < kn then eki::first::rest
                   else first::insert_eki eki rest

(* ekimei_tを挿入ソートする関数 *)
(* insort_ekimei : ekimei list -> ekimei list *)
let rec insort_ekimei xs = match xs with
[] -> []
| first::rest -> insert_eki first (insort_ekimei rest)

(* ekimei_tのリストを受け取って、名前の重複を取り除く*)
(* unit_ekimei : ekimei_t list -> ekimei_t list*)
let rec unit_ekimei xs = match xs with
[] -> [] 
| ( { kanji   = knj;
      kana    = kn;
      romaji  = rmj;
      shozoku = shzk;} as first )::rest 
    -> let rec filter name xs = match xs with 
    [] -> []
    | ({ kanji   = knj; 
         kana    = kn; 
         romaji  = rmj; 
         shozoku = shzk; } as first)::rest
        -> if name = knj then filter name rest
                           else first::filter name rest 
        in first:: unit_ekimei (filter knj rest)

(* ekimei_tのリストを受け取って、
 * 重複を取り除いて、ひらがなの順に整列をする*)
(* seiretsu : ekimei_t list -> ekimei_t list *)
let rec seiretsu xs = unit_ekimei (insort_ekimei xs)

(* testing *)
let yoyogi_uehara = {kanji="代々木上原"; kana="よよぎうえはら"; romaji="yoyogiuehara"; shozoku="千代田線"}
let yoyogi_koen = {kanji="代々木公園"; kana="よよぎこうえん"; romaji="yoyogikouen"; shozoku="千代田線"}
let omote_sando = {kanji="表参道"; kana="おもてさんどう"; romaji="omotesandou"; shozoku="千代田線"} 
let ikebukuro1 = {kanji="池袋"; kana="いけぶくろ"; romaji="ikebukuro"; shozoku="有楽町線"} 
let ikebukuro2 = {kanji="池袋"; kana="いけぶくろ"; romaji="ikebukuro"; shozoku="丸ノ内線"} 
let test_insort_ekimei = 
  insort_ekimei [yoyogi_uehara;yoyogi_koen;omote_sando;ikebukuro1;ikebukuro2]
let test_unit_ekimei =
  unit_ekimei [yoyogi_uehara;yoyogi_koen;omote_sando;ikebukuro1;ikebukuro2]

let test_seiretsu1 = 
  seiretsu [yoyogi_uehara;yoyogi_koen;omote_sando;ikebukuro1;ikebukuro2] 
   = [ikebukuro2;omote_sando;yoyogi_uehara;yoyogi_koen]
let test_seiretsu2 = seiretsu [] = []