2

優先キューを実装しましたが、うまく機能します。以下は私の型定義です。

type 'a t = | Leaf of ('a -> 'a -> int)
            | Node of 'a * 'a t * 'a t * ('a -> 'a -> int)

私の考えでは、ツリーはコンパレータ関数 ('a -> 'a -> int) を取り、コンパレータによってソートされる 'at を生成します。
ただし、すべてのリーフとノードにコンパレーターがあり、それを行うより良い方法があるかどうか疑問に思っています。
具体的には、ツリーが与えられた場合、そのコンパレーターに簡単にアクセスできるようにしたいと考えています。そして、ツリーのすべてのノードとリーフにコンパレーターを配置せずにこれを実行できるかどうかはわかりません。

ありがとう

4

1 に答える 1

4

この問題に対する標準的なアプローチは、PQ に含まれる型 + 与えられた比較関数を含むモジュールを指定すると、その型と比較関数に特化した新しい PQ モジュールを返すファンクターを作成することです。

module PriorityQueue (OT : Map.OrderedType) = struct
  type t = 
    | Leaf
    | Node of OT.t * t * t
  (*Define your functions in terms of OT.compare ...*)
end

次に、具体的な PriorityQueue モジュールを作成します

module FunnyPQ = PriorityQueue(struct
  type t = int
  let compare _ _ = pred (Random.int 3)
end)

OrderedType の定義を参照してください: http://caml.inria.fr/pub/docs/manual-ocaml-4.00/libref/Map.OrderedType.html

もちろん、あなたが取ったアプローチを使用することもできますが、次の方法でデータ型を2つの型に分解します

type 'a pq = 
  | Leaf
  | Node of 'a * 'a pq * 'a pq

type 'a t = { 
  comp : 'a -> 'a -> int ;
  pq : 'a pq
}

'a pq -> 'a pq -> 'a pqたとえば次のようなシグネチャを使用して関数を記述している場合、最初の pq 引数と 2 番目の pq 引数が同じ比較関数で構築されていることを保証できないため、このアプローチでは型の安全性が失われることに注意してください。

于 2013-03-12T20:36:07.343 に答える