Есть ли лучший способ создать такую ​​очередь приоритетов?

Question

Я реализовал приоритетную очередь, она работает хорошо. Ниже следует определение моего типа.

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

Моя идея состоит в том, что дерево имеет функцию компаратора («а ->» а -> Int) и выдает «на т, что будет отсортирован компаратором.
Однако у меня есть компаратор на каждом Листе и Узде, и мне интересно, есть ли лучший способ сделать это.
В частности, учитывая дерево, я хочу иметь возможность легко получить доступ к его компаратору. И я не знаю, смогу ли я сделать это, не имея компаратора на каждом Узде и Листе моего дерева.

Благодаря

Answer 1

Стандартный подход к этой проблеме, чтобы написать функтор, заданный модуль, который включает в себя тип, содержащийся в вашем PQ + функции сравнения вы дали возвращает новый PQ модуль специализируется на том, что type и сравнение функция.

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 были построены с использованием той же функции сравнения.