2

我已经实现了一个优先队列，它运行良好。下面是我的类型定义。

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

我的想法是树接受一个比较器函数（'a -> 'a -> int）并产生一个'at，它将由比较器排序。
但是，我在每个 Leaf 和 Node 上都有比较器，我想知道是否有更好的方法来做到这一点。
具体来说，给定一棵树，我希望能够轻松访问它的比较器。而且我不知道如果我的树的每个节点和叶子上没有比较器，我是否可以做到这一点。

谢谢

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 参数和第二个 pq 参数是使用相同的比较函数构造的。

于 2013-03-12T20:36:07.343 回答