मैं हास्केल में ऑब्जेक्ट्स के पेड़ को पॉइंटर्स के साथ माता-पिता और बच्चों को कैसे कोड करूं?

मुझे निम्न समस्या मिली है: मेरे पास विभिन्न वर्गों की वस्तुओं का पेड़ है जहां बाल वर्ग में कोई कार्रवाई माता-पिता को अमान्य करती है। अनिवार्य भाषाओं में, यह करने के लिए तुच्छ है। उदाहरण के लिए, जावा में:मैं हास्केल में ऑब्जेक्ट्स के पेड़ को पॉइंटर्स के साथ माता-पिता और बच्चों को कैसे कोड करूं?

public class A { 
    private List<B> m_children = new LinkedList<B>(); 
    private boolean m_valid = true; 

    public void invalidate() { 
     m_valid = false; 
    } 

    public void addChild(B child) { 
     m_children.add(child); 
     child.m_parent = this; 
    } 
} 

public class B { 
    public A m_parent = null; 
    private int m_data = 0; 

    public void setData(int data) { 
     m_data = 0; 
     m_parent.invalidate(); 
    } 
} 

public class Main { 
    public static void main(String[] args) { 
     A a = new A(); 
     B b = new B(); 
     b.setData(0); //invalidates A 
    } 
}

मैं उपरोक्त हास्केल में कैसे कर सकता हूं? मैं इसके चारों ओर अपने दिमाग को लपेट नहीं सकता, क्योंकि एक बार जब मैं हास्केल में ऑब्जेक्ट बनाता हूं, तो इसे बदला नहीं जा सकता है।

यदि संबंधित हास्केल कोड पोस्ट किया गया है तो मैं बहुत अधिक बाध्य होगा।

संपादित करें:

मैं गए एप्लिकेशन है कि दस्तावेजों को संपादित करता है: समस्या मैं हल करने के लिए कोशिश कर रहा हूँ निम्नलिखित है। एक दस्तावेज वस्तुओं का एक पदानुक्रम है। जब बच्चों की वस्तुओं के गुण संशोधित होते हैं, तो दस्तावेज़ को अमान्य स्थिति पर सेट करने की आवश्यकता होती है, ताकि उपयोगकर्ता जानता है कि दस्तावेज़ को सत्यापित करने की आवश्यकता है।

स्रोत

2010-06-07 axilmar

sepp2k और Tal Pressman के उत्तरों को जोड़ने के लिए, आप शुद्ध कार्यात्मक दुनिया से बचकर और 'एसटी' या 'आईओ' मोनैड का उपयोग करके, चीजों को करने के जावा तरीके की नकल करने के लिए हास्केल कोड भी लिख सकते हैं। "परिवर्तनीय" पॉइंटर्स के लिए 'एसटीआरआईफ़' का उपयोग करना। – yairchu

दिलचस्प। यह कैसे काम करता है? क्या कंपाइलर एसटीआरआईफ़ को विशेष निर्माण के रूप में मानता है? और एसटीआरआईफ़ और आईओआरएफ के बीच अंतर क्या हैं? मैंने इसे गुमराह किया है लेकिन मैं समझने में आसान कुछ नहीं आया था। – axilmar

मुझे हास्केल के साथ बहुत अधिक अनुभव नहीं है, लेकिन जहां तक मुझे पता है कि शुद्ध कार्यात्मक भाषाओं में संदर्भ ग्राफ में मंडलियों को रखना संभव नहीं है। इसका मतलब है कि:

आप अपने माता-पिता की ओर इशारा करते पेड़ों में एक 2 तरह सूचियों, बच्चे नहीं कर सकते हैं, आदि *
यह आम तौर पर सिर्फ एक नोड को बदलने के लिए पर्याप्त नहीं है। किसी भी नोड को बदले जाने वाले प्रत्येक नोड में डेटा संरचनाओं के "रूट" से शुरू होने वाले प्रत्येक नोड में परिवर्तन की आवश्यकता होती है जिसे आप बदलना चाहते हैं।

नीचे की रेखा है, मैं जावा (या कोई अन्य अनिवार्य भाषा) एल्गोरिदम लेने की कोशिश नहीं करता और इसे हास्केल में बदलने की कोशिश करता हूं। इसके बजाय, समस्या को हल करने के लिए एक अधिक कार्यात्मक एल्गोरिदम (और यहां तक कि एक अलग डेटा संरचना) खोजने का प्रयास करें।

संपादित करें:

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

आशा है कि समझ में आया। : एस

* जैसा कि जेबेरमैन द्वारा टिप्पणियों में बताया गया है और अन्य उत्तरों में, आलसी में आलसी मूल्यांकन का उपयोग करके परिपत्र संदर्भ ग्राफ बनाना संभव है।

स्रोत

2010-06-07 15:23:33

असल में यह सच नहीं है। हैकेल आलस्य में हमें अपने आप के संदर्भ में डेटा संरचना को परिभाषित करने की अनुमति मिलती है, यहां तक कि बहुत ही जटिल तरीकों से (Google "गाँठ बांधना")। तो एक दोगुनी लिंक्ड सूची कोई समस्या नहीं है। लेकिन जब आप सूची तत्वों में से किसी एक को संशोधित करने का प्रयास करते हैं तो आपको परेशानी होती है :) – jberryman

हम्म, जानना अच्छा है। मैं इसे ठीक करने के लिए अपना जवाब संपादित करूंगा। –

अपने शीर्षक में प्रश्न का उत्तर देने के लिए: हाँ, आप नोड्स बना सकते हैं जिनके माता-पिता और उनके बच्चों के साथ संबंध हैं। उदाहरण:

--    parent  children 
data Tree = Node (Maybe Tree) [Tree] 
root = Node Nothing [a,b] -- I can "forward reference" a and b because haskell is lazy 
a = Node (Just root) [] 
b = Node (Just root) []

प्रश्न यह है कि यह आपके विशेष उपयोग-मामले (अक्सर बार नहीं है) के लिए उपयोगी है या नहीं।

अब आपके शरीर में सवाल: आप सही हैं, आप इसे बनाए जाने के बाद एक मूल्य नहीं बदल सकते हैं।तो एक बार आपके पास एक वैध पेड़ हो जाने के बाद, आपके पास हमेशा एक वैध पेड़ होगा जब तक कि वेरिएबल संदर्भित करता है कि पेड़ गुंजाइश में है।

आपने वास्तव में वर्णन नहीं किया कि आप किस समस्या को हल करने की कोशिश कर रहे हैं, इसलिए मैं आपको यह नहीं बता सकता कि आप क्या करने की कोशिश कर रहे हैं, लेकिन मुझे यकीन है कि पेड़ को म्यूट किए बिना एक तरीका है ।

स्रोत

2010-06-07 15:28:05 sepp2k

जिस समस्या को मैं हल करने का प्रयास कर रहा हूं वह निम्न है: मेरे पास एक ऐसा एप्लिकेशन है जो दस्तावेजों को संपादित करता है। एक दस्तावेज वस्तुओं का एक पदानुक्रम है। जब बच्चों की वस्तुओं के गुण संशोधित होते हैं, तो दस्तावेज़ को अमान्य स्थिति पर सेट करने की आवश्यकता होती है, ताकि उपयोगकर्ता जानता है कि दस्तावेज़ को सत्यापित करने की आवश्यकता है। – axilmar

Maybe प्रकार के Functor उदाहरण का उपयोग करने में देखें।

उदाहरण के लिए, शायद आपकी समस्या इस तरह कुछ है: आप एक तत्व को बाइनरी पेड़ में डालना चाहते हैं, लेकिन केवल यदि यह पहले से मौजूद नहीं है। तुम कर सकते हो ऐसा ही कुछ के साथ:

data Tree a = Node a (Tree a) (Tree a) 
      | Tip 

maybeInsert :: a -> Tree a -> Maybe (Tree a) 
maybeInsert a Tip = Just $ Node a Tip Tip 
maybeInsert a (Node a' l r) 
    | a == a' = Nothing 
    | a < a' = fmap (\l'-> Node a' l' r) (maybeInsert a l) 
    | a > a' = fmap (\r'-> Node a' l r') (maybeInsert a r)

तो समारोह Nothing वापस आ जाएगी अगर हम तत्व पाया पहले से मौजूद हो, या तत्व डाला साथ Just नया पेड़ वापस जाने के लिए।

उम्मीद है कि जो भी आप करने की कोशिश कर रहे हैं उससे प्रासंगिक है।

स्रोत

2010-06-07 15:57:55 jberryman

एक पेड़ को संशोधित करने के लिए जो रूट और पीठ के रास्ते पर लगातार भ्रमण की आवश्यकता हो सकती है, ह्यूसेट द्वारा मूल पेपर की शब्दावली में "निशान" के साथ जिपर डेटा संरचना के एक संस्करण के लिए सही नौकरी की तरह लगता है; पेपर से कोड नमूने भी "यादगार जिपर" का नाम सुझाते हैं। बेशक, कुछ देखभाल के साथ, एक नियमित जिपर का भी उपयोग किया जा सकता है, लेकिन उन्नत संस्करण अधिक सुविधाजनक और/या उपयोग करने में सक्षम हो सकता है।

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

यहां पेपर का एक लिंक है: Gérard Huet, Functional Pearl: The Zipper। यह केवल छः पृष्ठ हैं, लेकिन इसमें निहित विचार किसी भी कार्यात्मक प्रोग्रामर के लिए बहुत उपयोगी हैं।

स्रोत

2010-06-07 16:01:15

हैकेल में ज़िप्पर पर एक लेख http://scienceblogs.com/goodmath/2010/01/zippers_making_functional_upda.php – stonemetal

दस्तावेज़ के लिए धन्यवाद, मैंने पहले जिपर संरचना के बारे में पढ़ा है। मुझे समझ में नहीं आता कि मेरे कार्यक्रम में इसका उपयोग कैसे किया जाए, हालांकि काम के लिए। उदाहरण के लिए, "अमान्य" संपत्ति सेट के साथ बच्चे को नया माता-पिता सेट करना और सेट करना संभव नहीं है, क्योंकि अमान्यता सभी बच्चों के लिए मान्य होना चाहिए। यदि मैं जिपर संरचना का उपयोग करता हूं, तो मुझे सभी बच्चों के लिए मूल वस्तु को बदलना होगा, और चूंकि मेरा पेड़ 6 परतों को गहरा है, यह परिवर्तन रूट ऑब्जेक्ट पर फिसल जाएगा। – axilmar

एक और समस्या भी है: मैं समझता हूं कि दिए गए कार्यों ("go_up", "go_left" आदि) का उपयोग कैसे करें, और मैं जिपर की अवधारणा को भी समझता हूं (अनिवार्य रूप से स्थानीय तर्कों को विनाशकारी रूप से अद्यतन चर के रूप में उपयोग करता हूं), लेकिन मैं नहीं करता यह समझ में नहीं आता कि इसे बाकी कार्यक्रम के साथ कैसे जोड़ना है। मान लीजिए कि मैं 'go_up' फ़ंक्शन का उपयोग करता हूं। मैं परिणाम कहां स्टोर करूं? क्या मैं इसे एक सूची में स्टोर करता हूं? और यदि हां, तो मैं सूची कहां स्टोर करूं? क्या मुझे एक रिकॉर्ड बनाना चाहिए जिसमें जिपर संरचना के डेटा की तरह सभी 'वर्तमान डेटा' शामिल हो? इस के लिए किसी भी समाधान की सराहना की। – axilmar

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

import Data.Maybe (fromJust) 
import Data.Tree 
import Data.Tree.Zipper 

type NodeData = Either Bool Int 
type TreePath a = [TreePos Full a -> TreePos Full a] 

firstChild' = fromJust . firstChild 
parent'  = fromJust . parent 
prev'  = fromJust . prev 
next'  = fromJust . next 

-- Determine the path from the root of the tree to the cursor. 
pathToMe :: TreePos Full NodeData -> TreePath NodeData 
pathToMe t | isRoot t = [] 
      | isFirst t = firstChild' : pathToMe (parent' t) 
      | otherwise = next' : pathToMe (prev' t) 

-- Mark a tree as invalid, but leave the cursor in the same place. 
invalidate :: TreePos Full NodeData -> TreePos Full NodeData 
invalidate t = foldr ($) (setLabel (Left False) (root t)) (pathToMe t) 

-- Set a node's internal data. 
setData :: Int -> TreePos Full NodeData -> TreePos Full NodeData 
setData = (invalidate .) . setLabel . Right 

main = let tree1 = Node (Left True) [Node (Right 1) [], Node (Right 2) []] 
      Just cursor = firstChild (fromTree tree1) 
      tree2 = setData 3 cursor 
     in do putStrLn (drawTree (fmap show tree1)) 
      putStrLn (drawTree (fmap show (toTree tree2))) 
      putStrLn $ "Cursor at "++show (label tree2)

आउटपुट:

Left True 
| 
+- Right 1 
| 
`- Right 2 

Left False 
| 
+- Right 3 
| 
`- Right 2 

Cursor at Right 3

स्रोत

2010-06-07 16:52:36 Anthony

धन्यवाद। जो मैं समझता हूं, उपर्युक्त कोड निम्नलिखित करता है: 1) मुख्य में एक पेड़ बनाता है। 2) एक कर्सर प्राप्त करके एक बच्चा हो जाता है। 3) डेटा सेट करता है, पेड़ को अमान्य करता है और एक नया रूट पेड़ देता है। अमान्यता इस प्रकार होती है: नए वैध ध्वज और शेष पेड़ से एक नया रूट नोड बनाया जाता है। क्या मैंने ऊपर से सही ढंग से समझ लिया है? – axilmar

यह सही है, सेट की गई चेतावनी के साथ, जो आपको केवल नए पेड़ की जड़ नहीं देता है, लेकिन कर्सर के साथ एक नया पेड़ मूल पेड़ में उसी स्थान पर सेट होता है (ताकि आप बाद में स्थानीय परिवर्तन जारी रख सकें) । – Anthony

एक और नोट यह है कि रूट को पहले से ही अमान्य होने पर पेड़ को पुनर्निर्माण न करके इस कोड को और अधिक कुशल बनाया जा सकता है। – Anthony

आलस्य यकीन है कि मान्यता भी अक्सर ऐसा नहीं होता है बनाने की देखभाल नहीं कर सकता है? इस तरह, आपको m_valid फ़ील्ड को स्टोर करने की आवश्यकता नहीं है।

उदाहरण के लिए, यदि आप केवल सहेजने पर मान्य हैं, तो आप ऑब्जेक्ट को अपने दिल की सामग्री में संपादित कर सकते हैं, हर समय पुन: वैध किए बिना; केवल जब उपयोगकर्ता 'सहेजें' बटन दबाता है तो validateDoc गणना का मान होता है। चूंकि मुझे यह सुनिश्चित करने के लिए पता नहीं है कि वैध साधनों की आपकी धारणा क्या है और इसके लिए आपको क्या चाहिए, मैं पूरी तरह से निशान का हो सकता हूं।

अपरीक्षित & अधूरा कोड:

data Document = Document { subDocs :: [SubDoc] } 
data SubDoc = SubDoc { content :: String } 

addSubDoc :: SubDoc -> (Document -> Document) 
addSubDoc = error "not yet implemented: addSubDoc" 

modifySubDoc :: Int -> (SubDoc -> SubDoc) -> (Document -> Document) 
modifySubDoc = error "not yet implemented: modifySubDoc" 


validateDoc :: Document -> Bool 
validateDoc = all validateSubDoc . subDocs 

validateSubDoc :: SubDoc -> Bool 
validateSubDoc = not . null . contents

मैं दस्तावेज़ के समग्र वैधता संभालने कर रहा हूँ केवल सहायक दस्तावेज़ों (सुनिश्चित करना है कि वे एक गैर खाली स्ट्रिंग शामिल द्वारा यहां नकली) पर निर्भर करता है।

वैसे, मुझे लगता है कि आप a.addChild(b);main में भूल गए हैं।

स्रोत

2010-06-08 10:56:33 yatima2975

मान्य दस्तावेज़ का अर्थ है कि यह एक निश्चित परीक्षण पास करता है। यहां विचार यह है कि उपयोगकर्ता दस्तावेज़ संपादित करता है, फिर उसे मान्य करता है। – axilmar

मैं हास्केल में ऑब्जेक्ट्स के पेड़ को पॉइंटर्स के साथ माता-पिता और बच्चों को कैसे कोड करूं?

उत्तर

संबंधित मुद्दे