एफ # में परिवर्तनीय डेटा संरचनाओं (उदाहरण के लिए, सूची छोड़ें, पेड़ स्प्ले) करने का सही तरीका क्या है?

Question

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

एफ # में कार्यात्मक डेटा संरचनाओं को कैसे करें, इसके बारे में बहुत सारे उदाहरण हैं, लेकिन म्यूटेबल डेटा संरचनाओं को कैसे करें, इस पर बहुत कुछ नहीं है, इसलिए मैंने दोगुनी लिंक्ड सूची here को किसी ऐसी चीज में ठीक करना शुरू किया जो आवेषण की अनुमति देता है और कहीं भी हटा देता है। मेरी योजना इसे एक स्किप सूची में बदलना है, और फिर पेड़ संरचनाओं के लिए एक समान संरचना (रिकॉर्ड के भेदभाव संघ) का उपयोग करना है जिसे मैं कार्यान्वित करना चाहता हूं। कुछ और अधिक महत्वपूर्ण शुरू करने से पहले, क्या एफ # में इस तरह के परिवर्तनीय संरचनाओं को करने का एक बेहतर तरीका है? क्या मुझे सिर्फ रिकॉर्ड का उपयोग करना चाहिए और भेदभाव वाले संघ से परेशान नहीं होना चाहिए? क्या मुझे इसके बजाय कक्षा का उपयोग करना चाहिए? क्या यह प्रश्न "गलत भी नहीं है"? क्या मुझे सी # में म्यूटेबल स्ट्रक्चर्स करना चाहिए, और एफ # में डुबकी नहीं डालना चाहिए जब तक कि मैं उन्हें अपने पूरी तरह कार्यात्मक समकक्षों से तुलना नहीं करना चाहता?

और, यदि रिकॉर्ड की एक डीयू है जो मैं चाहता हूं, तो क्या मैं नीचे दिए गए कोड को बेहतर या अधिक मूर्खता से लिख सकता हूं? ऐसा लगता है कि यहां बहुत सारी अनावश्यकता है, लेकिन मुझे यकीन नहीं है कि इससे कैसे छुटकारा पाना है।

module DoublyLinkedList = 
    type 'a ll = 
     | None 
     | Node of 'a ll_node 
    and 'a ll_node = { 
     mutable Prev: 'a ll; 
     Element : 'a ; 
     mutable Next: 'a ll; 
    } 

    let insert x l = 
     match l with 
     | None -> Node({ Prev=None; Element=x; Next=None }) 
     | Node(node) -> 
      match node.Prev with 
       | None -> 
        let new_node = { Prev=None; Element=x; Next=Node(node)} 
        node.Prev <- Node(new_node) 
        Node(new_node) 
       | Node(prev_node) -> 
        let new_node = { Prev=node.Prev; Element=x; Next=Node(node)} 
        node.Prev <- Node(new_node) 
        prev_node.Next <- Node(new_node) 
        Node(prev_node) 

    let rec nth n l = 
     match n, l with 
     | _,None -> None 
     | _,Node(node) when n > 0 -> nth (n-1) node.Next 
     | _,Node(node) when n < 0 -> nth (n+1) node.Prev 
     | _,Node(node) -> Node(node) //hopefully only when n = 0 :-) 

    let rec printLinkedList head = 
     match head with 
     | None ->() 
     | Node(x) -> 
      let prev = match x.Prev with 
         | None -> "-" 
         | Node(y) -> y.Element.ToString() 
      let cur = x.Element.ToString() 
      let next = match x.Next with 
         | None -> "-" 
         | Node(y) -> y.Element.ToString() 
      printfn "%s, <- %s -> %s" prev cur next 
      printLinkedList x.Next 

Answer 1

मुझे लगता है कि एक परिवर्तनीय रिकॉर्ड के साथ एक भेदभाव संघ का उपयोग करना एक अच्छा दृष्टिकोण है। पैटर्न मिलान के लिए भेदभाव वाले संघ आवश्यक हैं। परिवर्तनशील रिकॉर्ड का उपयोग कर के लिए एक वैकल्पिक परिवर्तनशील संदर्भ कोशिकाओं के साथ एक संघ मामला बनाने के लिए होगा:

// Note: using ´ instead of ' to avoid StackOverflow syntax confusion 
type LinkedList<´T> = 
    | None 
    | Node of (LinkedList<´T> ref) * 'T * (LinkedList<´T> ref) 

यह थोड़ा सरल कोड को जन्म दे सकती। उदाहरण के लिए insert समारोह (मैं इसे की कोशिश नहीं की है, लेकिन मुझे लगता है कि यह सही होना चाहिए) इस प्रकार दिखाई देगा:

let insert x l = 
    match l with 
    | None -> Node(ref None, x, ref None) 
    | Node(prev, v, next) as node -> 
     match !prev with 
     | None -> 
     prev := Node(ref None, x, ref node) 
     !prev 
     | Node(_, _, prevNextRef) -> 
     prevNextRef := Node(ref (!node.Prev), x, ref node) 
     prev := !prevNextRef 
     !prevNextRef 

हालांकि, मैं इस कोड को और अधिक संक्षिप्त बनाता है नहीं लगता है (हो सकता है यहां तक ​​कि थोड़ा कम पठनीय)। किसी भी मामले में, आप एक match अभिव्यक्ति का उपयोग करके insert फ़ंक्शन में तीन मामलों में अंतर करने के लिए सक्रिय पैटर्न को परिभाषित कर सकते हैं। निम्नलिखित आपकी मूल डेटा संरचना के लिए है।

let (|NodeInfo|) node = (node.Prev, node.Element, node.Next) 

अधिक जानकारी के लिए, Active Patterns at MSDN देखें: यह केवल एक रिकार्ड में संग्रहीत तत्वों की एक निकालने है। फिर, insert समारोह इस प्रकार दिखाई देगा:

let insert x l = 
    match l with 
    | None -> Node({ Prev=None; Element=x; Next=None }) 
    | Node(NodeInfo(None, _, _) as node) -> 
     let new_node = { Prev=None; Element=x; Next=Node(node)} 
     node.Prev <- Node(new_node) 
     Node(new_node) 
    | Node(NodeInfo(Node(prev_node), _, _) as node) ->    
     let new_node = { Prev=node.Prev; Element=x; Next=Node(node)} 
     node.Prev <- Node(new_node) 
     prev_node.Next <- Node(new_node) 
     Node(prev_node) 

[संपादित करें] वास्तव में, एक ही बात एक रिकार्ड के तत्वों निकालने के लिए पैटर्न का उपयोग किया जा सकता है, लेकिन मुझे लगता है कि सक्रिय पैटर्न कोड थोड़ा कर सकते हैं अच्छे।

Answer 2

कारण मैं पूछ रहा हूँ है, क्योंकि मैं वापस जाने के लिए और डेटा संरचनाओं मैं एल्गोरिदम वर्ग मैं इस सेमेस्टर ले लिया में के बारे में सीखा लागू (सूचियों, टेढ़ा पेड़, संलयन पेड़, y- तेजी की कोशिश करता छोड़ना चाहते, वैन एम्डे बोस पेड़, इत्यादि), जो एक शुद्ध सिद्धांत पाठ्यक्रम था, जिसमें कोई भी कोडिंग नहीं था, और मुझे लगता है कि मैं इसे करने के दौरान भी एफ # सीखने की कोशिश कर सकता हूं।

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

इससे पहले कि मैं कुछ और अधिक महत्वपूर्ण शुरू करता हूं, क्या एफ # में इस तरह के परिवर्तनीय संरचनाओं को करने का एक बेहतर तरीका है?

आप सही लाइनों के साथ काम कर रहे हैं। यदि आप उदाहरण चाहते हैं, तो इस mutable heap implementation को ओकैम में जीन-क्रिस्टोफ फिलियाट्रे द्वारा लिखे गए देखें। सरल और कुशल परिवर्तनीय डेटा संरचनाओं के कई अन्य महान उदाहरण हैं जो ओसीएमएल में लिखे गए उनके एपीआई में कार्यात्मक प्रोग्रामिंग का उपयोग करते हैं।

क्या मुझे सिर्फ रिकॉर्ड का उपयोग करना चाहिए और भेदभाव वाले संघ से परेशान नहीं होना चाहिए?

उत्परिवर्तनीय डेटा संरचनाओं के मामले में, उनके हिस्सों को अक्सर एक सरणी में संयोजित रूप से संग्रहीत किया जाता है। यही कारण है कि वे अक्सर अपने पूरी तरह कार्यात्मक समकक्षों की तुलना में बहुत अधिक कुशल होते हैं।

क्या मुझे सी # में उत्परिवर्तनीय संरचनाएं करनी चाहिए, और एफ # में डुबकी नहीं डालना चाहिए जब तक कि मैं उन्हें अपने पूर्ण कार्यात्मक समकक्षों से तुलना नहीं करना चाहता?

संख्या एफ # का उपयोग जैसे कि यह एक विशुद्ध रूप से कार्यात्मक प्रोग्रामिंग भाषा थे न करें। अशुद्ध कार्यात्मक भाषाओं का पूरा बिंदु (और कारण वे कहीं अधिक लोकप्रिय हैं) यह है कि उत्परिवर्तन उपयोगी है और हमेशा से बचा नहीं जाना चाहिए। Arrays और हैश टेबल महान डेटा संरचनाएं हैं। आपके द्वारा सूचीबद्ध किए गए म्यूटेबल डेटा स्ट्रक्चर भी उपयोगी हो सकते हैं।