Explicit naming of type variables

このページは最後に更新されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

last mod. 2010-08-05 (木) 17:15:50

OCaml 3.12 では fun (type t) ... という構文で型変数を通常の型のように扱うことができるようになりました。

例を使って説明しましょう。

リストの要素の重複を取り除きたい場合、安直には List.filter を使うところですが、これは計算量が O(n^2) のオーダーになってしまうので、要素数が増えてくると苦しいような気がします。要素に全順序が仮定できるのなら、 Set モジュールを使った方が効率がよさそうです。

let uniq cmp xs = ...

cmp を Set.OrderedType?.compare にして、ローカルモジュールを作ります。

let uniq (cmp : 'a -> 'a -> int) =
  let module S = Set.Make(struct type t = (* ??? *) let compare = cmp end) in
  ...

さて、 Set.OrderedType?.t にあたる型には何を指定すればよいでしょうか? 'a は型変数なのでここには書けません。

ここで fun (type t) の出番です。 t は Set.OrderedType? で使われているので (type s) としましょう。

let uniq = fun (type s) (cmp s -> s -> int) ->
  let module S = Set.Make(struct type t = s let compare = cmp end) in
  ...

この (type t) は関数定義の拡張構文の引数部分にも書くことができます。

let uniq (type s) (cmp : s -> s -> int) =
  let module S = Set.Make(struct type t = s let compare = cmp end) in
  ...

モジュールを作ることができたので、あとはこれを使うだけです。

let uniq (type s) (cmp : s -> s -> int) =
  let module S = Set.Make(struct type t = s let compare = cmp end) in
  fun xs ->
   S.elements (List.fold_right S.add xs S.empty)
(*
  val uniq : ('a -> 'a -> int) -> 'a list -> 'a list = <fun>
 *)

この s は fun (type s) ... -> expr の (type s) 以降 expr 以前の部分では普通の型名と同じように扱われますが、外側からは通常の型変数と同じように見えます。 uniq の型からもこのことがわかります。

新規 編集 添付