ओकैम में ओकासाकी के बूटस्ट्रैप किए गए ढेर को कार्यान्वित करना, यह संकलित क्यों नहीं करता है?

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 लाइन

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

मुझे लगता है कि BootstrappedElem लागू किया ORDERED के रूप में यह दोनों t और compare है है, लेकिन मैं यह देखने के लिए क्यों संकलक को खोजने में विफल विफल रहा है compare फ़ंक्शन।

बदलें

module rec BootstrappedElem : ORDERED 

को BootstrappedElem के हस्ताक्षर यह संकलन कर देगा, लेकिन यह यह असंभव बाद में भागों को लागू करने के बनाने के लिए प्रकार निर्माता E और TBootstrappedElem में छिपा होगा।

पूरे गैर संकलन कोड 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 

मुझे समझ नहीं आता क्यों पहले कोड काम करता है और दूसरा (जो बराबर लगता है) नहीं करता है। मेरा सुझाव है कि आप यह देखने के लिए थोड़ा इंतजार करें कि कोई विशेषज्ञ स्पष्टीकरण (एंड्रियास?) के साथ आता है, फिर a bug report भेजने पर विचार करें।,

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

हालांकि, कि संभव नहीं अपनी सेटिंग में है, क्योंकि BootstrappedElem के हस्ताक्षर BootstrappedHeap साथ पारस्परिक रूप से पुनरावर्ती है:

इस मामले में, एक समाधान पहले हस्ताक्षर है कि गलत ढंग से निपटाया लगता बाध्य करने के लिए है।

का संभावित हल जाहिरा तौर-नाजुक 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 

तुम भी आपसी प्रत्यावर्तन से बचने और एक पुनरावर्ती गाँठ में दोनों 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 embedding और शोधन के लिए with module ... का उपयोग कर के अपने निर्णय करने के लिए स्वाभाविक रूप से मेल खाती है। एक और समाधान HEAP को एक हस्ताक्षर लौटने वाले एक मज़ेदार के रूप में परिभाषित करना होगा, जिसे HEAP(Elem).S के रूप में उपयोग किया जाता है, और मुझे लगता है कि एक अलग रिकर्सिव शैली का चयन किया जा सकता था। यह नहीं कहना कि यह बेहतर होगा: मुझे लगता है कि "अमूर्त मॉड्यूल" शैली अधिक सुविधाजनक है।