ગયા ઉનાળામાં મેં ભાગ લીધો હતો ગૂગલ સમર ઓફ કોડ - Google ના વિદ્યાર્થીઓ માટેનો પ્રોગ્રામ. દર વર્ષે, આયોજકો ઘણા ઓપન સોર્સ પ્રોજેક્ટ્સ પસંદ કરે છે, જેમાં આવી જાણીતી સંસ્થાઓનો સમાવેશ થાય છે Boost.org и લિનક્સ ફાઉન્ડેશન. Google આ પ્રોજેક્ટ્સ પર કામ કરવા માટે વિશ્વભરના વિદ્યાર્થીઓને આમંત્રિત કરે છે. 

Google સમર ઓફ કોડ 2019 માં સહભાગી તરીકે, મેં લાઇબ્રેરીમાં એક પ્રોજેક્ટ કર્યો આલ્ગા સંસ્થા સાથે Haskell.org, જે હાસ્કેલ ભાષા વિકસાવી રહી છે - સૌથી પ્રખ્યાત કાર્યાત્મક પ્રોગ્રામિંગ ભાષાઓમાંની એક. અલ્ગા એક પુસ્તકાલય છે જે રજૂ કરે છે સુરક્ષિત લખો હાસ્કેલમાં ગ્રાફ માટે પ્રતિનિધિત્વ. તેનો ઉપયોગ થાય છે, ઉદાહરણ તરીકે, માં અર્થપૂર્ણ — એક ગીથબ લાઇબ્રેરી જે કોડના આધારે સિમેન્ટીક ટ્રી, કોલ અને ડિપેન્ડન્સી ગ્રાફ બનાવે છે અને તેની સરખામણી કરી શકે છે. મારો પ્રોજેક્ટ તે પ્રતિનિધિત્વ માટે દ્વિપક્ષીય ગ્રાફ અને અલ્ગોરિધમ્સ માટે એક પ્રકાર-સલામત રજૂઆત ઉમેરવાનો હતો. 

આ પોસ્ટમાં હું હાસ્કેલમાં દ્વિપક્ષીયતા માટેના ગ્રાફને તપાસવા માટેના મારા અલ્ગોરિધમના અમલ વિશે વાત કરીશ. અલ્ગોરિધમ સૌથી મૂળભૂત પૈકીનું એક હોવા છતાં, તેને કાર્યાત્મક શૈલીમાં સુંદર રીતે અમલમાં મૂકવાથી મને ઘણી પુનરાવૃત્તિઓ લાગી અને ઘણું કામ કરવું પડ્યું. પરિણામે, હું મોનાડ ટ્રાન્સફોર્મર્સ સાથે અમલીકરણ પર સ્થાયી થયો. 

મારા વિશે

મારું નામ વેસિલી અલ્ફેરોવ છે, હું સેન્ટ પીટર્સબર્ગ HSE માં ચોથા વર્ષનો વિદ્યાર્થી છું. અગાઉ મેં બ્લોગમાં લખ્યું હતું પેરામીટરાઇઝ્ડ અલ્ગોરિધમ્સ વિશેના મારા પ્રોજેક્ટ વિશે и ઝુરીહેકની સફર વિશે. અત્યારે હું ઇન્ટર્નશિપ પર છું બર્ગન યુનિવર્સિટી નોર્વેમાં, જ્યાં હું સમસ્યાના અભિગમ પર કામ કરી રહ્યો છું યાદી રંગ. મારી રુચિઓમાં પેરામીટરાઇઝ્ડ અલ્ગોરિધમ્સ અને કાર્યાત્મક પ્રોગ્રામિંગનો સમાવેશ થાય છે.

અલ્ગોરિધમના અમલીકરણ વિશે

ફોરવર્ડ

પ્રોગ્રામમાં ભાગ લેનારા વિદ્યાર્થીઓને બ્લોગ કરવા માટે ભારપૂર્વક પ્રોત્સાહિત કરવામાં આવે છે. તેઓએ મને બ્લોગ માટે પ્લેટફોર્મ પૂરું પાડ્યું હાસ્કેલનો ઉનાળો. આ લેખ અનુવાદ છે લેખ, મારા દ્વારા જુલાઇમાં અંગ્રેજીમાં લખાયેલું, ટૂંકી પ્રસ્તાવના સાથે. 

પ્રશ્નમાં કોડ સાથે પુલ વિનંતી મળી શકે છે અહીં.

તમે મારા કાર્યના પરિણામો વિશે વાંચી શકો છો (અંગ્રેજીમાં) અહીં.

આ પોસ્ટ ધારે છે કે વાચક વિધેયાત્મક પ્રોગ્રામિંગના મૂળભૂત ખ્યાલોથી પરિચિત છે, જો કે જ્યારે સમય આવશે ત્યારે હું ઉપયોગમાં લેવાતા તમામ શબ્દોને યાદ કરવાનો પ્રયાસ કરીશ.

દ્વિપક્ષીયતા માટે આલેખ તપાસી રહ્યું છે 

દ્વિપક્ષીયતા માટે ગ્રાફ તપાસવા માટેનું અલ્ગોરિધમ સામાન્ય રીતે સૌથી સરળ ગ્રાફ અલ્ગોરિધમ્સમાંના એક તરીકે અલ્ગોરિધમ્સના કોર્સમાં આપવામાં આવે છે. તેમનો વિચાર સીધો છે: પહેલા આપણે કોઈક રીતે ડાબે અથવા જમણા શેરમાં શિરોબિંદુઓ મૂકીએ છીએ, અને જ્યારે વિરોધાભાસી ધાર મળે છે, ત્યારે અમે ભારપૂર્વક કહીએ છીએ કે આલેખ દ્વિપક્ષીય નથી.

થોડી વધુ વિગત: પહેલા આપણે ડાબા શેરમાં કેટલાક શિરોબિંદુ મૂકીએ છીએ. દેખીતી રીતે, આ શિરોબિંદુના બધા પડોશીઓ જમણા લોબમાં આવેલા હોવા જોઈએ. આગળ, આ શિરોબિંદુના પડોશીઓના તમામ પડોશીઓ ડાબા લોબમાં આવેલા હોવા જોઈએ, અને તેથી વધુ. અમે શિરોબિંદુઓને શેર અસાઇન કરવાનું ચાલુ રાખીએ છીએ જ્યાં સુધી અમે પડોશીઓને સોંપ્યા નથી તેવા શિરોબિંદુના કનેક્ટેડ ઘટકમાં હજુ પણ શિરોબિંદુઓ છે. પછી અમે બધા કનેક્ટેડ ઘટકો માટે આ ક્રિયાને પુનરાવર્તિત કરીએ છીએ.

જો સમાન પાર્ટીશનમાં આવતા શિરોબિંદુઓ વચ્ચે કોઈ ધાર હોય, તો ગ્રાફમાં એક વિચિત્ર ચક્ર શોધવું મુશ્કેલ નથી, જે દ્વિપક્ષીય ગ્રાફમાં વ્યાપકપણે જાણીતું છે (અને તદ્દન સ્પષ્ટ રીતે) અશક્ય છે. નહિંતર, અમારી પાસે યોગ્ય પાર્ટીશન છે, જેનો અર્થ છે કે ગ્રાફ દ્વિપક્ષીય છે.

સામાન્ય રીતે, આ અલ્ગોરિધમનો ઉપયોગ કરીને અમલમાં મૂકવામાં આવે છે પહોળાઈ પ્રથમ શોધ અથવા ઊંડાઈ પ્રથમ શોધ. આવશ્યક ભાષાઓમાં, ઊંડાણ-પ્રથમ શોધનો ઉપયોગ સામાન્ય રીતે થાય છે કારણ કે તે સહેજ સરળ છે અને વધારાના ડેટા સ્ટ્રક્ચર્સની જરૂર નથી. મેં ઊંડાણ-પ્રથમ શોધ પણ પસંદ કરી કારણ કે તે વધુ પરંપરાગત છે.

આમ, અમે નીચેની યોજના પર આવ્યા. અમે ઊંડાણ-પ્રથમ શોધનો ઉપયોગ કરીને ગ્રાફના શિરોબિંદુઓને પાર કરીએ છીએ અને તેમને શેર અસાઇન કરીએ છીએ, જેમ જેમ આપણે ધાર સાથે આગળ વધીએ છીએ તેમ શેરની સંખ્યા બદલીએ છીએ. જો આપણે એવા શિરોબિંદુને શેર અસાઇન કરવાનો પ્રયાસ કરીએ કે જેમાં પહેલેથી જ શેર અસાઇન કરેલ હોય, તો અમે સુરક્ષિત રીતે કહી શકીએ કે આલેખ દ્વિપક્ષીય નથી. જે ક્ષણે બધા શિરોબિંદુઓને એક શેર સોંપવામાં આવે છે અને અમે બધી કિનારીઓ જોઈ લીધી છે, અમારી પાસે એક સારું પાર્ટીશન છે.

ગણતરીઓની શુદ્ધતા

હાસ્કેલમાં આપણે ધારીએ છીએ કે બધી ગણતરીઓ છે ચોખ્ખો. જો કે, જો આ ખરેખર કેસ હોત, તો અમારી પાસે સ્ક્રીન પર કંઈપણ છાપવાનો કોઈ રસ્તો ન હોત. બધા પર, ચોખ્ખો ગણતરીઓ એટલી આળસુ છે કે ત્યાં એક પણ નથી ચોખ્ખો કંઈક ગણતરી માટે કારણો. પ્રોગ્રામમાં થતી તમામ ગણતરીઓ કોઈક રીતે ફરજ પાડવામાં આવે છે "અશુદ્ધ" મોનાડ આઇઓ.

મોનાડ્સ એ ગણતરીઓને રજૂ કરવાની એક રીત છે અસરો હાસ્કેલમાં. તેઓ કેવી રીતે કાર્ય કરે છે તે સમજાવવું આ પોસ્ટના અવકાશની બહાર છે. અંગ્રેજીમાં સારું અને સ્પષ્ટ વર્ણન વાંચી શકાય છે અહીં.

અહીં હું એ નિર્દેશ કરવા માંગુ છું કે જ્યારે કેટલાક મોનાડ્સ, જેમ કે 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 એ ઊંડાણ-પ્રથમ શોધનો ભાગ છે જ્યાં આપણે પ્રથમ વખત શિરોબિંદુની મુલાકાત લઈએ છીએ. અહીં આપણે શિરોબિંદુને શેર નંબર અસાઇન કરીએ છીએ અને બધા પડોશીઓ પર onEdge ચલાવીએ છીએ. આ તે છે જ્યાં આપણે કૉલ સ્ટેકને પુનઃસ્થાપિત કરીએ છીએ: જો msum મૂલ્ય પરત કરે છે, તો અમે શિરોબિંદુ v ત્યાં દબાણ કરીએ છીએ.
• onEdge એ ભાગ છે જ્યાં આપણે ધારની મુલાકાત લઈએ છીએ. તે દરેક ધાર માટે બે વાર કહેવામાં આવે છે. અહીં આપણે તપાસીએ છીએ કે બીજી બાજુના શિરોબિંદુની મુલાકાત લેવામાં આવી છે કે નહીં, અને જો ન હોય તો તેની મુલાકાત લઈએ. જો મુલાકાત લેવામાં આવે, તો અમે તપાસ કરીએ છીએ કે ધાર વિરોધાભાસી છે કે કેમ. જો તે હોય, તો અમે મૂલ્ય પરત કરીએ છીએ - પુનરાવર્તિત સ્ટેકની ખૂબ જ ટોચ, જ્યાં અન્ય તમામ શિરોબિંદુઓ પછી પાછા ફરવા પર મૂકવામાં આવશે.
• પ્રોસેસવર્ટેક્સ દરેક શિરોબિંદુ માટે તપાસ કરે છે કે શું તેની મુલાકાત લેવામાં આવી છે અને જો ન હોય તો તેના પર વર્ટેક્સ ચલાવે છે.
• dfs બધા શિરોબિંદુઓ પર પ્રોસેસવર્ટેક્સ ચલાવે છે.

બસ.

ઇનલાઇન શબ્દનો ઇતિહાસ

INLINE શબ્દ અલ્ગોરિધમના પ્રથમ અમલીકરણમાં ન હતો; તે પછીથી દેખાયો. જ્યારે મેં બહેતર અમલીકરણ શોધવાનો પ્રયાસ કર્યો, ત્યારે મેં જોયું કે બિન-ઈનલાઈન સંસ્કરણ કેટલાક ગ્રાફ પર નોંધપાત્ર રીતે ધીમું હતું. સિમેન્ટીકલી ફંક્શન્સ એ જ કામ કરવું જોઈએ તે ધ્યાનમાં લેતા, આનાથી મને ખૂબ જ આશ્ચર્ય થયું. અજાણી વ્યક્તિ પણ, GHC ના ભિન્ન સંસ્કરણવાળા અન્ય મશીન પર કોઈ નોંધપાત્ર તફાવત નહોતો.

GHC કોર આઉટપુટ વાંચવામાં એક અઠવાડિયું ગાળ્યા પછી, હું સ્પષ્ટ ઇનલાઇનની એક લાઇનથી સમસ્યાને ઠીક કરવામાં સક્ષમ હતો. GHC 8.4.4 અને GHC 8.6.5 ની વચ્ચે અમુક સમયે ઑપ્ટિમાઇઝરે આ જાતે કરવાનું બંધ કર્યું.

મેં હાસ્કેલ પ્રોગ્રામિંગમાં આવી ગંદકીનો સામનો કરવાની અપેક્ષા નહોતી કરી. જો કે, આજે પણ, ઑપ્ટિમાઇઝર્સ કેટલીકવાર ભૂલો કરે છે, અને તેમને સંકેતો આપવાનું અમારું કામ છે. ઉદાહરણ તરીકે, અહીં આપણે જાણીએ છીએ કે ફંક્શન ઇનલાઇન હોવું જોઈએ કારણ કે તે અનિવાર્ય સંસ્કરણમાં ઇનલાઇન છે, અને આ કમ્પાઇલરને સંકેત આપવાનું એક કારણ છે.

આગળ શું થયું?

પછી મેં અન્ય મોનાડ્સ સાથે હોપક્રોફ્ટ-કાર્પ અલ્ગોરિધમનો અમલ કર્યો, અને તે પ્રોગ્રામનો અંત હતો.

Google સમર ઑફ કોડનો આભાર, મેં ફંક્શનલ પ્રોગ્રામિંગમાં વ્યવહારુ અનુભવ મેળવ્યો, જેણે મને આવતા ઉનાળામાં જેન સ્ટ્રીટ ખાતે ઇન્ટર્નશિપ મેળવવામાં મદદ કરી. વિધેયાત્મક પ્રોગ્રામિંગમાં સામેલ થવા માટે તમે ઉનાળો કરી શકો તેવા થોડામાંથી), પણ પરંપરાગત ભાષાઓમાં મારા અનુભવ કરતાં નોંધપાત્ર રીતે અલગ, વ્યવહારમાં આ દાખલાને લાગુ કરવાની અદ્ભુત દુનિયા સાથે પણ મને પરિચય કરાવ્યો.

સોર્સ: www.habr.com