5

私はOCamlでセット（バランスの取れた探索木）の表現を実装しました。それは実際にMakeは署名の関手です

module Make :
  functor (T : ORDERED_TYPE) ->
sig
  type elt = T.t
  type t
  val empty : t
  val cons : elt -> t -> t
  val delete : elt -> t -> t
  val mem : elt -> t -> bool
  val cardinal : t -> int
end

どこ

 module type ORDERED_TYPE = sig type t val compare : t -> t -> int end

Mapここで、標準ライブラリのような辞書を実装したいと思います。次のような署名が必要です

 module Make: functor (T : ORDERED_TYPE) -> sig
    type key = T.t
    type +'a t
    ...
 end

t辞書の種類はどこですか。

バランスの取れた探索木を再び実装することはエレガントではないので、上記のファンクターとして実装されたセットの観点から辞書を定義したいと思います。それをしてもいいですか？

4

4 に答える 4

4

ジェフリーが指摘したように、あなたのSetインターフェースは、その上に便利に実装するのに十分な表現力がありませんMap。セットをキーからユニット値へのマップとして定義することにより、Setから実装する方が簡単です。Map

私がお勧めするもう1つの可能性は、最初に、カプセル化されていないバランスの取れた検索ツリーのモジュールを公開することです。これは、インターフェイスによって完全に明らかにされる効率的なデータ構造を提供することを唯一の目的としています。そうすれば、ゲームをプレイして一方を他方で定義する必要なしに、Mapとを含む任意のデータ構造に自由に再利用できます。Setこの場合、これはそれほど重要ではないかもしれませんが（ほとんどの目的でSetから定義するのが合理的です）、私の意見では、一般的な場合の方が優れた設計です。Map

簡単に言うと、実装を再利用する場合は、「実装モジュール」を公開し、その上に「インターフェースモジュール」を定義します。

于 2012-04-29T07:53:25.017 に答える
3

私には、マップは順序付けられたペアのセットである (部分的な) 関数のようです。比較関数を正しく定義すれば、それができると思います。メンバーシップの目的で 2 つの値を比較すると等しいが、実際には等しい値ではないという事実を説明するために、関数を Set インターフェイスに追加する必要がある場合があります。現在のインターフェイスでマップのルックアップ関数を定義することはできないようです。

于 2012-04-29T06:21:15.507 に答える
2

他の人がすでに指摘しているように、指定されたセットの上に要求されたマップファンクターを実装できない理由は少なくとも2つあります。

  1. セットシグニチャは、特定のセット内の「等しい」要素を見つける方法を提供しません。
  2. そして、たとえそうだとしても、タイプ'a mapが要求するように思われるので、そこに多形的に値を格納することはできませんでした。

このタスクでは、セットの上にマップを実装する必要がありますか？たぶん、あなたはそれらをセットのように実装することになっていますか？

于 2012-04-29T09:36:39.577 に答える
0

まあ、実際にはそこに等号演算子があります-順序付けられた型からの比較関数です。

したがって、キー部分のみを比較するキー/値型の独自のモジュールを定義します。

module Keyvalue = struct
   type t = ('a * 'b)
   let compare x y = Pervasives.compare (fst x) (fst y)
end

これで完了です。ここでの問題は、Setがその値を取得できないことです。get関数もfold関数もありません。これは、そのようなデータ構造に対して実際に制限されています。Setの実装をいじることが許されている場合は、 get関数を追加する必要があります。

module Set = sig
   ...
   get : t -> elt -> elt
end

ちょうど要求された要素を返します。返されたタプルの 2 番目の要素を取得すると、元のキーと値のペアから値が取得されます。

于 2012-05-02T13:08:28.393 に答える