OCamlで岡崎のブートストラップされたヒープを実装すると、なぜコンパイルされませんか？

Question

（最小限の非コンパイルする例がhttps://gist.github.com/4044467で見つけることができ、以下のより多くの背景を参照してください。）

私はOkasakiの純粋に機能的なデータ構造の第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) 

BootstrappedHeapの実装、Okasakiによると、このようなものです：

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は、私はBootstrappedElemはそれがtとcompareの両方を持っているようORDEREDを実装しましたが、私は、コンパイラが見つからなかった理由を見ることができなかったと思うライン

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

ですcompare機能です。

module rec BootstrappedElem : ORDERED 

にBootstrappedElemの

変更署名は、それがコンパイルになりますが、これは、それは不可能後で部品を実装できるようにすることBootstrappedElemで型コンストラクタEとTを非表示になります。

全体の非コンパイルしたコードは、私は、これが型チェッカのバグかもしれないと考えていhttps://raw.github.com/gist/4044281/0ce0336c40b277e59cece43dbadb9b94ce6efdaf/ordered.ml

Answer 1

でダウンロードすることができます。私はあなたのコードを次のように減らしました：

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


module type CARRY = sig 
    module M : ORDERED 
end 

(* works *) 
module HigherOrderFunctor 
    (Make : functor (X : ORDERED) -> (CARRY with module M = X)) 
= struct 
    module rec Base 
    : (ORDERED with type t = string) 
    = String 
    and Other 
    : (CARRY with module M = Base) 
    = Make(Base) 
end 

(* does not work *) 
module HigherOrderFunctor 
    (Make : functor (X : ORDERED) -> (CARRY with module M = X)) 
= struct 
    module rec Base 
    : sig 
     (* 'compare' seems dropped from this signature *) 
     type t = string 
     val compare : t -> t -> int 
    end 
    = String 
    and Other 
    : (CARRY with module M = (Base : sig type t = string val compare : t -> t -> int end)) 
    = Make(Base) 
end 

私は最初のコードが動作し、2番目のコード（これは同等と思われます）が理解できません。私はあなたが専門家が説明（Andreas？）を持って来るのを見るためにちょっと待ってから、a bug reportを送ることを検討することをお勧めします。この場合

、解決策は、最初の取り扱いを誤っ思わ署名をバインドすることです：BootstrappedElemの署名がBootstrappedHeapと相互に再帰的であるため、

(* works again *) 
module HigherOrderFunctor 
    (Make : functor (X : ORDERED) -> (CARRY with module M = X)) 
= struct 
    (* bind the problematic signature first *) 
    module type S = sig 
    type t = string 
    val compare : t -> t -> int 
    end 

    module rec Base : S = String 
    and Other : (CARRY with module M = Base) = Make(Base) 
end 

しかし、それは、あなたの設定では不可能です。

この問題を回避するには、明らかに、繊細なwith module ...構造物を避け、シンプルなタイプの平等with type Elem.t = ...でそれを置き換えることです：

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 type Elem.t = BootstrappedElem.t) = 
    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 

あなたはまた、相互再帰を避け、1つの再帰的な結び目にBootstrappedElemとBootstrappedHeapの両方を定義することができ、 BootstrappedElemを内に定義することによって、再帰的BootstrappedHeapを定義します。

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

    module Elem = Element 

    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 

このスタイルはHEAP署名にElemを埋め込むと洗練のためwith module ...を使用してのあなたの決定に自然に対応しています。もう1つの解決策は、HEAP(Elem).Sとして使用される署名を返すファンクタとしてHEAPを定義することでした。異なる再帰スタイルが選択されている可能性があります。これはより良いとは言えません：私は "抽象的なモジュール"スタイルがより便利だと思います。