ओकैम

Question

में म्यूटेबल वैरिएबल का हैशटेबल मुझे ओकैम में म्यूटेबल वैरिएबल के हैशटेबल का उपयोग करने की आवश्यकता है, लेकिन यह काम नहीं करता है।

let link = Hashtbl.create 3;; 
let a = ref [1;2];; 
let b = ref [3;4];; 
Hashtbl.add link a b;; 

# Hashtbl.mem link a;; 
- : bool = true 

# a := 5::!a;; 
- : unit =() 

# Hashtbl.mem link a;; 
- : bool = false 

वहाँ यह काम करता है बनाने के लिए कोई तरीका है?

Answer 1

समान सामग्री वाले हो सकता है कि परिवर्तनीय चर को अभी भी अलग किया जा सकता है क्योंकि वे स्मृति में विभिन्न स्थानों पर संग्रहीत हैं। उनकी तुलना भौतिक समानता ऑपरेटर (==) से की जा सकती है। हालांकि, ओकैमल समानता से बेहतर कुछ भी प्रदान नहीं करता है, यह संदर्भों पर एक नॉनट्रिविअल हैश फ़ंक्शन या ऑर्डर प्रदान नहीं करता है, इसलिए संदर्भों को संग्रहीत करने के लिए आप केवल एक ही डेटा संरचना बना सकते हैं, कुछ रूपों की एक एसोसिएशन सूची है, जिसमें $ \ Theta (n) अधिकांश उपयोगों के लिए $ एक्सेस समय।

(यदि आप गंदे खेलते हैं तो आप वास्तव में अंतर्निहित सूचक पर जा सकते हैं। लेकिन सूचक आपके पैरों के नीचे जा सकता है। फिर भी इसका उपयोग करने का एक तरीका है, लेकिन यदि आपको पूछने की ज़रूरत है, तो आपको इसका उपयोग नहीं करना चाहिए और आप वैसे भी इसके लिए पर्याप्त हताश नहीं हैं।)

दो अलग-अलग संदर्भों में एक अलग सामग्री होने पर संदर्भों की तुलना करना आसान होगा। तो इसे बनाओ! अपने संदर्भों में एक अद्वितीय पहचानकर्ता जोड़ें। एक वैश्विक काउंटर रखें, प्रत्येक बार जब आप कोई संदर्भ बनाते हैं तो इसे 1 तक बढ़ाएं, और डेटा के साथ काउंटर वैल्यू स्टोर करें। अब आपके संदर्भों को उनके काउंटर वैल्यू द्वारा अनुक्रमित किया जा सकता है।

let counter = ref 0 
let new_var x = incr counter; ref (!counter, x) 
let var_value v = snd !v 
let update_var v x = v := (fst !v, x) 
let hash_var v = Hashtbl.hash (fst !v) 

बेहतर प्रकार सुरक्षा और बेहतर दक्षता के लिए, एक काउंटर मूल्य और एक आइटम युक्त एक डेटा संरचना परिभाषित करते हैं।

let counter = ref 0 
type counter = int 
type 'a variable = { 
    key : counter; 
    mutable data : 'a; 
} 
let new_var x = incr counter; {key = !counter; data = x} 
let hash_var v = Hashtbl.hash v.key 

आप एक मॉड्यूल में उपरोक्त कोड डाल दिया और counter प्रकार सार कर सकते हैं। साथ ही, आप Hashtbl फ़ैक्टरोरियल इंटरफ़ेस का उपयोग करके हैश तालिका मॉड्यूल को परिभाषित कर सकते हैं। एक क्लीनर, अधिक मॉड्यूलर संरचना के साथ चर और एक हैश टेबल संरचना को परिभाषित करने का एक और तरीका यहां दिया गया है।

module Counter = (struct 
    type t = int 
    let counter = ref 0 
    let next() = incr counter; !counter 
    let value c = c 
end : sig 
    type t 
    val next : unit -> t 
    val value : t -> int 
end) 
module Variable = struct 
    type 'a variable = { 
     mutable data : 'a; 
     key : Counter.t; 
    } 
    let make x = {key = Counter.next(); data = x} 
    let update v x = v.data <- x 
    let get v = v.data 
    let equal v1 v2 = v1 == v2 
    let hash v = Counter.value v.key 
    let compare v1 v2 = Counter.value v2.key - Counter.value v1.key 
end 
module Make = functor(A : sig type t end) -> struct 
    module M = struct 
    type t = A.t Variable.variable 
    include Variable 
    end 
    module Hashtbl = Hashtbl.Make(M) 
    module Set = Set.Make(M) 
    module Map = Map.Make(M) 
end 

हम मध्यवर्ती मॉड्यूल Variable जरूरत है क्योंकि प्रकार variable पैरामीट्रिक है और मानक पुस्तकालय डेटा संरचना functors (Hashtbl.Make, Set.Make, Map.Make) केवल कोई तर्क के साथ प्रकार निर्माताओं के लिए परिभाषित कर रहे हैं। यहां एक इंटरफ़ेस है जो एक संबंधित हैश तालिका (और सेट, और मानचित्र) प्रकार के साथ, पॉलिमॉर्फिक इंटरफ़ेस (संबंधित कार्यों के साथ, लेकिन डेटा संरचनाओं के साथ) और मोनोमोर्फिक उदाहरणों के निर्माण के लिए एक मजेदार दोनों का खुलासा करता है।

module Variable : sig 
    type 'a variable 
    val make : 'a -> 'a variable 
    val update : 'a variable -> 'a -> unit 
    val get : 'a variable -> 'a 
    val equal : 'a -> 'a -> bool 
    val hash : 'a variable -> int 
    val compare : 'a variable -> 'b variable -> int 
end 
module Make : functor(A : sig type t end) -> sig 
    module M : sig 
    type t = A.t variable.variable 
    val make : A.t -> t 
    val update : t -> A.t -> unit 
    val get : t -> A.t 
    val equal : t -> t -> bool 
    val hash : t -> int 
    val compare : t -> t -> int 
    end 
    module Hashtbl : Hashtbl.S with type key = M.t 
    module Set : Set.S with type key = M.t 
    module Map : Map.S with type key = M.t 
end 

ध्यान दें कि अगर आप उम्मीद करते हैं कि अपने कार्यक्रम एक रन के दौरान अधिक से अधिक 2^30 चर उत्पन्न हो सकता है, एक int इसे काट नहीं होगा। 2^60-बिट मान, या Int64.t बनाने के लिए आपको दो int मानों की आवश्यकता है।

ध्यान दें कि यदि आपका प्रोग्राम बहुप्रचारित है, तो आपको वृद्धि और लुकअप परमाणु बनाने के लिए काउंटर के चारों ओर एक ताला की आवश्यकता है।

Answer 2

आप फ़ैक्टरोरियल इंटरफ़ेस का उपयोग कर सकते हैं, जो आपको अपने हैश और समानता कार्यों की आपूर्ति करने देता है। फिर आप उन कार्यों को लिखते हैं जो केवल आपके मूल्यों के गैर-परिवर्तनीय भागों पर आधारित होते हैं। इस उदाहरण में, कोई गैर-परिवर्तनीय भाग नहीं हैं। इसलिए, यह विशेष रूप से स्पष्ट नहीं है कि आप तालिका में क्या ढूंढ रहे हैं। लेकिन एक और यथार्थवादी उदाहरण (मेरे अनुभव में) में गैर-परिवर्तनीय भाग हैं जिनका आप उपयोग कर सकते हैं।

यदि कोई गैर-परिवर्तनीय भाग नहीं हैं, तो आप उन्हें विशेष रूप से हैशिंग में उपयोग के लिए जोड़ सकते हैं। उदाहरण के लिए, आप प्रत्येक मान के लिए एक मनमाना अद्वितीय पूर्णांक जोड़ सकते हैं।

शारीरिक समानता (==) के आधार पर हैशिंग करना भी संभव है, जिसमें संदर्भ (और अन्य परिवर्तनीय मान) के लिए उचित परिभाषा है। आपको इसके साथ सावधान रहना होगा, हालांकि, शारीरिक समानता थोड़ा मुश्किल है। उदाहरण के लिए, आप अपनी हैश कुंजी के रूप में किसी मान के भौतिक पते का उपयोग नहीं कर सकते - कचरा संग्रहण के कारण किसी भी समय कोई पता बदल सकता है।