Veriun verën e kaluar mora pjesë në — një program për studentët nga kompaninë Google. Çdo vit, organizatorët përzgjidhin disa projekte Open Source, duke përfshirë nga organizata të njohura si и . Për të punuar mbi këto projekte, Google fton studentë nga e gjithë bota.
Si pjesëmarrës në Google Summer of Code 2019, unë realizova një projekt brenda bibliotekës në organizatën , e cila merret me zhvillimin e gjuhës Haskell — një nga gjuhët më të njohura të programimit funksional. Alga është një bibliotekë që ofron të përfaqësimit për grafët në Haskell. Ajo përdoret, për shembull, në — bibliotekën e kompanisë Github, e cila ndërton pemë semantike, grafë thirrjesh dhe varësish nga kodi dhe është në gjendje t'i krahasojë ato. Projekti im përfshinte shtimin e një përfaqësimi të sigurt për grafët dy-pjesësh dhe algoritme për këtë përfaqësim.
Në këtë postim do të flas për implementimin tim të algoritmit për verifikimin e grafit për dy-pjesshmëri në Haskell. Megjithëse algoritmi është një nga më bazikët, implementimi i tij tërheqës në stilin funksional më mori disa iteracione dhe kërkoi një punë të konsiderueshme. Si rezultat, vendosa për një implementim me transformatorë monad.
Për vetë
Më quajnë Vasily Alfyrov, jam student i vitit të katërt në Universitetin e Peterburgut. Më parë në blog kam shkruar и . Tani po bëj një praktikë në në Norvegji, ku merrem me qasjet ndaj problemit të . Fushat e mia të interesit përfshijnë algoritmet e parametrizuara dhe programimin funksional.
Rreth implementimit të algoritmit
Parathënie
Studentët që marrin pjesë në program, këshillohen me ngulm të mbajnë një blog. Më kanë ofruar një platformë për blogun . Ky artikull është një përkthim , i shkruar prej meje për aty në korrik në anglisht, me një parathënie të vogël.
Pull Request me kodin që po flitet, mund ta gjeni .
Për rezultatet e punës sime mund të lexoni (në anglisht) .
Postimi supozon njohjen e lexuesit me konceptet bazë në programimin funksional, edhe pse do të përpiqem të rikujtoj të gjitha termat e përdorura, kur të arrijë koha për to.
Verifikimi i grafëve për dy-pjeshmëri
Algoritmi i kontrollit të grafit për ndarjen në dy pjesë zakonisht jepet në kursin e algoritmeve si një nga algoritmet më të thjeshta të grafëve. Ideja e tij është e drejtpërdrejtë: fillimisht ne në njëfarë mënyre vendosim pikat në pjesën e majtë ose të djathtë, dhe kur zbulojmë një skaj të kundërt, konfirmojmë se grafi nuk është ndarë në dy pjesë.
Më në detaje: fillimisht ne vendosim një pikë në pjesën e majtë. Sigurisht, të gjitha fqinjët e kësaj pike duhet të jenë në pjesën e djathtë. Më pas, të gjithë fqinjët e fqinjëve të kësaj pike duhet të jenë në pjesën e majtë, dhe kështu me radhë. Ne vazhdojmë të caktojmë pikave pjesët derisa në komponentin e lidhjes së pikës me të cilën filluam, të ketë ende pika të pa caktuara fqinjët. Pastaj ne e përsërisim këtë veprim për të gjitha komponentët e lidhjes.
Nëse ka një skaj midis pikave që përfundojnë në të njëjtën pjesë, nuk është e vështirë të gjejmë një cikël çifte në grafik, siç dihet gjerësisht (dhe është mjaft e qartë) e pamundur në një grafik të ndarë në dy pjesë. Përndryshe kemi një ndarje të saktë në pjesë, dhe kështu, grafi është i ndarë në dy pjesë.
Si rregull, ky algoritëm realizohet me или . Në gjuhët imperativë zakonisht përdoret kërkimi në thellësi, si pak më i thjeshtë dhe që nuk kërkon struktura të dhënash shtesë. Unë gjithashtu zgjodha kërkimin në thellësi si metodë më tradicionale.
Kështu, ne arritëm në skemën e mëposhtme. Ne kalojmë nëpër pikat e grafit duke përdorur kërkimin në thellësi dhe u caktojmë ato pjesë, duke ndryshuar numrin e pjesës kur kalojmë përmes një skaji. Nëse përpiqemi të ndajmë një pjesë një pikës, e cila tashmë ka një pjesë të caktuar, mund të konfirmojmë se grafi nuk është ndarë në dy pjesë. Në momentin që të gjitha pikat janë ndarë dhe ne e kemi parë të gjithë skajet, ne kemi një ndarje të mirë.
Pastrimi i llogaritjeve
Në Haskell supozojmë se të gjitha llogaritjet janë të pastra. Megjithatë, sikur kjo të ishte e vërtetë, ne nuk do të kishim mundësi të printonim asgjë në ekran. Në përgjithësi, llogaritjet të pastra janë kaq të ngadalta, saqë nuk ka asnjë arsye të pastrë për të llogaritur ndonjë gjë. Të gjitha llogaritjet që ndodhin në program, në një farë mënyre, përforcohen në "mungesën e pastërtisë" monadën IO.
Monadat janë një mënyrë për të paraqitur llogaritjet me efekte. në Haskell. Shpjegimi i mënyrës sesi ato punojnë del përtej këtij posti. Një përshkrim i mirë dhe i kuptueshëm mund të lexoni në anglisht .
Këtu dua të theksoj se, ndonëse disa monada, si IO, janë të implementuara përmes magjisë së kompilatorit, pothuajse të gjitha të tjerat janë të implementuara programërisht dhe të gjitha llogaritë në to janë të pastra.
Ekzistojnë shumë efekte dhe për secilin është krijuar një monadë e vetme. Kjo është një teori shumë e fuqishme dhe e bukur: të gjitha monadat implementojnë të njëjtën ndërfaqe. Ne do të flasim për këto tri monada:
- Either e a — një llogaritje që kthen një vlerë të tipit a ose hedh një përjashtim të tipit e. Sjellja e kësaj monade është shumë e ngjashme me punën me përjashtimet në gjuhët imperativë: gabimet mund të kapen ose të kalojnë më tej. Diferenca kryesore është se monada është e implementuar plotësisht në mënyrë logjike në bibliotekën standarde në Haskell, ndërkohë që 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 akses në një gjendje të ndryshueshme të tipit s.
- Maybe a. Monada Maybe shpreh një llogaritje që mund të ndërpritet në çdo moment nga kthimi i Nothing. Megjithatë, ne 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 duke kthyer një vlerë konkrete.
Implementimi i algoritmit
Ne kemi dy tipe të dhënash, Graph a dhe Bigraph a b, i pari nga të cilët përfaqëson grafet me pika të shënuara me vlera të tipit a, ndërsa tjetri përfaqëson grafet e dyfishta me pika të majtë të shënuara me vlera të tipit a dhe pika të djathta të shënuara me vlera të tipit b.
Këto nuk janë tipe nga biblioteka Alga. Në Alga nuk ka përfaqësim për grafet e dyfishta të paorientuara. Tipet i krijova kështu për qartësi.
Gjithashtu, do të na nevojiten funksione ndihmëse me këto nënshkrime:
-- Lista e fqinjëve të kësaj kulme.
neighbours :: Ord a => a -> Graph a -> [a]
-- Ndërtoni një graf bipartit nga grafi dhe funksioni, për secilën kulm
-- që jep aksionin e saj dhe shënimin në aksionin e ri, duke injoruar skajet konfliktuese.
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]
Sinshtet e 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ë procesit të kërkimit në thellësi gjejmë një skaj konfliktues, cikli çuditshëm ndodhet në krye të grimit të rekursisë. Kështu që, për ta rikuperuar atë, na duhet të prishim të gjitha në grimin e rekursisë deri në shfaqjen e parë të kulmës së fundit.
Ne do të zbatojmë kërkimin në thellësi, duke mbajtur një array asociativ të numrave të aksionit për secilën kulmë. Grimi i rekursisë do të mbahet automatikisht përmes implementimit të klasës Functor të monadës që kemi zgjedhur: thjesht do të duhet të vendosim të gjitha kulmet në rrugë në rezultatin që kthehet nga funksioni rekursiv.
Ideja ime e parë ishte të përdorja monadën Either, e cila në dukje realizon efektet që na nevojiten. Implementimi i parë që shkrova ishte shumë i afërt me këtë variant. Në të vërtetë, unë kisha pesë implementime të ndryshme në një moment, dhe përfundimisht u ndala në një tjetër.
Në radhë të parë, na nevojitet të mbajmë një array asociativ të identifikuesve të aksionit — ky është diçka në lidhje me State. Në radhë të dytë, na nevojitet të dimë si 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ë rastin kur llogaritja nuk është ndalur, ndërsa Maybe kthen në këtë rast vetëm informacion në lidhje me këtë. Duke qenë se nuk na nevojitet një vlerë e veçantë në rastin e suksesit (ajo është tashmë e ruajtur në State), ne zgjedhim Maybe. Dhe në momentin kur na nevojitet të kombinojmë efektet e dy monadave, dalin , të cilat në fakt këto efekte i kombinojnë.
Pse e zgjodha një tip kaq të ndërlikuar? Dy arsye. Së pari, realizimi doli shumë i ngjashëm me të imperative. Së dyti, na nevojitet të manipulojmë me vlerën që kthehet në rast të konfliktit, kur kthehemi prapa nga rekursioni për të rikuperuar një cikël të çuditshëm, dhe kjo është shumë më e lehtë ta bëjmë 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)
Blloku where — është thelbi i algoritmit. Do përpiqem të shpjegoj se çfarë ndodh brenda tij.
- inVertex — është pjesa e kërkimit në thellësi, ku ne vizitojmë një pikë për herë të parë. Këtu i japim pikës numrin e pjesës dhe aktivizojmë onEdge për të gjithë fqinjët. Gjithashtu, kjo është vendi ku rikuperojmë grumbullin e thirrjeve: nëse msum ktheu një vlerë, ne e lidhim atje pikën v.
- onEdge — është pjesa kur vizitojmë skajet. Ajo thirret dy herë për çdo skaj. Këtu kontrollojmë nëse maja nga ana tjetër është vizituar dhe e vizitojmë atë nëse nuk është. Nëse është vizituar, kontrollojmë nëse skaji është konfliktual. Nëse është, kthejmë vlerën — majën e stack-ut të rekursivitetit, ku më pas do të ngjiten të gjitha majat e tjera gjatë kthimit.
- processVertex kontrollon për çdo majë nëse është vizituar dhe e nis inVertex në të nëse nuk është.
- dfs nis processVertex në të gjitha majat.
Kjo është 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 grafe versioni pa INLINE funksiononte ndjeshëm më ngadalë. Duke pasur parasysh që semantikisht funksionet duhet të punojnë njësoj, kjo më befasoi shumë. Edhe më e çuditshme ishte që në një makinë tjetër me një version tjetër të GHC nuk kishte asnjë ndryshim të dukshëm.
Pas një javë të kaluar duke lexuar daljen e GHC Core, arrita të rregulloj problemin me një rresht me INLINE të qartë. Në një moment midis GHC 8.4.4 dhe GHC 8.6.5 optimizuesi ndaloi ta bëjë këtë automatikisht.
Nuk e prisja të hasja një kaos të tillë në programimin me Haskell. Megjithatë, optimizuesit megjithatë, madje edhe në kohët tona, ndonjëherë bëjnë gabime dhe t'u japësh atyre sugjerime — është detyra jonë. Për shembull, këtu e dimë që funksioni duhet të jetë i inlinuar, sepse është i inlinuar në versionin imperativ, dhe kjo është arsyeja për të dhënë një sugjerim për kompajlerin.
Çfarë ndodhi më pas?
Më pas realizova algoritmin e Hopcroft-Karpa me monada të tjera, dhe me këtë programi përfundoi.
Falë Google Summer of Code, fitova përvojë praktike në programimin funksional, që jo vetëm që më ndihmoi të kaloj në një praktikë në Jane Street verën tjetër (nuk jam i sigurt se sa e njohur është kjo vend për audiencën e ditur të Habra, por është një nga pak ku në verë mund të merresh me programimin funksional), por gjithashtu më prezantoi me botën e habitshme të aplikimit të kësaj paradigme në praktikë, e cila ndryshon ndjeshëm nga përvoja ime në gjuhët tradicionale.
Burimi: habr.com
