プログラミングの基礎 第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 [] = []