functional-programming - OkasakiのブートストラップされたヒープをOCamlに実装すると、なぜコンパイルされないのですか？

Question

（最小限の非コンパイル例はhttps://gist.github.com/4044467にあります。以下の背景を参照してください。）

OkasakiのPurelyFunctionalDataStructureの第10章で紹介されているブートストラップヒープを実装しようとしています。以下は、私の非コンパイルコードの簡略版です。

次の署名を使用してヒープを実装します。

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

module type HEAP =
sig
  module Elem : ORDERED

  type heap

  val empty : heap
  val insert : Elem.t -> heap -> heap
  val find_min : heap -> Elem.t
  val delete_min : heap -> heap
end

データ構造は、その実装が同じ種類のデータ構造の別の実装に依存している場合にブートストラップされると言います。したがって、次のようなヒープがあります（実際の実装は重要ではありません）。

module SomeHeap (Element : ORDERED) : (HEAP with module Elem = Element) =
struct
  module Elem = Element

  type heap

  let empty = failwith "skipped"
  let insert = failwith "skipped"
  let find_min = failwith "skipped"
  let delete_min = failwith "skipped"
end 

次に、実装しようとしているブートストラップされたヒープは、任意のヒープ実装に依存する可能性があり、次のシグネチャを持つことになっています。

module BootstrappedHeap
  (MakeH : functor (Element : ORDERED) -> HEAP with module Elem = Element)
  (Element : ORDERED) : (HEAP with module Elem = Element)

したがって、次のように使用できます。

module StringHeap = BootstrappedHeap(SomeHeap)(String)

Okasakiによると、BootstrappedHeapの実装は次のようになります。

module BootstrappedHeap
  (MakeH : functor (Element : ORDERED) -> HEAP with module Elem = Element)
  (Element : ORDERED) : (HEAP with module Elem = Element) =
struct
  module Elem = Element

  module rec BootstrappedElem :
  sig
    type t =
      | E
      | H of Elem.t * PrimH.heap
    val compare : t -> t -> int
  end =
  struct
    type t =
      | E
      | H of Elem.t * PrimH.heap
    let compare t1 t2 = match t1, t2 with
      | H (x, _), H (y, _) -> Elem.compare x y
      | _ -> failwith "unreachable"
  end
  and PrimH : (HEAP with module Elem = BootstrappedElem) =
    MakeH(BootstrappedElem)

  type heap

  let empty = failwith "not implemented"
  let insert = failwith "not implemented"
  let find_min = failwith "not implemented"
  let delete_min = failwith "not implemented"
end

しかし、これはコンパイルではありません！エラーメッセージは次のとおりです。

File "ordered.ml", line 52, characters 15-55:
Error: In this `with' constraint, the new definition of Elem
       does not match its original definition in the constrained signature:
       Modules do not match:
         sig type t = BootstrappedElem.t end
       is not included in
         ORDERED
       The field `compare' is required but not provided

52行目は

and PrimH : (HEAP with module Elem = BootstrappedElem) =

との両方があるのでBootstrappedElem実装したと思いますが、コンパイラが関数を見つけられない理由がわかりませんでした。ORDEREDtcomparecompare

BootstrappedElemの署名をに変更します

module rec BootstrappedElem : ORDERED

コンパイルされますが、これにより型コンストラクターが非表示になりE、T後BootstrappedElemの部分を実装できなくなります。

非コンパイルコード全体は、https：//raw.github.com/gist/4044281/0ce0336c40b277e59cece43dbadb9b94ce6efdaf/ordered.mlからダウンロードできます。