2012-02-03 8 views
2

私が念頭に置いているデータ構造には、一意の文字列を格納するメンバーのレコードが含まれています。 は、抽象的に、これは私が考えているレコードです:Ocamlのレコード内のコンテナ

struct A { 
name: string; 
neighbors: Set of String; 
}; 

しかし、私はOCamlでは、レコード内の設定コンテナを作成するように見えることはできません。セットがファンクタであり、伝統的なタイプではないことを考えれば、私はこれをどのように行うことができるのか分かりません。

答えて

5

Setは、必要なセットのタイプごとに新しいタイプをインスタンス化するファンクタです。比較関数を知る必要があるので、string listのようにstring setを実行することはできません(Batteries IncludedまたはextlibからPSet、多型セットを使用しない限り)。あなたが理解する必要が

type record = { 
    name: string; 
    neighbors: string BatSet.t 
}; 
2

:だから:バッテリー多型セット(それは型チェックしないとあなたは同じ比較関数を使用していること、それに注意してください)で

module StringSet = Set.Make(String);; (* or use BatSet.StringSet *) 
type record = { 
    name: string; 
    neighbors: StringSet.t; 
}; 

たとえば、 "文字列リスト"とビルドしたい "文字列セット"の違いです。

リストの場合、そのリストは、リストを作成するためにリストの内容について何も知る必要がないため、「リスト」です。あるセットに対しては、ログ(N)時間のアクセスが必要です。そのために、要素の順序に応じてセットを整理したいとします。だから、あなたはそれらを比較することができる必要があります。 OCamlはデフォルトの比較関数(Pervasives.compare)を提供していますが、その関数は必ずしも最良のものではありません。例えば、整数などのために高価ですし、常に動作しません。値の構造は、常にあなたが望む順序ではありません)。

OCamlでは、型が値に依存する場合( "集合"の場合ですが、 "ソート済みリスト"の場合もあります)、型を定義するためにファンクタを使用する必要があります。ファンクタを適用して新しいタイプを取得します。

このコードがあなたのために何をするかです:

モジュールStringSet = Set.Make(String)を

は同等です:

module StringSet = Set.Make(struct 
    type t = string 
    let compare = compare 
end) 

「比較=比較してみましょう比較関数がデフォルト値であることを意味します(2番目の比較はPervasives.compareを参照します)。 Stringモジュールにはすでに "type t = string"と "let compare = compare"が含まれているので、代わりに "String"を直接使用できます。

関連する問題