Implementieren Okasaki Bootstrapped Heaps in OCaml, warum kompiliert es nicht?

Question

(Ein minimales Nicht-Kompilierung Beispiel kann bei https://gist.github.com/4044467 gefunden wird, weiter unten noch mehr Hintergrund sehen.)

I in Kapitel 10 des Okasaki rein funktionalen Datenstruktur Bootstrapped Heaps eingeführt umzusetzen versuchen. Das Folgende ist eine vereinfachte Version meines nicht kompilierenden Codes.

Wir sind ein Haufen mit folgenden Unterschrift zu implementieren:

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 

Wir sagen, eine Datenstruktur ist Bootstrap, wenn seine Umsetzung auf einer weiteren Implementierung der gleichen Art von Datenstruktur abhängt. So haben wir einen Haufen wie diese (die tatsächliche Umsetzung ist nicht wichtig):

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 

Dann wird der Bootstrap-Haufen wir implementieren gehen, die auf jedem Haufen Implementierung abhängen kann, soll die folgende Signatur haben : So können wir es so

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

verwenden:

module StringHeap = BootstrappedHeap(SomeHeap)(String) 

Die Implementierung von BootstrappedHeap nach Okasaki, ist wie folgt:

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 

Aber das kompiliert nicht! Die Fehlermeldung lautet:

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 

Die Linie 52 ist die Linie

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

Ich denke BootstrappedElemORDERED umgesetzt habe, da es sowohl t und compare hat, aber ich konnte nicht erkennen, warum der Compiler finden kann die compare Funktion.

ändern Sie die Signatur von BootstrappedElem zu

module rec BootstrappedElem : ORDERED 

wird es kompilieren machen, aber dies wird den Typkonstruktor E und T in BootstrappedElem verstecken, um es unmöglich, die später Teile zu implementieren.

Der gesamte nicht-Kompilierung-Code kann ich glaube an https://raw.github.com/gist/4044281/0ce0336c40b277e59cece43dbadb9b94ce6efdaf/ordered.ml

Answer 1

heruntergeladen werden dabei um einen Fehler in der Typprüfung sein könnte. Ich habe den Code in dem folgenden Beispiel reduziert:

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 

Ich verstehe nicht, warum der erste Code funktioniert und das zweite (die äquivalent scheint) nicht. Ich schlage vor, Sie warten ein wenig, um zu sehen, ob ein Experte mit einer Erklärung kommt (Andreas?), Dann überlegen Sie, senden Sie a bug report.

In diesem Fall ist eine Lösung, um zuerst die Unterschrift zu binden, die falsch behandelt scheinen:

(* 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 

jedoch, dass in Ihrer Einstellung nicht möglich ist, da die Signatur von BootstrappedElem mit BootstrappedHeap gegenseitig rekursiv ist.

Eine Abhilfe ist, die scheinbar verwöhnte with module ... Konstrukt und ersetzen sie durch eine einfache Art Gleichheit with type Elem.t = ... zu vermeiden:

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 

Sie können auch vermeiden, dass die gegenseitige Rekursion und definieren sowohl BootstrappedElem und BootstrappedHeap in einer rekursiven Knoten, durch Definieren BootstrappedEleminnerhalb der rekursive 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 

Dieser Stil entspricht natürlich Ihre Entscheidung von Elem in dem HEAP Signatur einbetten und mit with module ... zur Verfeinerung. Eine andere Lösung wäre gewesen, HEAP als einen Funktor zu definieren, der eine Signatur zurückgibt, die als HEAP(Elem).S verwendet wird, und ich nehme an, dass ein anderer rekursiver Stil gewählt worden sein könnte. Um nicht zu sagen, dass dies besser gewesen wäre: Ich denke, dass der "abstrakte Modul" -Stil bequemer ist.