हास्केल पर दो सरल कार्य (शुरुआती के लिए)

सभी उपयोगकर्ताओं के लिए शुभकामनाएँ Habrahabr!
मैंने हाल ही में हास्केल का अध्ययन करना शुरू किया, और इसे थोड़ा महारत हासिल करने के बाद, मैंने थोड़ा संचित अनुभव साझा करने का फैसला किया। बेशक, हास्केल का ज्ञान डार्कस के रूप में उस स्तर पर नहीं है, इसलिए नीचे वर्णित दो कार्यों का उद्देश्य शुरुआती लोगों पर अधिक है, लेकिन अनुभवी उपयोगकर्ता शायद इसे ठीक कर देंगे और आपको बताएंगे कि यह कैसे बेहतर करना है। यह केवल हब्रहाब्र पर मेरा पहला लेख नहीं है, लेकिन सामान्य तौर पर मेरा पहला ट्यूटोरियल जो मैंने कभी लिखा है।

टास्क 1

N जिलों वाले शहर में, सीमा शुल्क बिंदु बनाए जाने चाहिए। लेकिन उन्हें शहर के सबसे व्यस्त इलाकों में स्थापित करने की आवश्यकता है। भरा हुआ वह क्षेत्र है जिसके माध्यम से आप गुजरते हैं यदि आप शहर ए के भाग बी से भाग में जाते हैं, अर्थात। अगर कोई चक्कर नहीं है। अगर हम शहर को एक ग्राफ के रूप में और नोड्स के रूप में क्षेत्रों की कल्पना करते हैं, तो हम एक विशेष मार्ग के लिए सभी "अड़चनों" (= अड़चनों को या "सुई की आंख") भी कहते हैं। निम्नलिखित घोषणाएँ दी गई हैं:

type District = Integer type NumOfDistricts = Integer type Route = (District, District) newtype CityMap = CM (NumOfDistricts, [Route]) --  : type Path = [District] type Bottleneck = District 

अंत में, फ़ंक्शन चालू होना चाहिए:

 bottlenecks :: CityMap -> District -> District -> [Bottleneck] 

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

मैं आपको एक उदाहरण देता हूं। मान लीजिए कि हमारे पास निम्नलिखित शहर हैं

शहर = सीएम (6, [(2,3), (1,2), (3,1), (4,3), (4,6), (5,6), (5,3)])



तब फ़ंक्शन कॉल करें

 bottlenecks city 1 6 

नोड संख्या 3 (एक नोड से मिलकर एक सरणी) वापस करना चाहिए।

शुरुआत करने के लिए, हम एक फ़ंक्शन लिखते हैं जो किसी विशेष नोड के सभी पड़ोसियों को वापस करता है।

 neighbours :: CityMap -> District -> [District] 

चूंकि प्रत्येक रूट तत्व में केवल दो तत्व होते हैं, हम बस यह जांच सकते हैं कि जोड़ी के तत्वों में से एक (पी, क्यू) वांछित (बी) तत्व है या नहीं। यदि b, p के बराबर है, तो q और इसके विपरीत जोड़ें। आप इसके लिए mapMaybe फ़ंक्शन का उपयोग कर सकते हैं।

 neighbours (CM (_,rs)) b = mapMaybe neighbour rs where neighbour (p,q) | b == p = Just q | b == q = Just p | otherwise = Nothing 

परीक्षण:

*Main Data.List> neighbours city 3
[2,1,4,5]

यह काम करता है! अब जब आप किसी भी नोड के पड़ोसियों को पा सकते हैं, तो किसी भी दो बिंदुओं के बीच का रास्ता खोजना अच्छा होगा। या बल्कि, न केवल एक मार्ग, बल्कि सभी संभव पथ:

 paths :: CityMap -> District -> District -> [Path] 

हमें उस नोड को याद रखने के लिए एल्गोरिदम के हर चरण को नहीं भूलना चाहिए जिसे हम पहले ही देख चुके हैं (अन्यथा हम सर्कल में अंतहीन रूप से चलेंगे)। शुरू से लक्ष्य तक के रास्ते खोजने के लिए एल्गोरिथ्म:

1. यदि start == लक्ष्य है, तो वापस लौटें [[प्रारंभ]]
2. यदि शुरू की गई नोड्स (= विज़िट की गई) की सरणी में मौजूद नहीं है, तो पड़ोसियों के प्रत्येक तत्व (= अगले) के लिए हम इस पड़ोसी से लक्ष्य तक का रास्ता तलाशते हैं।
3. अन्यथा वापस लौटें [] (यदि हम पहले ही शुरू हो चुके हैं)

समस्या यह है कि हमारे पथ फ़ंक्शन विज़िट किए गए नोड्स के प्रत्येक चरण पर "सेव" नहीं करते हैं। इसे पथों के उप-कार्य का उपयोग करके लागू किया जा सकता है:

 paths :: CityMap -> District-> District -> [Path] paths cm start goal = paths' [] cm start goal where paths' visited cm start goal | start == goal = [[start]] | start `notElem` visited = [start:rest | next <- neighbours cm start, rest <- paths' (start:visited) cm next goal] | otherwise = [] 

परीक्षण:

*Main Data.List> paths city 1 2
[[1,2],[1,3,2]]

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

 [1..n] \\ [start, goal] --  n -  

सभी रास्तों में उपयोग की जाने वाली संख्या का पता लगाने के लिए, हम प्रतिच्छेद फ़ंक्शन का उपयोग करेंगे, जो केवल उन तत्वों को लौटाता है जो दोनों सेटों में पाए जाते हैं। यानी आपको इस फ़ंक्शन को सभी संभावित समाधानों और सेट पथों के पहले तत्व के सेट पर लागू करने की आवश्यकता है, फिर दूसरे तत्व के उत्तर को लागू करें, आदि। उत्तर इस प्रकार लिखा जा सकता है:

((((([1..n] \\ [start, goal]) intersect paths[0]) intersect paths[1]) intersect paths[2]) intersect...)

फिर, बाधाओं को एक पंक्ति में लिखा जा सकता है:

 bottlenecks :: CityMap -> District -> District -> [Bottleneck] bottlenecks cm@(CM (n,_)) start goal = foldl intersect ([1..n] \\ [start, goal]) $ (paths cm start goal) 

Data.Maybe (mapMaybe के लिए) और Data.List (प्रतिच्छेद के लिए) मॉड्यूल आयात करना याद रखें।

टास्क २

हम एक समान समस्या पर विचार करते हैं, अर्थात्, Erdös संख्या की समस्या। मैं संक्षेप में बताऊंगा कि यह क्या है: गणितज्ञ पॉल एर्दो के साथ एक वैज्ञानिक लेख लिखने वाले सभी को नंबर 1 मिलता है, उन सभी ने जो सह-लेखक पॉल एर्दो के साथ एक वैज्ञानिक लेख लिखा था (लेकिन उनके साथ नहीं) नंबर 2 प्राप्त करते हैं, आदि। अर्थात, Erdös नंबर n वाले लोगों के सह-लेखक के पास Erdös नंबर n + 1 है। कार्य एक विशिष्ट व्यक्ति के लिए यह संख्या ढूंढना है (यदि इस व्यक्ति और एर्दो के बीच संबंध नहीं पाया जा सकता है, तो नंबर -1 प्रिंट करें)। तो, शुरू करने के लिए, हम उन डेटा के प्रकारों को निर्धारित करेंगे, जिनके साथ हम काम करेंगे - ये वैज्ञानिक हैं (एक वैज्ञानिक में एक प्रारंभिक और एक उपनाम होता है), वे लेखक भी हैं, साथ ही प्रत्येक तत्व का एक डेटाबेस जिसमें लेख का शीर्षक (वैज्ञानिक कार्य) और लेखकों के नाम हैं जिन्होंने इसे प्रकाशित किया है । हम उस डेटाबेस को भी घोषित करेंगे जिसका उपयोग हम परीक्षण के लिए करेंगे:

 type ErdosNumber = Int data Scientist = Sc Initial SurName type Initial = Char type SurName = String type Author = Scientist newtype Database = Db [([Author],PaperTitle)] type PaperTitle = String type Path = [Author] db = Db [([Sc 'M' "Smith",Sc 'G' "Martin",Sc 'P' "Erdos"],"Newtonian Forms of Prime Factors"), ([Sc 'P' "Erdos",Sc 'W' "Reisig"],"Stuttering in Petri Nets"), ([Sc 'M' "Smith",Sc 'X' "Chen"],"First Order Derivates in Structured Programming"), ([Sc 'T' "Jablonski",Sc 'Z' "Hsueh"],"Selfstabilizing Data Structures"), ([Sc 'X' "Chen",Sc 'L' "Li"],"Prime Numbers and Beyond")] 

आइए पिछले कार्य के रूप में शुरू करते हैं एक फ़ंक्शन लिखकर जो सभी पड़ोसियों को परिभाषित करता है (यानी जो इस लेखक के सीधे संपर्क में हैं):

 neighbours :: Database -> Author -> [Author] 

पिछले कार्य के विपरीत, हमारे डेटाबेस में प्रत्येक डेटाबेस तत्व में दो प्रकार के लेखक शामिल हो सकते हैं, इसलिए मैपमेब फ़ंक्शन अपरिहार्य है। प्रत्येक डेटाबेस आइटम ([लेखक], पेपरटेल) के लिए हम जाँचेंगे कि क्या लेखक, जिनके पड़ोसी हम खोजने की कोशिश कर रहे हैं, [लेखक] सरणी में प्रवेश करते हैं, यदि ऐसा है, तो पूरे [लेखक] सरणी को ले लें, यदि नहीं, तो अगले तत्व पर जाएं डेटाबेस। अंत में, उस लेखक का नाम हटाना आवश्यक होगा जिसे हम परिणामी सूची से ढूंढ रहे थे (हम उसके पड़ोसियों की तलाश कर रहे हैं, इसलिए हमें उसकी आवश्यकता नहीं है):

 neighbours :: Database -> Author -> [Author] neighbours (Db []) _ = [] neighbours (Db ((a,_):xs)) (Sc is) = filter (/= (Sc is)) ((neighbour a) ++ (neighbours (Db xs) (Sc is))) where neighbour a | (Sc is) `elem` a = a | otherwise = [] 

यह घोषित करना न भूलें कि हम अपने वैज्ञानिकों की तुलना कैसे करेंगे:

 instance Eq Scientist where (Sc i1 s1) == (Sc i2 s2) = (i1 == i2) && (s1 == s2) 

अब हम "प्रारंभ" के लेखक से लेकर वैज्ञानिक (Sc 'P' "Erdos") तक सभी संभव तरीकों की तलाश करेंगे। पथ फ़ंक्शन व्यावहारिक रूप से कोई भिन्न नहीं है जो हमने पहले ही लिखा था:

 paths :: Database -> Author -> [Path] paths db start = paths' [] db start where paths' visited db start | start == (Sc 'P' "Erdos") = [[start]] | start `notElem` visited = [start:rest | next <- neighbours db start, rest <- paths' (start:visited) db next] | otherwise = [] 

लेखक से Erdös तक सभी संभावित रास्तों की एक सरणी होने से, आप लंबाई फ़ंक्शन का उपयोग करके प्रत्येक पथ को उसकी लंबाई में बदल सकते हैं (यानी, हमें एक ऐसा सरणी मिलता है जिसमें प्रत्येक पथ की लंबाई होती है)। परिणामी सरणी से, न्यूनतम संख्या (= सबसे छोटा पथ) चुनें और इस संख्या में से एक घटाएं, क्योंकि Erdös की संख्या स्वयं 0. है इससे पहले कि हम भूल जाएं, जांचें कि क्या कोई रास्ता है जो Erdös की ओर जाता है (यदि नहीं, तो -1 वापस करें):

 erdosNum :: Database -> Scientist -> ErdosNumber erdosNum db sc | length (paths db sc) == 0 = (-1) | otherwise = (-) (minimum (map length (paths db sc))) 1 

प्रोग्रामिंग में गुड लक!