Okami'nin OCaml'daki önyüklemeli yığınlarını uygulamak, neden derleme yapmıyor?

Question

(Bir minimal olmayan derleme örneği https://gist.github.com/4044467 bulunabilir, aşağıda daha arka plan bakın.) Ben Okasaki en Tamamen Fonksiyonel Veri Yapısı Bölüm 10'da sunulan desteksiz yığınları uygulamak çalışıyorum

. Aşağıdaki derleme kodumun basitleştirilmiş bir sürümüdür.

Biz şu imzası ile bir yığın uygulamak konum:

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 

Biz veri yapısı uygulama veri yapısı aynı tür başka uygulamasına bağlıdır zaman bootstrapped olduğunu söylüyorlar. Bu yüzden böyle bir yığın (gerçek uygulanmasında önemli değildir) sahiptir:

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 

Sonra herhangi yığın uygulanmasına bağlı olabilir biz uygulamak için gidiyoruz desteksiz yığın, aşağıdaki imza gerekiyordu :

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

Bu yüzden bu gibi kullanabilirsiniz:

module StringHeap = BootstrappedHeap(SomeHeap)(String) 

BootstrappedHeap uygulanması, Okasaki göre şu şekildedir:

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 

Ancak bu bir derleme değil!

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 

hat 52

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

Ben hem t ve compare olduğu gibi BootstrappedElemORDERED uygulamak düşünmedin hattını oluşturmak, ama derleyici bulamazsa nedenini görmek için başarısız oldu: hata mesajıdır compare işlevi.

Değişim

module rec BootstrappedElem : ORDERED 

için BootstrappedElem imzası o derleme yapacak ama bu imkansız sonraki kısımlarını uygulamak için yapmak BootstrappedElem tip yapıcısı E ve T gizler.

bütün olmayan derleme kod

Bu tip denetleyici bir hata olabileceğini düşünüyoruz https://raw.github.com/gist/4044281/0ce0336c40b277e59cece43dbadb9b94ce6efdaf/ordered.ml

Answer 1

de indirilebilir. Ben aşağıdaki örneğe kodunuzu azaltmıştır: ilk kod çalışır ve (eşdeğer görünüyor) ikinci yapmaz neden

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 

anlamıyorum. Bir uzmanın bir açıklama ile gelip gelmediğini görmek için biraz beklemenizi öneririm (Andreas?), Sonra a bug report göndermeyi düşünün.BootstrappedElem imzası BootstrappedHeap karşılıklı özyinelemeli olduğundan,

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

Ancak, bu senin ayarında mümkün değildir: Bu durumda

, çözüm birinci mishandled görünüyor imzayı bağlamaktır.

bir geçici çözüm görünüşte-narin with module ... yapısını önlemek ve basit tip eşitlik with type Elem.t = ... ile değiştirmek için:

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 

Ayrıca karşılıklı özyinelemeye önlemek ve bir özyinelemeli düğüm hem BootstrappedElem ve BootstrappedHeap tanımlayabiliriz, BootstrappedElem'u numaralı özette BootstrappedHeap özyinelemede tanımlayarak.

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 

Bu stil HEAP imzasında Elem gömme ve arıtma için with module ... kullanmanın sizin karar doğal olarak gelir. Başka bir çözüm ise HEAP'u HEAP(Elem).S olarak kullanılan imzayı döndüren bir çevirici olarak tanımlamak olurdu ve sanırım farklı bir özyinelemeyi seçmiş olabilirsiniz. Bunun daha iyi olacağını söylemek istemiyorum: "Soyut modül" tarzının daha uygun olduğunu düşünüyorum.