Verën e kaluar mora pjesë - një program për studentët nga Google. Çdo vit, organizatorët zgjedhin disa projekte me burim të hapur, duke përfshirë nga organizata të tilla të njohura si и . Google fton studentë nga e gjithë bota të punojnë në këto projekte.
Si pjesëmarrëse në Google Summer of Code 2019, bëra një projekt brenda bibliotekës me organizatën , e cila po zhvillon gjuhën Haskell - një nga gjuhët më të famshme të programimit funksional. Alga është një bibliotekë që përfaqëson paraqitje për grafikët në Haskell. Përdoret, për shembull, në — një bibliotekë Github që ndërton pemë semantike, grafikë thirrjesh dhe varësie bazuar në kod dhe mund t'i krahasojë ato. Projekti im ishte të shtoja një paraqitje të sigurt për tipin për grafikët dypalësh dhe algoritme për atë paraqitje.
Në këtë postim do të flas për zbatimin tim të një algoritmi për kontrollimin e një grafiku për dypalësi në Haskell. Edhe pse algoritmi është një nga më themelorët, zbatimi i tij bukur në një stil funksional më mori disa përsëritje dhe kërkoi mjaft punë. Si rezultat, u vendosa në një zbatim me transformatorë monadë.
Rreth vetes sime
Unë quhem Vasily Alferov, jam student në vitin e katërt në Shën Petersburg HSE. Më herët në blog kam shkruar и . Tani për tani jam në një stazh në në Norvegji, ku po punoj për qasjet ndaj problemit . Interesat e mia përfshijnë algoritme të parametrizuara dhe programim funksional.
Rreth zbatimit të algoritmit
Parathënie libri
Studentët që marrin pjesë në program inkurajohen fuqimisht të bëjnë blog. Ata më dhanë një platformë për blogun . Ky artikull është një përkthim , shkruar nga unë atje në korrik në anglisht, me një parathënie të shkurtër.
Mund të gjendet Kërkesa për tërheqje me kodin në fjalë .
Ju mund të lexoni për rezultatet e punës sime (në anglisht) .
Ky postim synon të njohë lexuesin me konceptet bazë në programimin funksional, megjithëse do të përpiqem të kujtoj të gjithë termat e përdorur kur të vijë koha.
Kontrollimi i grafikëve për dypalësi
Një algoritëm për të kontrolluar një grafik për dypalësi zakonisht jepet në një kurs mbi algoritmet si një nga algoritmet më të thjeshtë të grafikut. Ideja e tij është e drejtpërdrejtë: së pari ne vendosim disi kulme në pjesën e majtë ose të djathtë, dhe kur gjendet një skaj konfliktual, ne pohojmë se grafiku nuk është dypalësh.
Pak më shumë detaje: së pari vendosim një kulm në pjesën e majtë. Natyrisht, të gjithë fqinjët e këtij kulmi duhet të shtrihen në lobin e djathtë. Më tej, të gjithë fqinjët e fqinjëve të këtij kulmi duhet të shtrihen në lobin e majtë, e kështu me radhë. Ne vazhdojmë t'u caktojmë aksione kulmeve për sa kohë që ka ende kulme në komponentin e lidhur të kulmit me të cilin filluam, të cilave nuk i kemi caktuar fqinjët. Më pas e përsërisim këtë veprim për të gjithë komponentët e lidhur.
Nëse ka një skaj midis kulmeve që bien në të njëjtën ndarje, nuk është e vështirë të gjesh një cikël tek në grafik, gjë që njihet gjerësisht (dhe fare qartë) e pamundur në një graf bipartit. Përndryshe, ne kemi një ndarje të saktë, që do të thotë se grafiku është bipartit.
Në mënyrë tipike, ky algoritëm zbatohet duke përdorur ose . Në gjuhët imperative, kërkimi i parë në thellësi zakonisht përdoret pasi është pak më i thjeshtë dhe nuk kërkon struktura shtesë të të dhënave. Zgjodha gjithashtu kërkimin e parë në thellësi pasi është më tradicional.
Kështu, arritëm në skemën e mëposhtme. Ne përshkojmë kulmet e grafikut duke përdorur kërkimin e parë në thellësi dhe caktojmë aksione atyre, duke ndryshuar numrin e ndarjes ndërsa lëvizim përgjatë skajit. Nëse përpiqemi të caktojmë një pjesë në një kulm që tashmë ka një pjesë të caktuar, mund të themi me siguri se grafiku nuk është dypalësh. Në momentin që të gjitha kulmet u caktohet një pjesë dhe ne kemi parë të gjitha skajet, kemi një ndarje të mirë.
Pastërtia e llogaritjeve
Në Haskell supozojmë se të gjitha llogaritjet janë pastër. Megjithatë, nëse do të ishte vërtet kështu, ne nuk do të kishim asnjë mënyrë për të printuar asgjë në ekran. fare, i pastër llogaritjet janë aq dembel sa nuk ka asnjë pastër arsye për të llogaritur diçka. Të gjitha llogaritjet që ndodhin në program detyrohen disi "i papastër" monad IO.
Monadat janë një mënyrë për të paraqitur llogaritjet me efektet në Haskell. Shpjegimi se si funksionojnë është përtej qëllimit të këtij postimi. Një përshkrim i mirë dhe i qartë mund të lexohet në anglisht .
Këtu dua të theksoj se ndërsa disa monada, si IO, zbatohen përmes magjisë së përpiluesit, pothuajse të gjitha të tjerat zbatohen në softuer dhe të gjitha llogaritjet në to janë të pastra.
Ka shumë efekte dhe secila ka monadën e vet. Kjo është një teori shumë e fortë dhe e bukur: të gjitha monadat zbatojnë të njëjtën ndërfaqe. Ne do të flasim për tre monadat e mëposhtme:
- Ose ea është 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 trajtimin e përjashtimeve në gjuhët imperative: gabimet mund të kapen ose të kalojnë. Dallimi kryesor është se monada zbatohet plotësisht logjikisht në bibliotekën standarde në Haskell, ndërsa gjuhët imperative zakonisht përdorin mekanizma të sistemit operativ.
- Gjendja sa është një llogaritje që kthen një vlerë të tipit a dhe ka akses në gjendjen e ndryshueshme të tipit s.
- Ndoshta a. Monada Ndoshta shpreh një llogaritje që mund të ndërpritet në çdo kohë duke kthyer Asgjë. Megjithatë, do të flasim për zbatimin e klasës MonadPlus për llojin Maybe, e cila shpreh efektin e kundërt: është një llogaritje që mund të ndërpritet në çdo kohë duke kthyer një vlerë specifike.
Zbatimi i algoritmit
Kemi dy lloje të dhënash, Grafiku a dhe Bigrafi ab, i pari prej të cilëve përfaqëson grafikë me kulme të etiketuara me vlera të tipit a, dhe i dyti përfaqëson grafikë dypalësh me kulme në anën e majtë të etiketuar me vlera të tipit a dhe djathtas. - kulmet anësore të etiketuara me vlera të tipit b.
Këto nuk janë lloje nga biblioteka Alga. Alga nuk ka një paraqitje për grafikë dypalësh të padrejtuar. I bëra llojet si kjo për qartësi.
Do të na duhen gjithashtu funksione ndihmëse me nënshkrimet e mëposhtme:
-- Список соседей данной вершины.
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)Është e lehtë të shihet se nëse gjatë kërkimit të parë në thellësi kemi gjetur një skaj konfliktual, cikli tek qëndron në krye të pirgut të rekursionit. Kështu, për ta rikthyer atë, ne duhet të ndërpresim gjithçka nga grumbulli i rekursionit deri në shfaqjen e parë të kulmit të fundit.
Ne zbatojmë kërkimin e parë në thellësi duke mbajtur një grup shoqërues të numrave të aksioneve për çdo kulm. Stacki i rekursionit do të mbahet automatikisht përmes zbatimit të klasës Functor të monadës që kemi zgjedhur: do të na duhet vetëm të vendosim të gjitha kulmet nga shtegu në rezultatin e kthyer nga funksioni rekurziv.
Ideja ime e parë ishte të përdorja monadën Ose, e cila duket se zbaton saktësisht efektet që na duhen. Zbatimi i parë që shkrova ishte shumë afër këtij opsioni. Në fakt, unë kisha pesë zbatime të ndryshme në një moment dhe përfundimisht u vendosa në një tjetër.
Së pari, ne duhet të mbajmë një grup shoqërues të identifikuesve të aksioneve - kjo është diçka për shtetin. Së dyti, ne duhet të jemi në gjendje të ndalojmë kur zbulohet një konflikt. Kjo mund të jetë ose Monad për Ose, ose MonadPlus për Ndoshta. Dallimi kryesor është se Ose mund të kthejë një vlerë nëse llogaritja nuk është ndalur, dhe Ndoshta kthen vetëm informacione për këtë në këtë rast. Meqenëse nuk kemi nevojë për një vlerë të veçantë për sukses (ajo tashmë është ruajtur në gjendje), ne zgjedhim Ndoshta. Dhe në momentin kur duhet të kombinojmë efektet e dy monadave, ato dalin , të cilat kombinojnë saktësisht këto efekte.
Pse zgjodha një lloj kaq kompleks? Dy arsye. Së pari, zbatimi rezulton të jetë shumë i ngjashëm me imperativin. Së dyti, duhet të manipulojmë vlerën e kthimit në rast konflikti kur kthehemi nga rekursioni për të rivendosur ciklin tek, gjë që është shumë më e lehtë për t'u bërë në monadën Ndoshta.
Kështu e marrim këtë zbatim.
{-# 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)
Blloku ku është thelbi i algoritmit. Do të përpiqem të shpjegoj se çfarë po ndodh brenda saj.
- inVertex është pjesa e kërkimit të parë në thellësi ku ne vizitojmë kulmin për herë të parë. Këtu caktojmë një numër share në kulm dhe ekzekutojmë onEdge në të gjithë fqinjët. Kjo është gjithashtu ajo ku ne rivendosim grupin e thirrjeve: nëse msum kthen një vlerë, ne shtyjmë kulmin v atje.
- onEdge është pjesa ku ne vizitojmë skajin. Ai thirret dy herë për çdo skaj. Këtu kontrollojmë nëse kulmi në anën tjetër është vizituar dhe e vizitojmë nëse jo. Nëse vizitohet, ne kontrollojmë nëse skaji është në konflikt. Nëse është, ne kthejmë vlerën - majën e pirgut të rekursionit, ku të gjitha kulmet e tjera do të vendosen më pas pas kthimit.
- processVertex kontrollon për çdo kulm nëse është vizituar dhe ekzekuton në Vertex në të nëse jo.
- dfs ekzekuton processVertex në të gjitha kulmet.
Kjo është e gjitha.
Historia e fjalës INLINE
Fjala INLINE nuk ishte në zbatimin e parë të algoritmit; ajo u shfaq më vonë. Kur u përpoqa të gjeja një zbatim më të mirë, zbulova se versioni jo-INLINE ishte dukshëm më i ngadalshëm në disa grafikë. Duke marrë parasysh që funksionet semantike duhet të funksionojnë njësoj, kjo më befasoi shumë. Edhe më e çuditshme, në një makinë tjetër me një version tjetër të GHC nuk kishte asnjë ndryshim të dukshëm.
Pasi kalova një javë duke lexuar daljen GHC Core, munda ta rregulloja problemin me një linjë të qartë INLINE. Në një moment midis GHC 8.4.4 dhe GHC 8.6.5, optimizuesi ndaloi ta bënte këtë vetë.
Nuk prisja të hasja një pisllëk të tillë në programimin Haskell. Megjithatë, edhe sot, optimizuesit ndonjëherë bëjnë gabime dhe është detyra jonë t'u japim atyre sugjerime. Për shembull, këtu ne e dimë se funksioni duhet të jetë i inlinuar sepse është i inlinuar në versionin imperativ, dhe kjo është një arsye për t'i dhënë kompajlerit një aluzion.
Çfare ndodhi me pas?
Pastaj zbatova algoritmin Hopcroft-Karp me monada të tjera dhe ky ishte fundi i programit.
Falë Google Summer of Code, fitova përvojë praktike në programimin funksional, i cili jo vetëm që më ndihmoi të merrja një praktikë në Jane Street verën e ardhshme (nuk jam i sigurt se sa i njohur është ky vend edhe në mesin e audiencës me njohuri të Habrit, por është një nga të paktat ku mund të vera për t'u angazhuar në programim funksional), por gjithashtu më njohu me botën e mrekullueshme të zbatimit të kësaj paradigme në praktikë, dukshëm e ndryshme nga përvoja ime në gjuhët tradicionale.
Burimi: www.habr.com