गेल्या उन्हाळ्यात मी भाग घेतला कोड समर ऑफ कोड - Google वरील विद्यार्थ्यांसाठी एक कार्यक्रम. दरवर्षी, आयोजक अनेक मुक्त स्रोत प्रकल्प निवडतात, ज्यात अशा सुप्रसिद्ध संस्थांचा समावेश आहे Boost.org и लिनक्स फाऊंडेशन. Google जगभरातील विद्यार्थ्यांना या प्रकल्पांवर काम करण्यासाठी आमंत्रित करते. 

Google समर ऑफ कोड 2019 मध्ये सहभागी म्हणून, मी लायब्ररीमध्ये एक प्रकल्प केला अल्गा संस्थेसह Haskell.org, जी हास्केल भाषा विकसित करत आहे - सर्वात प्रसिद्ध कार्यात्मक प्रोग्रामिंग भाषांपैकी एक. अल्गा एक लायब्ररी आहे जे प्रतिनिधित्व करते सुरक्षित टाइप करा हास्केलमधील आलेखांचे प्रतिनिधित्व. हे वापरले जाते, उदाहरणार्थ, मध्ये अर्थपूर्ण — एक गिथब लायब्ररी जी कोडवर आधारित सिमेंटिक ट्री, कॉल आणि अवलंबित्व आलेख तयार करते आणि त्यांची तुलना करू शकते. माझा प्रकल्प द्विपक्षीय आलेख आणि त्या प्रतिनिधित्वासाठी अल्गोरिदमसाठी एक प्रकार-सुरक्षित प्रतिनिधित्व जोडण्याचा होता. 

या पोस्टमध्ये मी हॅस्केलमधील द्विपक्षीयतेसाठी आलेख तपासण्यासाठी अल्गोरिदमच्या माझ्या अंमलबजावणीबद्दल बोलेन. जरी अल्गोरिदम हे सर्वात मूलभूत असले तरी, कार्यात्मक शैलीमध्ये ते सुंदरपणे अंमलात आणण्यासाठी मला अनेक पुनरावृत्ती झाली आणि खूप काम करावे लागले. परिणामी, मी मोनाड ट्रान्सफॉर्मरसह अंमलबजावणीवर स्थायिक झालो. 

माझ्याबद्दल

माझे नाव वसिली अल्फेरोव्ह आहे, मी सेंट पीटर्सबर्ग एचएसई येथे चौथ्या वर्षाचा विद्यार्थी आहे. यापूर्वी मी ब्लॉगमध्ये लिहिले होते पॅरामीटराइज्ड अल्गोरिदम बद्दल माझ्या प्रकल्पाबद्दल и झुरीहॅकच्या सहलीबद्दल. सध्या मी इंटर्नशिपवर आहे बर्गन विद्यापीठ नॉर्वेमध्ये, जिथे मी समस्येच्या दृष्टिकोनावर काम करत आहे सूची रंग. माझ्या स्वारस्यांमध्ये पॅरामीटराइज्ड अल्गोरिदम आणि कार्यात्मक प्रोग्रामिंग समाविष्ट आहे.

अल्गोरिदमच्या अंमलबजावणीबद्दल

प्रस्तावना

कार्यक्रमात सहभागी होणाऱ्या विद्यार्थ्यांना ब्लॉगसाठी जोरदार प्रोत्साहन दिले जाते. त्यांनी मला ब्लॉगसाठी व्यासपीठ उपलब्ध करून दिले हॅस्केलचा उन्हाळा. हा लेख अनुवाद आहे लेख, मी तिथे जुलैमध्ये इंग्रजीत लिहिले होते, एका छोट्या प्रस्तावनेसह. 

प्रश्नातील कोड असलेली पुल विनंती आढळू शकते येथे.

तुम्ही माझ्या कामाच्या परिणामांबद्दल वाचू शकता (इंग्रजीमध्ये) येथे.

या पोस्टचा उद्देश वाचकांना फंक्शनल प्रोग्रामिंगमधील मूलभूत संकल्पनांसह परिचित करण्यासाठी आहे, जरी वेळ येईल तेव्हा मी वापरलेल्या सर्व संज्ञा आठवण्याचा प्रयत्न करेन.

द्विपक्षीयतेसाठी आलेख तपासत आहे 

द्विपक्षीयतेसाठी आलेख तपासण्यासाठी एक अल्गोरिदम सामान्यतः अल्गोरिदमच्या कोर्समध्ये सर्वात सोपा आलेख अल्गोरिदम म्हणून दिला जातो. त्याची कल्पना सरळ आहे: प्रथम आपण डाव्या किंवा उजव्या भागामध्ये शिरोबिंदू ठेवतो आणि जेव्हा विरोधाभासी किनार आढळते, तेव्हा आम्ही ठामपणे सांगतो की आलेख द्विपक्षीय नाही.

थोडे अधिक तपशील: प्रथम आपण डाव्या शेअरमध्ये काही शिरोबिंदू ठेवतो. अर्थात, या शिरोबिंदूचे सर्व शेजारी उजव्या लोबमध्ये असले पाहिजेत. पुढे, या शिरोबिंदूच्या शेजाऱ्यांचे सर्व शेजारी डाव्या लोबमध्ये पडलेले असणे आवश्यक आहे, आणि असेच. आम्ही शिरोबिंदूंना समभाग नियुक्त करणे सुरू ठेवतो जोपर्यंत आम्ही सुरू केलेल्या शिरोबिंदूच्या कनेक्ट केलेल्या घटकामध्ये अद्याप शिरोबिंदू आहेत ज्यासाठी आम्ही शेजाऱ्यांना नियुक्त केलेले नाही. त्यानंतर आम्ही सर्व कनेक्ट केलेल्या घटकांसाठी ही क्रिया पुन्हा करतो.

जर समान विभाजनामध्ये शिरोबिंदूंमध्ये एक धार असेल तर, आलेखामध्ये विषम चक्र शोधणे कठीण नाही, जे द्विपक्षीय आलेखामध्ये व्यापकपणे ज्ञात (आणि अगदी स्पष्टपणे) अशक्य आहे. अन्यथा, आमच्याकडे योग्य विभाजन आहे, याचा अर्थ आलेख द्विपक्षीय आहे.

सामान्यतः, हे अल्गोरिदम वापरून लागू केले जाते रुंदी प्रथम शोध किंवा खोली प्रथम शोध. अत्यावश्यक भाषांमध्ये, खोली-प्रथम शोध सहसा वापरला जातो कारण तो थोडासा सोपा असतो आणि अतिरिक्त डेटा संरचनांची आवश्यकता नसते. मी खोली-प्रथम शोध देखील निवडला कारण तो अधिक पारंपारिक आहे.

अशा प्रकारे, आम्ही खालील योजनेवर आलो. आम्ही गहराई-प्रथम शोध वापरून आलेखाचे शिरोबिंदू पार करतो आणि त्यांना शेअर्स नियुक्त करतो, जसजसे आम्ही काठावर जातो तसतसे शेअरची संख्या बदलते. जर आम्ही एखाद्या शिरोबिंदूला शेअर नियुक्त करण्याचा प्रयत्न केला ज्यामध्ये आधीपासून एक शेअर नियुक्त केला आहे, तर आम्ही सुरक्षितपणे म्हणू शकतो की आलेख द्विपक्षीय नाही. ज्या क्षणी सर्व शिरोबिंदूंना एक वाटा दिला जातो आणि आम्ही सर्व कडा पाहिल्या, तेव्हा आमच्याकडे एक चांगले विभाजन आहे.

गणनेची शुद्धता

Haskell मध्ये आम्ही सर्व गणना आहेत असे गृहीत धरतो स्वच्छ. तथापि, जर हे खरोखरच घडले असते, तर आमच्याकडे स्क्रीनवर काहीही मुद्रित करण्याचा कोणताही मार्ग नसता. अजिबात, स्वच्छ गणना इतकी आळशी आहे की एकही नाही स्वच्छ काहीतरी मोजण्याची कारणे. प्रोग्राममध्ये होणारी सर्व गणना कशीतरी सक्ती केली जाते "अशुद्ध" मोनाड आयओ.

मोनाड्स हे गणनेचे प्रतिनिधित्व करण्याचा एक मार्ग आहे परिणाम Haskell मध्ये. ते कसे कार्य करतात हे स्पष्ट करणे या पोस्टच्या व्याप्तीच्या पलीकडे आहे. इंग्रजीमध्ये चांगले आणि स्पष्ट वर्णन वाचता येते येथे.

येथे मला सूचित करायचे आहे की IO सारख्या काही मोनाड्स कंपायलर मॅजिकद्वारे अंमलात आणल्या जातात, तर इतर जवळजवळ सर्व सॉफ्टवेअरमध्ये लागू केले जातात आणि त्यातील सर्व गणना शुद्ध आहेत.

बरेच प्रभाव आहेत आणि प्रत्येकाचे स्वतःचे मोनाड आहे. हा एक अतिशय मजबूत आणि सुंदर सिद्धांत आहे: सर्व मोनाड समान इंटरफेस लागू करतात. आपण पुढील तीन मोनाड्सबद्दल बोलू.

• एकतर ea ही एक गणना आहे जी प्रकार a चे मूल्य मिळवते किंवा प्रकार e चा अपवाद फेकते. या मोनाडचे वर्तन अत्यावश्यक भाषांमधील अपवाद हाताळण्यासारखे आहे: त्रुटी पकडल्या जाऊ शकतात किंवा पुढे जाऊ शकतात. मुख्य फरक असा आहे की हास्केलमधील मानक लायब्ररीमध्ये मोनाड पूर्णपणे तार्किकरित्या लागू केले जाते, तर अनिवार्य भाषा सामान्यतः ऑपरेटिंग सिस्टम यंत्रणा वापरतात.
• स्टेट sa ही एक गणना आहे जी प्रकार a चे मूल्य मिळवते आणि प्रकार s च्या परिवर्तनीय स्थितीमध्ये प्रवेश करते.
• कदाचित ए. कदाचित मोनाड अशी गणना व्यक्त करते जी कधीही काहीही परत करून व्यत्यय आणू शकते. तथापि, आम्ही कदाचित प्रकारासाठी मोनाडप्लस वर्गाच्या अंमलबजावणीबद्दल बोलू, जे उलट परिणाम व्यक्त करते: ही एक गणना आहे जी विशिष्ट मूल्य परत करून कधीही व्यत्यय आणू शकते.

अल्गोरिदमची अंमलबजावणी

आमच्याकडे आलेख a आणि Bigraph ab असे दोन डेटा प्रकार आहेत, त्यातील पहिला प्रकार a च्या मूल्यांसह लेबल केलेल्या शिरोबिंदूंसह आलेख दर्शवतो आणि दुसरा प्रकार a आणि उजवीकडे लेबल केलेल्या डाव्या बाजूच्या शिरोबिंदूसह द्विपक्षीय आलेख दर्शवतो. -साइड शिरोबिंदू b प्रकाराच्या मूल्यांसह लेबल केलेले.

हे अल्गा लायब्ररीतील प्रकार नाहीत. अल्गामध्ये अनिर्देशित द्विपक्षीय आलेखांचे प्रतिनिधित्व नाही. मी स्पष्टतेसाठी असे प्रकार केले आहेत.

आम्हाला खालील स्वाक्षरींसह मदतनीस कार्ये देखील आवश्यक आहेत:

-- Список соседей данной вершины.
neighbours :: Ord a => a -> Graph a -> [a]

-- Построить двудольный граф по графу и функции, для каждой вершины
-- выдающей её долю и пометку в новой доле, игнорируя конфликтные рёбра.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
                                         -> Graph a
                                         -> Bigraph b c

-- Список вершин в графе
vertexList :: Ord a => Graph a -> [a]
Сигнатура функции, которую мы будем писать, выглядит так:

type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)

हे पाहणे सोपे आहे की खोली-प्रथम शोध दरम्यान आम्हाला परस्परविरोधी किनार आढळल्यास, विचित्र चक्र पुनरावृत्ती स्टॅकच्या शीर्षस्थानी आहे. अशा प्रकारे, ते पुनर्संचयित करण्यासाठी, आपल्याला पुनरावृत्ती स्टॅकपासून शेवटच्या शिरोबिंदूच्या पहिल्या घटनेपर्यंत सर्व काही कापले पाहिजे.

आम्ही प्रत्येक शिरोबिंदूसाठी शेअर संख्यांच्या सहयोगी ॲरे राखून सखोल-प्रथम शोध लागू करतो. आम्ही निवडल्या मोनाडच्या फंक्टर क्लासच्या अंमलबजावणीद्वारे रिकर्सन स्टॅक आपोआप राखला जाईल: आम्हाला रिकर्सिव्ह फंक्शनमधून मिळालेल्या रिझल्टमध्ये पाथमधील सर्व शिरोबिंदू ठेवण्याची आवश्यकता असेल.

एकतर मोनाड वापरण्याची माझी पहिली कल्पना होती, जी आपल्याला आवश्यक असलेल्या प्रभावांची अंमलबजावणी करते असे दिसते. मी लिहिलेली पहिली अंमलबजावणी या पर्यायाच्या अगदी जवळ होती. खरं तर, माझ्याकडे एका टप्प्यावर पाच वेगवेगळ्या अंमलबजावणी होत्या आणि शेवटी दुसऱ्यावर सेटल झालो.

प्रथम, आम्हाला शेअर आयडेंटिफायरचा एक सहयोगी ॲरे राखण्याची गरज आहे - हे राज्याबद्दल काहीतरी आहे. दुसरे म्हणजे, जेव्हा संघर्ष आढळतो तेव्हा आपण थांबण्यास सक्षम असणे आवश्यक आहे. हे एकतर एकतर मोनाड किंवा कदाचित मोनाडप्लस असू शकते. मुख्य फरक असा आहे की जर गणना थांबविली गेली नसेल तर एकतर मूल्य परत करू शकते आणि कदाचित या प्रकरणात फक्त याबद्दल माहिती परत करेल. आम्हाला यशासाठी वेगळ्या मूल्याची आवश्यकता नसल्यामुळे (ते आधीच राज्यात संग्रहित आहे), आम्ही कदाचित निवडतो. आणि या क्षणी जेव्हा आपल्याला दोन मोनाड्सचे परिणाम एकत्र करण्याची आवश्यकता असते तेव्हा ते बाहेर येतात मोनाड ट्रान्सफॉर्मर, जे हे परिणाम तंतोतंत एकत्र करतात.

मी इतका जटिल प्रकार का निवडला? दोन कारणे. प्रथम, अंमलबजावणी अत्यावश्यक सारखीच असल्याचे दिसून येते. दुसरे, विचित्र लूप पुनर्संचयित करण्यासाठी पुनरावृत्तीवरून परत येताना संघर्षाच्या बाबतीत आम्हाला परतावा मूल्य हाताळण्याची आवश्यकता आहे, जे कदाचित मोनाडमध्ये करणे खूप सोपे आहे.

अशा प्रकारे आम्हाला ही अंमलबजावणी मिळते.

{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE ScopedTypeVariables #-}

data Part = LeftPart | RightPart

otherPart :: Part -> Part
otherPart LeftPart  = RightPart
otherPart RightPart = LeftPart

type PartMap a = Map.Map a Part
type OddCycle a = [a]

toEither :: Ord a => PartMap a -> a -> Either a a
toEither m v = case fromJust (v `Map.lookup` m) of
                    LeftPart  -> Left  v
                    RightPart -> Right v

type PartMonad a = MaybeT (State (PartMap a)) [a]

detectParts :: forall a. Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)
detectParts g = case runState (runMaybeT dfs) Map.empty of
                     (Just c, _)  -> Left  $ oddCycle c
                     (Nothing, m) -> Right $ toBipartiteWith (toEither m) g
    where
        inVertex :: Part -> a -> PartMonad a
        inVertex p v = ((:) v) <$> do modify $ Map.insert v p
                                      let q = otherPart p
                                      msum [ onEdge q u | u <- neigbours v g ]

        {-# INLINE onEdge #-}
        onEdge :: Part -> a -> PartMonad a
        onEdge p v = do m <- get
                        case v `Map.lookup` m of
                             Nothing -> inVertex p v
                             Just q  -> do guard (q /= p)
                                           return [v]

        processVertex :: a -> PartMonad a
        processVertex v = do m <- get
                             guard (v `Map.notMember` m)
                             inVertex LeftPart v

        dfs :: PartMonad a
        dfs = msum [ processVertex v | v <- vertexList g ]

        oddCycle :: [a] -> [a]
        oddCycle c = tail (dropWhile ((/=) last c) c)

जेथे ब्लॉक हा अल्गोरिदमचा मुख्य भाग आहे. मी त्याच्या आत काय घडत आहे ते स्पष्ट करण्याचा प्रयत्न करेन.

• inVertex हा depth-first search चा भाग आहे जिथे आपण प्रथमच शिरोबिंदूला भेट देतो. येथे आम्ही शिरोबिंदूला एक शेअर क्रमांक नियुक्त करतो आणि सर्व शेजाऱ्यांवर onEdge चालवतो. येथे देखील आम्ही कॉल स्टॅक पुनर्संचयित करतो: जर msum ने मूल्य परत केले, तर आम्ही व्हर्टेक्स v तेथे दाबतो.
• onEdge हा भाग आहे जिथे आपण काठाला भेट देतो. प्रत्येक काठासाठी दोनदा म्हटले जाते. येथे आपण दुसऱ्या बाजूच्या शिरोबिंदूला भेट दिली आहे का ते तपासतो आणि नसल्यास त्यास भेट देतो. भेट दिल्यास, काठ परस्परविरोधी आहे का ते आम्ही तपासतो. असे असल्यास, आम्ही मूल्य परत करतो - पुनरावृत्ती स्टॅकच्या अगदी वरच्या भागावर, जेथे इतर सर्व शिरोबिंदू परत आल्यावर ठेवल्या जातील.
• processVertex प्रत्येक शिरोबिंदूला भेट दिली आहे की नाही ते तपासते आणि नसल्यास त्यावर इनव्हर्टेक्स चालवते.
• dfs सर्व शिरोबिंदूंवर processVertex चालवते.

एवढेच.

इनलाइन शब्दाचा इतिहास

INLINE हा शब्द अल्गोरिदमच्या पहिल्या अंमलबजावणीमध्ये नव्हता; तो नंतर दिसला. जेव्हा मी एक चांगली अंमलबजावणी शोधण्याचा प्रयत्न केला, तेव्हा मला आढळले की गैर-इनलाइन आवृत्ती काही आलेखांवर लक्षणीयपणे हळू होती. सिमेंटिकली फंक्शन्स सारखीच चालली पाहिजेत हे लक्षात घेऊन, मला खूप आश्चर्य वाटले. अगदी अनोळखी, GHC ची भिन्न आवृत्ती असलेल्या दुसऱ्या मशीनवर लक्षणीय फरक नव्हता.

GHC कोर आउटपुट वाचण्यात एक आठवडा घालवल्यानंतर, मी स्पष्ट INLINE च्या एका ओळीने समस्येचे निराकरण करण्यात सक्षम झालो. GHC 8.4.4 आणि GHC 8.6.5 मधील काही क्षणी ऑप्टिमायझरने हे स्वतःहून करणे थांबवले.

हॅस्केल प्रोग्रामिंगमध्ये अशी घाण येण्याची मला अपेक्षा नव्हती. तथापि, आजही, ऑप्टिमायझर कधीकधी चुका करतात आणि त्यांना सूचना देणे हे आमचे काम आहे. उदाहरणार्थ, येथे आपल्याला माहित आहे की फंक्शन इनलाइन केले पाहिजे कारण ते अत्यावश्यक आवृत्तीमध्ये इनलाइन केलेले आहे आणि हे कंपाइलरला एक इशारा देण्याचे कारण आहे.

पुढे काय झाले?

मग मी हॉपक्रॉफ्ट-कार्प अल्गोरिदम इतर मोनाड्ससह लागू केले आणि तो कार्यक्रमाचा शेवट झाला.

Google समर ऑफ कोडबद्दल धन्यवाद, मला फंक्शनल प्रोग्रामिंगचा व्यावहारिक अनुभव मिळाला, ज्याने मला पुढील उन्हाळ्यात जेन स्ट्रीटवर इंटर्नशिप मिळविण्यात मदत केली नाही (मला खात्री नाही की हे ठिकाण हॅब्रच्या जाणकार प्रेक्षकांमध्येही किती प्रसिद्ध आहे, परंतु हे एक आहे. फंक्शनल प्रोग्रॅमिंगमध्ये गुंतण्यासाठी तुम्ही उन्हाळ्यात राहू शकता अशा काहीपैकी), परंतु पारंपारिक भाषांमधील माझ्या अनुभवापेक्षा लक्षणीय भिन्न, सरावात हा नमुना लागू करण्याच्या अद्भूत जगाची मला ओळख करून दिली.

स्त्रोत: www.habr.com