मैं एक कार्यात्मक प्रोग्रामिंग भाषा में ग्राफ और ग्राफ एल्गोरिदम कैसे कार्यान्वित करूं?

Question

असल में, मुझे पता है कि ग्राफ डेटा संरचनाओं को कैसे बनाया जाए और प्रोग्रामिंग भाषाओं में डिजस्ट्रा के एल्गोरिदम का उपयोग करें जहां साइड इफेक्ट्स की अनुमति है। आम तौर पर, ग्राफ एल्गोरिदम कुछ नोड्स को 'विज़िट' के रूप में चिह्नित करने के लिए संरचना का उपयोग करते हैं, लेकिन इसके दुष्प्रभाव होते हैं, जिन्हें मैं टालने का प्रयास कर रहा हूं।

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

Answer 1

आप देख सकते हैं कि मार्टिन एर्विग के हास्केल functional graph library चीजें कैसे करता है। उदाहरण के लिए, इसके shortest-path functions सभी शुद्ध हैं, और आप इसे लागू करने के लिए source code देख सकते हैं।

एक और विकल्प, like fmark mentioned, एक अमूर्तता का उपयोग करना है जो आपको राज्य के संदर्भ में शुद्ध कार्यों को लागू करने की अनुमति देता है। उन्होंने राज्य मोनड का उल्लेख किया है (जो lazy और strict किस्मों दोनों में उपलब्ध है)। एक अन्य विकल्प, यदि आप जीएचसी हास्केल कंपाइलर/दुभाषिया (या, मुझे लगता है कि, किसी भी हास्केल कार्यान्वयन जो रैंक -2 प्रकारों का समर्थन करता है) में काम कर रहा है, तो दूसरा विकल्प the ST monad है, जो आपको शुद्ध कार्यों को लिखने की अनुमति देता है जो आंतरिक रूप से परिवर्तनीय चर के साथ सौदा करते हैं ।

Answer 2

अधिकांश कार्यात्मक भाषाएं आंतरिक कार्यों का समर्थन करती हैं। तो आप बाहरी परत में अपना ग्राफ प्रतिनिधित्व बना सकते हैं और इसे केवल आंतरिक फ़ंक्शन से संदर्भित कर सकते हैं।

इस किताब को इसे बड़े पैमाने पर http://www.amazon.com/gp/product/0262510871/ref=pd_lpo_k2_dp_sr_1?ie=UTF8&cloe_id=aa7c71b1-f0f7-4fca-8003-525e801b8d46&attrMsgId=LPWidget-A1&pf_rd_p=486539851&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0262011530&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=114DJE8K5BG75B86E1QS

Answer 3

मैं वास्तव में कुछ चालाक तकनीक के बारे में जानकर बहुत खुशी होगी शामिल किया गया है, लेकिन मुझे लगता है कि वहाँ दो बुनियादी दृष्टिकोण हैं:

1. कुछ वैश्विक स्थिति ऑब्जेक्ट को संशोधित करें। यानी साइड इफेक्ट्स
2. ग्राफ़ को संशोधित ग्राफ के रूप में वापसी मान के साथ अपने कार्यों के लिए एक तर्क के रूप में पास करें। मुझे लगता है कि यह "राज्य की बड़ी मात्रा में गुजरने" का आपका दृष्टिकोण है

यह कार्यात्मक प्रोग्रामिंग में किया गया है। यदि कंपाइलर/दुभाषिया कोई अच्छा है, तो यह आपके लिए स्मृति प्रबंधित करने में मदद करेगा। विशेष रूप से, आप यह सुनिश्चित करना चाहते हैं कि यदि आप अपने किसी भी फ़ंक्शन में रिकर्स करते हैं तो आप पूंछ रिकर्सन का उपयोग करते हैं।

Answer 4

आप Haskell का उपयोग कर रहे थे, तो केवल कार्यात्मक भाषा जिसके साथ मैं परिचित हूँ, मैं State monad का उपयोग कर की सिफारिश करेंगे। राज्य मोनैड एक ऐसे कार्य के लिए एक अमूर्त है जो एक राज्य लेता है और एक मध्यवर्ती मूल्य और कुछ नया राज्य मूल्य देता है। यह उन स्थितियों के लिए considered idiomatic haskell है जहां एक बड़ा राज्य बनाए रखना जरूरी है।

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

Answer 5

मैं बस सेट के रूप में विज़िट सेट रखता हूं और इसे पैरामीटर के रूप में पास करता हूं। किसी ऑर्डर किए गए प्रकार और पूर्णांक के अतिरिक्त-कुशल सेट के सेट के कुशल लॉग-टाइम कार्यान्वयन हैं।

ग्राफ का प्रतिनिधित्व करने के लिए मैं आसन्नता सूचियों का उपयोग करता हूं, या मैं एक सीमित नक्शा का उपयोग करूंगा जो प्रत्येक नोड को अपने उत्तराधिकारी की सूची में मैप करता है। यह निर्भर करता है कि मैं क्या करना चाहता हूं।

एबेलसन और सुस्मान की बजाय, मैं क्रिस ओकासाकी के Purely Functional Data Structures की सलाह देता हूं। मैंने क्रिस के शोध प्रबंध से जुड़ा हुआ है, लेकिन यदि आपके पास पैसा है, तो उसने इसे excellent book में विस्तारित किया।

---

बस grins के लिए, यहाँ एक थोड़ा डरावना रिवर्स क्रंमोत्तर गहराई-प्रथम हास्केल में निरंतरता-गुजर शैली में किया खोज है। यह सीधे Hoopl अनुकूलक पुस्तकालय से बाहर है:

postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e) 
          => LabelMap (block C C) -> e -> LabelSet -> [block C C] 
postorder_dfs_from_except blocks b visited = 
vchildren (get_children b) (\acc _visited -> acc) [] visited 
where 
    vnode :: block C C -> ([block C C] -> LabelSet -> a) 
         -> ([block C C] -> LabelSet -> a) 
    vnode block cont acc visited = 
     if setMember id visited then 
      cont acc visited 
     else 
      let cont' acc visited = cont (block:acc) visited in 
      vchildren (get_children block) cont' acc (setInsert id  visited) 
     where id = entryLabel block 
    vchildren bs cont acc visited = next bs acc visited 
     where next children acc visited = 
       case children of []  -> cont acc visited 
           (b:bs) -> vnode b (next bs) acc  visited 
    get_children block = foldr add_id [] $ targetLabels bloc 
    add_id id rst = case lookupFact id blocks of 
         Just b -> b : rst 
         Nothing -> rst 

Answer 6

यहाँ एक स्विफ्ट उदाहरण है। आपको यह थोड़ा और अधिक पठनीय मिल सकता है। सुपर क्रिप्टिक हास्केल उदाहरणों के विपरीत, चर वास्तव में वर्णित रूप से नामित हैं।

https://github.com/gistya/Functional-Swift-Graph