स्थानीय रूप से एक पूरी तरह कार्यात्मक पेड़ संपादन

Question

के एक पेड़ टी को परिभाषित करते हैं आसान काम - बस ई के बच्चों को अपडेट करें और हम कर चुके हैं। हालांकि, एक अपरिवर्तनीय दुनिया में पहले ई के पथ को जानना जरूरी है, फिर ई 'ई + नए बच्चे से ई' प्राप्त करें, फिर बी प्राप्त करें और फिर अंततः ए '(= टी') प्राप्त करें।

यह बोझिल है;

: आदर्श, वहाँ ई

के लिए पथ की आपूर्ति मैं इस समस्या पर हमला करने के दो संभव तरीके को देखने के बिना कुछ समारोह है कि ई और जी (और संभवतः टी) के मूल्यों को लेने के लिए और टी का उत्पादन होता है ', होगा

• माता पिता संदर्भ - इस तरह से, प्रत्येक नोड जड़ को अपने रास्ते प्राप्त करने के लिए सक्षम होगा। दो समस्याएं: दो परस्पर संदर्भ नोड्स (यानी माता-पिता < -> बच्चे) बनाना पूरी तरह कार्यात्मक भाषा में कोई समस्या है (कोई आसान समाधान?); और जब भी ई -> ई 'व्युत्पन्न होता है, ई के बच्चों के सभी को नए व्युत्पन्न होने की आवश्यकता है, क्योंकि अब वे ई के बजाय ई के पुराने मान को स्टोर करते हैं।
• ज़िप्पर - प्रत्येक नोड अपने मूल जिपर से व्युत्पन्न पर एक जिपर स्टोर करता है। पारस्परिक रूप से संदर्भित समस्या गायब हो जाता है, लेकिन अभी भी, जब ई -> ई 'प्राप्त होता है, ई के सभी' के बच्चों के ज़िपर के रूप में अच्छी तरह से प्राप्त किया जा करने की जरूरत है, क्योंकि वे अब पुराने पेड़ ई

को इंगित क्या मैं दिमाग में उचित प्रदर्शन के साथ भी संभव हूं? किसी भी इनपुट के लिए बहुत धन्यवाद!

Answer 1

एक और विकल्प, एक आलसी प्रतिस्थापन करने के आधार पर आधारित। यदि यह प्रदर्शन महत्वपूर्ण है और इसमें बहुत सारे बदलाव आएंगे, तो मैं इसका बेंचमार्किंग करने का सुझाव दूंगा।

मैंने इसे एफ # में लागू किया है, हालांकि मुझे नहीं लगता कि मैंने अपने प्रिंटिंग फ़ंक्शन को छोड़कर कुछ भी "इन्फॉर" का उपयोग किया है।

यह टेक्स्ट की एक दीवार है, मूल सिद्धांत पेड़ को आलसी रखने के लिए है, नोड को प्रतिस्थापित करने वाले फ़ंक्शन को प्रतिस्थापित करके नोड्स को प्रतिस्थापित करें।

चाल आपको किसी नोड की पहचान करने के लिए कुछ तरीका चाहिए, यह उसका स्वयं का संदर्भ/नाम नहीं है, और यह मूल्य से नहीं है। पहचान ReplacementNodes इस मामले में मैं System.Object के इस्तेमाल किया है पर duplicable होने के लिए के रूप में वे referentially प्रत्येक विशिष्ट हैं।

type TreeNode<'a> = { 
    getChildren: unit -> seq<TreeNode<'a>>; 
    value: 'a; 
    originalRefId: System.Object; //This is set when the onject is created, 
            // so we can identify any nodes that are effectivly this one 
    } 


let BasicTreeNode : 'a ->seq<TreeNode<'a>>-> TreeNode<'a> = fun nodeValue -> fun children -> 
    {value = nodeValue; originalRefId = System.Object(); getChildren = fun() -> children;} 


let rec ReplacementNode : TreeNode<'a> -> TreeNode<'a> -> TreeNode<'a> -> TreeNode<'a> = 
    fun nodeToReplace -> fun newNode -> fun baseNode -> 
     if (System.Object.ReferenceEquals(baseNode.originalRefId, nodeToReplace.originalRefId)) then 
      //If it has the same Oringal 
      newNode //replace the node 
     else 
      //Just another pass on node, tranform its children, keep orignial reference 
      {value = baseNode.value; 
      originalRefId = baseNode.originalRefId; 
      getChildren = fun() -> 
       baseNode.getChildren() |> Seq.map(ReplacementNode nodeToReplace newNode); } 


type TreeType<'a> = { 
    Print: unit -> unit; 
    ReplaceNode: TreeNode<'a> -> TreeNode<'a> -> TreeType<'a>; 
    //Put all the other tree methods, like Traversals, searches etc in this type 
    } 

let rec Tree = fun rootNode -> 
    { 
     Print = fun() -> 
      let rec printNode = fun node -> fun depth -> 
       printf "%s %A\n" (String.replicate depth " - ") node.value 
       for n in node.getChildren() do printNode n (depth + 1) 
      printNode rootNode 0 
      ; 
     ReplaceNode = fun oldNode -> fun newNode -> 
      Tree (ReplacementNode oldNode newNode rootNode) 



    } 

टेस्ट केस/उदाहरण:

let e = BasicTreeNode "E" Seq.empty 
let d = BasicTreeNode "D" Seq.empty 
let c = BasicTreeNode "C" Seq.empty 
let b = BasicTreeNode "B" [d;e] 
let a = BasicTreeNode "A" [b;c] 
let originalTree = Tree a 
printf "The Original Tree:\n" 
originalTree.Print() 

let g = BasicTreeNode "G" Seq.empty 
let newE = BasicTreeNode "E" [g] 

let newTree = originalTree.ReplaceNode e newE 
printf "\n\nThe Tree with a Local Change: \n" 
newTree.Print() 

printf "\n\nThe Original Tree is Unchanged: \n" 
originalTree.Print() 


printf "\n\nThe Tree with a Second Local Change: \n" 
let h = BasicTreeNode "H" Seq.empty 
let newC = BasicTreeNode "C" [h] 
let newTree2 = newTree.ReplaceNode c newC 
newTree2.Print() 



printf "\n\nTrying to Change a node that has been replaced doesn't work \n" 
let i = BasicTreeNode "i" Seq.empty 
let newnewC = BasicTreeNode "C" [h; i] 
let newTree3 = newTree.ReplaceNode c newC //newTree.ReplaceNode newc newnewC would work 
newTree3.Print() 

---

हम परीक्षण के अंत में देखा कि का उपयोग कर वस्तु के लिए एक पुराने नोड नाम (/ संदर्भ) प्रतिस्थापित किया जा रहा काम नहीं करता। एक और नोड के संदर्भ आईडी है कि एक नए प्रकार बनाने का विकल्प है:

//Like a basicTreeNode, but reuses an existing ID, so they can be replaced for oneanother 
let EdittedTreeNode = fun orignalNode -> fun nodeValue -> fun children -> 
    {value = nodeValue; originalRefId = orignalNode.originalRefId; getChildren = fun() -> children;} 

तुम भी, ReplacementNode परिभाषा को संपादित कर सकता है इतना है कि यह आईडी को बरकरार रखता है, नोड यह बदलता है की।