ProHoster > GSoC 2019: Kontrolli i grafëve për dyndësi dhe transformatorët e monadave

GSoC 2019: Kontrolli i grafëve për dyndësi dhe transformatorët e monadave

VerĂ«n e kaluar kam marrĂ« pjesĂ« nĂ« Google Summer of Code — programi pĂ«r studentĂ«t nga kompania Google. Çdo vit organizatorĂ«t pĂ«rzgjedhin disa projekte Open Source, pĂ«rfshirĂ« nga organizata kaq tĂ« njohura si Boost.org dhe The Linux Foundation. PĂ«r tĂ« punuar nĂ« kĂ«to projekte, Google fton studentĂ« nga e gjithĂ« bota. 

Si pjesĂ«marrĂ«s nĂ« Google Summer of Code 2019, unĂ« realizova njĂ« projekt nĂ« kuadĂ«r tĂ« bibliotekĂ«s Alga nĂ« organizatĂ«n Haskell.org, e cila merret me zhvillimin e gjuhĂ«s Haskell — njĂ« nga gjuhĂ«t mĂ« tĂ« njohura tĂ« programimit funksional. Alga — njĂ« bibliotekĂ« qĂ« ofron njĂ« pĂ«rfaqĂ«sim tipobezĂ« pĂ«r grafet nĂ« Haskell. Ajo pĂ«rdoret, pĂ«r shembull, nĂ« semantic — bibliotekĂ« e kompanisĂ« Github, qĂ« ndĂ«rton pemĂ« semantike nga kodi, grafet e thirrjeve dhe varĂ«sive dhe Ă«shtĂ« nĂ« gjendje t’i krahasojĂ« ato. Projekti im pĂ«rfshinte shtimin e njĂ« pĂ«rfaqĂ«simi tipobezĂ« pĂ«r grafet dyshkuese dhe algoritmet pĂ«r kĂ«tĂ« pĂ«rfaqĂ«sim. 

Në këtë post unë do të flas rreth implementimit tim të algoritmit për të cekur dyshkueshmërinë e një grafi në Haskell. Megjithëse algoritmi është një nga më bazikët, implementimi i tij elegant në stil funksional më mori disa iteracione dhe kërkoi mjaft punë. Si rezultat, vendosa për një implementim me transformatorë monadë. 

GSoC 2019: Kontrolli i grafëve për dyndësi dhe transformatorët e monadave

Rreth meje

Më quajnë Vasili Alfyrov, unë jam student në vitin e katërt në Universitetin e Lartë në Shën Petersburg. Më parë në blog kam shkruar për projektin tim për algoritmet e parametrizuara dhe për udhëtimin në ZuriHac. Tani, unë jam duke bërë një praktikë në Universitetin e Bergenit në Norvegji, ku merrem me qasjet për problemin e List Coloring. Interesat e mia përfshijnë algoritmet e parametrizuara dhe programimin funksional.

Rreth implementimit të algoritmit

Parathënie

Studentëve që marrin pjesë në program iu rekomandohet të mbajnë një blog. Më është ofruar një platformë për blogun Summer of Haskell. Ky artikull është përkthim artikullit, shkruar nga unë atje në korrik në anglisht, me një parathënie të vogël. 

Pull Request me kodin që diskutohet mund të gjendet këtu.

Për rezultatet e punës sime mund të lexoni (në anglisht) këtu.

Postimi supozon një njohuri të lexuesit me konceptet bazike të programimit funksional, megjithatë do përpiqem të kujtoj të gjitha terminologjitë e përdorura kur të arrijë koha.

Kontrolli i grafëve për dyshkueshmëri 

Algoritmi për kontrollin e grafit për dyshkueshmëri zakonisht jepet në kursin e algoritmeve si një nga algoritmet më të thjeshta grafike. Ideja e tij është e drejtpërdrejtë: fillimisht ne në njëfarë mënyre vendosim skajet në anën e majtë apo të djathtë, dhe kur zbulojmë një lidhje konfliktoze, ne argumentojmë se grafi nuk është dyshkues.

Për të qenë pak më të detajuar: fillimisht ne vendosim një skaj në anën e majtë. Sigurisht, të gjithë fqinjët e këtij skaji duhet të jenë në anën e djathtë. Më pas, të gjithë fqinjët e fqinjëve të këtij skaji duhet të jenë në anën e majtë, e kështu me radhë. Ne vazhdojmë të caktuar skajet derisa në komponentin lidhës të skajit me të cilin filluam ende ka skaje për të cilat nuk kemi caktuar fqinjë. Pastaj ne përsërisim këtë veprim për të gjitha komponentët lidhës.

Nëse ka një lidhje mes skajeve që kanë rënë në të njëjtën anë, nuk është e vështirë të gjendet në graf një cikël çuditshëm, siç dihet gjerësisht (dhe është mjaft e dukshme) është e pamundur në një graf dyshkues. Përndryshe, ne kemi një ndarje të saktë në anë, pra grafi është dyshkues.

Si rregull, ky algoritëm implementohet duke përdorur kërkimin në gjerësi ose kërkimin në thellësi. Në gjuhët imperative zakonisht përdorin kërkimin në thellësi, pasi është pak më i thjeshtë dhe nuk kërkon struktura të tjera të dhënash. Unë gjithashtu zgjodha kërkimin në thellësi si më të traditës.

Kështu, ne arritëm në skemën e mëposhtme. Ne kalojmë përmes skajeve të grafit duke përdorur kërkimin në thellësi dhe caktojmë përkatësitë, duke ndryshuar numrin e përkatësisë gjatë kalimit nëpër lidhje. Nëse ne përpiqemi të caktojmë një përkatësi një skaji që tashmë ka një përkatësi të caktuar, mund të afirmojmë se grafi nuk është dyshkues. Në momentin që të gjitha skajet janë caktuar një përkatësie dhe ne kemi parë të gjitha lidhjet, kemi një ndarje të mirë.

Pastërtia e llogaritjeve

Në Haskell supozojmë se të gjitha llogaritjet janë të pastra. Megjithatë, nëse kjo do të ishte vërtet kështu, ne nuk do të kishim mundësinë të printonim ndonjë gjë në ekran. Në të vërtetë, llogaritjet janë aq lenjësa saqë nuk ka asnjë arsye të pastër për të llogaritur ndonjë gjë. Të gjitha llogaritjet që ndodhin në program, kështu apo ndryshe, janë të forcuara në monadën "e papastër" . Monadat janë një mënyrë për të paraqitur llogaritjet me

efekte në Haskell. Shpjegimi se si funksionojnë ato kalon përtej këtij postimi. Një përshkrim i mirë dhe i kuptueshëm mund të lexoni në anglisht. në Haskell. Shpjegimi se si funksionojnë ato del jashtë kornizës së këtij postimi. Një përshkrim i mirë dhe i kuptueshëm mund të lexohet në anglisht. këtu.

Dëgjova dëshirat e mia, që ndërsa disa monada, si IO, janë të realizuara përmes magjisë së kompajluesit, pothuajse të gjitha të tjerat janë realizuar programatikisht dhe të gjitha llogaritë në to janë të pastra.

Ka shumë efekte dhe për çdo një të gjatë një monadë të vetme. Kjo është një teori shumë e fuqishme dhe e bukur: të gjitha monadat realizojnë të njëjtin ndërfaqe. Do të flasim për këto tri monada:

  • Either e a — njĂ« llogaritje qĂ« kthen njĂ« vlerĂ« tĂ« tipit a ose hidhet njĂ« pĂ«rjashtim tĂ« tipit e. Sjellja e kĂ«saj monade Ă«shtĂ« shumĂ« e ngjashme me punĂ«n me pĂ«rjashtime nĂ« gjuhĂ«t imperativ: gabimet mund tĂ« kapen ose tĂ« kalohen mĂ« tej. Dallimi kryesor Ă«shtĂ« se monada Ă«shtĂ« plotĂ«sisht e realizuar logjikisht nĂ« bibliotekĂ«n standarde nĂ« Haskell, ndĂ«rsa nĂ« gjuhĂ«t imperativ zakonisht pĂ«rdoren mekanizmat e sistemit operativ.
  • State s a — njĂ« llogaritje qĂ« kthen njĂ« vlerĂ« tĂ« tipit a dhe ka qasje nĂ« gjendjen e ndryshueshme tĂ« tipit s.
  • Maybe a. Monad Maybe shpreh njĂ« llogaritje qĂ« mund tĂ« ndĂ«rpritet nĂ« çdo moment me kthimin e Nothing. MegjithatĂ«, do tĂ« flasim pĂ«r implementimin e klasĂ«s MonadPlus pĂ«r tipin Maybe, qĂ« shpreh efektin e kundĂ«rt: kjo Ă«shtĂ« njĂ« llogaritje qĂ« mund tĂ« ndĂ«rpritet nĂ« çdo moment me kthimin e njĂ« vlere specifike.

Implementimi i algoritmit

Kemi dy lloje të dhënash, Graph a dhe Bigraph a b, nga të cilat e para përfaqëson grafet me kulma të etiketuar me vlera të tipit a, dhe e dyta përfaqëson grafet bipartite me kulma të majtë të etiketuar me vlera të tipit a dhe kulma të djathtë të etiketuar me vlera të tipit b.

Këto nuk janë tipet nga biblioteka Alga. Në Alga nuk ka një përfaqësim për grafet bipartite të paorientuara. Unë i kam bërë këto tipa për qartësi.

Gjithashtu, na nevojiten funksione ndihmëse me këto nënshkrime:

-- Lista e fqinjëve të këtij kulmi.
neighbours :: Ord a => a -> Graph a -> [a]

-- Ndërto graf bipartit nga grafi dhe funksioni, për çdo kulm
-- që jep pjesën e saj dhe etiketën në pjesën e re, duke injoruar lidhjet me konflikt.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c

-- Lista e kulmeve në graf
vertexList :: Ord a => Graph a -> [a]
Nënshkrimi i funksionit që do të shkruajmë duket kështu:

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

Nuk është e vështirë të vëresh se nëse gjatë kërkimit në thellësi gjejmë një lidhje me konflikt, cikli çuditshëm është në majë të grumbullit të rekursioni. Pra, për ta rikuperuar, na nevojitet të presim grumbullin e rekursioni deri në shfaqjen e parë të kulmit të fundit.

Do të realizojmë kërkimin në thellësi, duke mbajtur një tabelë asociative të numrave të pjesëve për secilin kulm. Grumbulli i rekursioni do të mbështetet automatikisht përmes implementimit të klasës Functor të monadës që kemi zgjedhur: do të duhet vetëm të vendosim të gjithë kulmet nga rruga në rezultatin e kthyer nga funksioni rekursiv.

Ideja ime e parë ishte të përdorja monadën Either, e cila duket se realizon saktësisht efektet që na nevojiten. Implementimi i parë që bëra ishte shumë i afërt me këtë variant. Në fakt, në një moment, kisha pesë implementime të ndryshme, dhe përfundimisht u ndala në një tjetër.

SĂ« pari, na duhet tĂ« mbajmĂ« njĂ« tabelĂ« asociative identifikuesish pĂ«r pjesĂ«t — kjo ka tĂ« bĂ«jĂ« me State. SĂ« dyti, na nevojitet tĂ« dimĂ« tĂ« ndalemi nĂ« rast se zbulojmĂ« njĂ« konflikt. Kjo mund tĂ« jetĂ« ose Monad pĂ«r Either, ose MonadPlus pĂ«r Maybe. Dallimi kryesor Ă«shtĂ« se Either mund tĂ« kthejĂ« njĂ« vlerĂ« nĂ« rast se llogaritja nuk Ă«shtĂ« ndalur, ndĂ«rsa Maybe kthen nĂ« kĂ«tĂ« rast vetĂ«m informacionin pĂ«r kĂ«tĂ«. Duke qenĂ« se nuk na nevojitet njĂ« vlerĂ« e veçantĂ« nĂ« rast suksesi (ajo tashmĂ« ruhet nĂ« State), ne zgjedhim Maybe. Dhe nĂ« momentin kur na nevojitet tĂ« kombinojmĂ« efektet e dy monadave, dalin transformatorĂ«t e monadave, tĂ« cilat saktĂ«sisht kombinojnĂ« kĂ«to efekte.

Pse zgjodha një tip kaq të komplikuar? Dy arsye. Së pari, realizimi del të jetë shumë i ngjashëm me atë imperativ. Së dyti, na nevojitet të manipulojmë me vlerën që kthehet në rast konflikti, teksa kthehemi prapa nga rekursioni për të rikuperuar ciklin çuditshëm, dhe kjo është shumë më e lehtë të bëhet në monadën Maybe.

Kështu, ne marrim një realizim të tillë.

{-# 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  a -> PartMonad a
        onEdge p v = do m  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  [a]
        oddCycle c = tail (dropWhile ((/=) last c) c)

Bloku where — Ă«shtĂ« thelbi i algoritmit. Do tĂ« pĂ«rpiqem tĂ« shpjegoj se çfarĂ« ndodh brenda tij.

  • inVertex — Ă«shtĂ« pjesa e kĂ«rkimit nĂ« thellĂ«si, ku ne vizitojmĂ« majĂ«n pĂ«r herĂ« tĂ« parĂ«. KĂ«tu i japim majĂ«s numrin e pjesĂ«s dhe aktivizojmĂ« onEdge pĂ«r tĂ« gjithĂ« fqinjĂ«t. Gjithashtu, ky Ă«shtĂ« vendi ku rikthejmĂ« grumbullin e thirrjeve: nĂ«se msum kthen njĂ« vlerĂ«, ne bashkangjisim atje majĂ«n v.
  • onEdge — Ă«shtĂ« pjesa, ku vizitojmĂ« skajin. Ajo thirret dy herĂ« pĂ«r çdo skaj. KĂ«tu kontrollojmĂ« nĂ«se maja Ă«shtĂ« vizituar nga ana tjetĂ«r dhe e vizitojmĂ« nĂ«se jo. NĂ«se Ă«shtĂ« vizituar, kontrollojmĂ« nĂ«se skaji Ă«shtĂ« konfliktual. NĂ«se Ă«shtĂ«, kthejmĂ« vlerĂ«n — majĂ«n mĂ« tĂ« lartĂ« tĂ« grumbullit tĂ« rikthimit, ku mĂ« pas do tĂ« bashkangjiten tĂ« gjitha majat e tjera.
  • processVertex kontrollon pĂ«r çdo majĂ«, nĂ«se ajo Ă«shtĂ« vizituar, dhe e aktivizoni inVertex nĂ«se jo.
  • dfs aktivizon processVertex pĂ«r tĂ« gjitha majat.

Kaq ishte gjithçka.

Historia e fjalës INLINE

Fjala INLINE nuk ishte në implementimin e parë të algoritmit, ajo u shfaq më vonë. Kur përpiqesha të gjeja një implementim më të mirë, vura re se në disa grafikë versioni pa INLINE funksiononte dukshëm më ngadalë. Duke pasur parasysh se semantikisht funksionet duhet të punojnë njësoj, kjo më befasoi shumë. Edhe më e çuditshme ishte se në një makinë tjetër me një version tjetër të GHC, nuk kishte ndonjë diferencë të dukshme.

Pasi kalova një javë duke lexuar daljen e GHC Core, arrita ta zgjidh problemin me një rresht të qartë INLINE. Në një moment mes GHC 8.4.4 dhe GHC 8.6.5 optimizuesi ndali ta bënte këtë vetë.

Nuk e prisja tĂ« takoja kaq shumĂ« papastĂ«rti nĂ« programimin nĂ« Haskell. MegjithatĂ«, optimizatorĂ«t ende, madje edhe nĂ« kohĂ«t tona, bĂ«jnĂ« gabime dhe t'u japim atyre sugjerime — Ă«shtĂ« detyra jonĂ«. PĂ«r shembull, kĂ«tu e dimĂ« se funksioni duhet tĂ« jetĂ« i atyre, pasi ai Ă«shtĂ« i atyre nĂ« versionin imperativ, dhe kjo Ă«shtĂ« njĂ« arsye pĂ«r tĂ« dhĂ«nĂ« njĂ« sugjerim pĂ«r kompiluesin.

ÇfarĂ« ndodhi mĂ« pas?

Më pas implementova algoritmin e Hopcroft-Karp me monadat e tjera dhe këtu përfundoi programi.

Falë Google Summer of Code fitova përvojë praktike në programimin funksional, e cila jo vetëm se më ndihmoi të kaloj për një praktikë në Jane Street verën e ardhshme (nuk jam i sigurt se sa e njohur është kjo vend për audiencën e njohur të Habra, por është një nga pak vendet ku verës mund të punosh me programim funksional), por gjithashtu më prezantoi me një botë të mrekullueshme të aplikimit të kësaj paradigme në praktikë, që dallon në mënyrë të konsiderueshme nga përvoja ime në gjuhët tradicionale.

Burimi: habr.com

Bleni hostim tĂ« besueshĂ«m pĂ«r faqe me mbrojtje nga DDoS, serverĂ« VPS VDS đŸ”„ Bleni hostim tĂ« besueshĂ«m pĂ«r faqe me mbrojtje nga DDoS, serverĂ« VPS VDS | ProHoster