मज़ेदार Map.make में विलय के OCaml semantics?

Question

मैं एक ओकैमल फ़ंक्शन लिख रहा हूं जहां मुझे दो मानचित्रों को मर्ज करने की आवश्यकता है। मैं merge फ़ंक्शन Map.Make (OCaml के संस्करण 3.12.0 में पाया गया) द्वारा प्रदान किए गए फ़ंक्शन के अर्थशास्त्र को समझने में सक्षम नहीं हूं। क्या कोई मुझे ओकैमल मैनुअल से अधिक विस्तृत स्पष्टीकरण प्रदान कर सकता है? एक उदाहरण शायद मेरे लिए इसे समझने के लिए पर्याप्त होगा।

इसके अतिरिक्त, दो मैप्स जिन्हें मुझे विलय करने की आवश्यकता है, उनमें कुछ रोचक गुण हैं: चाबियाँ एक ही प्रकार (int, वास्तव में) हैं, और उनका डोमेन विवादित है। विलय दिनचर्या से अधिक कुशल दृष्टिकोण होगा?

Answer 1

merge एक फ़ंक्शन और दो मानचित्र लेता है। किसी भी मानचित्र में मौजूद प्रत्येक कुंजी के लिए, फ़ंक्शन को कॉल किया जाएगा। यदि कुंजी केवल नक्शे में से एक में मौजूद है, तो दूसरे के लिए मूल्य किसी के रूप में पारित नहीं किया जाएगा (यही कारण है कि तर्क विकल्प हैं)। यदि फ़ंक्शन Some x लौटाते हैं, तो नए मानचित्र में प्रश्न की कुंजी के लिए x मान होगा। अन्यथा कुंजी मौजूद नहीं होगी।

उदाहरण:

let map1 = add 1 2 (add 2 3 empty);; 
let map2 = add 2 5 (add 3 4 empty);; 
let map3 = merge (fun k xo yo -> match xo,yo with 
    | Some x, Some y -> Some (x+y) 
    | _ -> None 
) map1 map2;; 

अब मानचित्रण 2 -> 8 शामिल map3।

आप के लिए इसे बदल हैं:

let map3 = merge (fun k xo yo -> match xo,yo with 
    | Some x, Some y -> Some (x+y) 
    | None, yo -> yo 
    | xo, None -> xo 
) map1 map2;; 

यह मैपिंग 1 -> 2, 2 -> 8 और 3 -> 4 शामिल होंगे।

Answer 2

पहले उत्तर के आधार पर, और अतिरिक्त प्रश्न (संबंध तोड़ना डोमेन के मामले में नक्शे विलय), मैं उसके बाद निम्न सामान्य मर्ज दिनचर्या का प्रस्ताव होगा विचार:

let merge_disjoint m1 m2 = 
    IntMap.merge 
    (fun k x0 y0 -> 
     match x0, y0 with 
     None, None -> None 
     | None, Some v | Some v, None -> Some v 
     | _, _ -> invalid_arg "merge_disjoint: maps are not disjoint") 
    m1 m2 

वहाँ कुछ अधिक कुशल तरीका होगा यह करने के लिए?

- डेविड।

Answer 3

अपने नक्शे के बाद से संबंध तोड़ना हैं तो आप सिर्फ छोटे मानचित्र के माध्यम से लूप और में सम्मिलित कर सकते बड़ा:

let disjoint_merge m1 m2 = 
    if (IntMap.cardinal m1) < (IntMap.cardinal m2) then 
    IntMap.fold IntMap.add m1 m2 
    else 
    IntMap.fold IntMap.add m2 m1 

घटना में है कि आप OCaml के एक पुराने संस्करण है कि cardinal शामिल नहीं है का उपयोग कर रहे फ़ंक्शन आप हमेशा एक मानचित्र को हमेशा के माध्यम से फिर से शुरू करने के लिए चुन सकते हैं। क्या इसके बाद के संस्करण कोड करता है का सवाल है, यह का उपयोग करता है: सभी तत्वों के माध्यम से

val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b 

कौन सा मूल रूप से दोहराता एक नक्शा है, और एक समारोह है कि एक चाबी, मूल्य और प्रकार 'b के कुछ अन्य चर लेता है और के बारे में कुछ रिटर्न कॉल उस प्रकार ('b)। हमारे मामले में हम IntMap.add फ़ंक्शन पास कर रहे हैं और यह अन्य चर हमारा दूसरा मानचित्र है। तो यह सभी तत्वों के माध्यम से पुनरावृत्त करता है और उन्हें दूसरे मानचित्र में जोड़ता है।

संपादित करें: आप से बेहतर कर रहे हैं बस कर रही:

let disjoint_merge m1 m2 = 
    IntMap.fold IntMap.add m1 m2 

EDIT2: और भी बेहतर:

let disjoint_merge = IntMap.fold IntMap.add;; 

मैं सिर्फ cardinal के कार्यान्वयन को देखा और यह पेड़ चलता है और गिनती देता है। तो आकारों की जांच करके आप ओ (एन + एम + मिनट (एन, एम) लॉग (अधिकतम (एन, एम)) कर रहे हैं बस ओ (एन लॉग (एम) के बजाय)।