OCaml一人勉強会 - Map - nihaaaaaaaa(のヮッ☆)

また随分間が空きましたが、大学も始まったことですしちゃっちゃかと参りましょう。
ファンクタシリーズ第二段。Mapです。整数をキーに受け取る Map を定義しましょう。比較関数には Pervasives.compare をそのまま使います。

# module IntMap = Map.Make(struct type t = int let compare = compare end);;
module IntMap :
  sig
    type key = int
    type +'a t
    val empty : 'a t
    val is_empty : 'a t -> bool
    val add : key -> 'a -> 'a t -> 'a t
    val find : key -> 'a t -> 'a
    val remove : key -> 'a t -> 'a t
    val mem : key -> 'a t -> bool
    val iter : (key -> 'a -> unit) -> 'a t -> unit
    val map : ('a -> 'b) -> 'a t -> 'b t
    val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
  end
# open IntMap;;

'a という見慣れない表記が出てきましたが、これは covariant とかいうらしいです。よく知りません。

まあ気にせずにいきます。詳細は偉い人に教えてもらいましょう（酷い）
ここで重要なのは IntMap が多相型だということですね。covariant とかしりません。
Set のように要素をリストとして取得できないので iter を使ってキーと要素を表示する関数を先に書いておきましょう。

# let print_map m = iter (fun k s -> print_int k; print_endline (" : " ^ s)) m;;
val print_map : string IntMap.t -> unit = <fun>

ちゃんと型推論されてて賢いなー。
Set 同様、空の Map を返す empty から始めます。 add でキーと要素を結びつけることができます。

# let m0, m1 = empty, empty;;
val m0 : 'a IntMap.t = <abstr>
val m1 : 'a IntMap.t = <abstr>
# let m0 = add 1 "hoge" m0;;
val m0 : string IntMap.t = <abstr>
# let m1 = add 1 3 m1;;
val m1 : int IntMap.t = <abstr>

add した時点で型変数がちゃんと型に置き換わってます。わー。
まあ m1 は上で定義した print_map が使えないのでいらない子です。

# print_map m0;;
1 : hoge
- : unit = ()
# print_map m1;;
Characters 10-12:
  print_map m1;;
            ^^
This expression has type int IntMap.t but is here used with type
  string IntMap.t

ジェネリックな print が欲しい所ですね…
既に存在するキーに値を結びつけようとすると、値は上書きされます。

# print_map (add 1 "hige" m0);;
1 : hige
- : unit = ()

さよなら "hoge"。
要素追加するばかりでも仕方ないので、取得してみましょう。 find を使います。find って bool 返しそうな感じがするのになー…

# find 1 m0;;
- : string = "hige"
# find 2 m0;;
Exception: Not_found.

要素がないと例外を飛ばします。OCamlのこういうところはちょっと嫌い。返すべき値が無いので仕方ないんですが…
キーが存在するか確かめてから要素を取得すれば例外飛ばさずにすみますね。ということでそういう時は mem を使いましょう。

# mem 2 m0;;
- : bool = false

mem が要素返して find が bool 返すと思うんだけれどなあ…！
次は要素を取り除いてみましょう。remove を使います。

# print_map (remove 2 m0);;
1 : hige
- : unit = ()
# print_map (remove 1 m0);;
- : unit = ()

存在しないキーを指定した場合例外…は飛ばずに何もおきない。えー？そうなの？ find みたく返すべき値が存在しないわけではないから納得はできるんですが。なんだか釈然としないなあ。
ある Map から別の Map を作りたいときは map。 mapmapmapmapmap。
しかしこの辺のイテレータ、どういう順番で要素まわってるんでしょうか。多分追加順だと思うんですが、謎です。

# print_map (map (fun x -> x ^ "++") m0);;
1 : hige++
- : unit = ()
# map (fun x -> [x]) m0;;
- : string list IntMap.t = <abstr>

いたってふつーです。違う型の Map も作れます。
キーも欲しいときは mapi を。なんていうか、嫌な名前ですね。

# mapi (fun k m -> (k,m)) m0;;
- : (IntMap.key * string) IntMap.t = <abstr>

もちろん、畳み込み？っていうの？ fold もあります。

# fold (fun k m s -> s ^ ":" ^ m) (add 2 "huga" m0) "";;
- : string = ":hige:huga"

折角なので fold を使ってキーと要素を入れ替えた Map を作ってみましょう。

# module StrMap = Map.Make(String);;
...
# let m2 = fold (fun k m s -> StrMap.add m k s) (add 2 "huga" m0) StrMap.empty;;
val m2 : IntMap.key StrMap.t = <abstr>

入れ替えるだけなので簡単ですね。わざわざ定義しないといけないのは面倒ですがそういうものです。
ちゃんとできてるか確かめてみましょう。

# StrMap.iter (Printf.printf "%s : %d\n") m2;;
hige : 1
huga : 2
- : unit = ()

できてますね。

まあそんな感じで Map でした。次はデータ構造はやめて入出力周りとかみていこうかなと思います。