Prošlog ljeta sudjelovao sam u — programu za studente koji organizira Google. Svake godine organizatori odabiru nekoliko Open Source projekata, uključujući i one poznatih organizacija poput i . Za rad na tim projektima Google poziva studente iz cijelog svijeta.
Kao sudionik Google Summer of Code 2019, radio sam na projektu unutar biblioteke s organizacijom , koja se bavi razvojem Haskell jezika — jednog od najpoznatijih funkcionalnih programskih jezika. Alga — biblioteka koja predstavlja predstavljanje grafova u Haskellu. Koristi se, na primjer, u — biblioteci kompanije Github, koja gradi semantička stabla, grafove poziva i zavisnosti i može ih uspoređivati. Moj projekt se sastojao od dodavanja tipovno sigurnog prikaza za bipartitne grafove i algoritama za tu reprezentaciju.
U ovom postu ću govoriti o svojoj implementaciji algoritma za provjeru bipartitnosti grafa u Haskellu. Iako je algoritam jedan od najosnovnijih, njegova lijepa implementacija u funkcionalnom stilu zahtijevala je nekoliko iteracija i prilično mnogo rada. Na kraju sam se odlučio za implementaciju s monadskim transformatorima.
O meni
Moje ime je Vasiliy Alfjorov, student sam četvrte godine Peterburške visoke škole. Prije sam u blogu pisao i . Trenutno sam na praksi na u Norveškoj, gdje se bavim pristupima zadatku . Moji interesi uključuju parametritzovane algoritme i funkcionalno programiranje.
O implementaciji algoritma
Predgovor
Studentima koji sudjeluju u programu toplo se preporučuje vođenje bloga. Dobio sam platformu za blog . Ovaj članak je prijevod , koji sam napisao tamo u srpnju na engleskom jeziku, s malim uvodom.
Pull Request s kodom o kojem se radi može se pronaći .
O rezultatima mog rada možete pročitati (na engleskom) .
Post pretpostavlja upoznavanje čitatelja s osnovnim pojmovima u funkcionalnom programiranju, iako ću se potruditi podsjetiti na sve korištene termine kada dođe vrijeme.
Provjera grafova na bipartitnost
Algoritam provjere grafova na bipartitnost obično se predaje u okviru algoritama kao jedan od najjednostavnijih grafičkih algoritama. Njegova ideja je jednostavna: prvo na neki način stavljamo čvorove u lijevu ili desnu skupinu, a kada se otkrije sukobna grana, tvrdimo da graf nije bipartitan.
Malo detaljnije: prvo stavljamo neki čvor u lijevu skupinu. Očigledno, svi susjedi tog čvora moraju biti u desnoj skupini. Zatim, svi susjedi susjeda tog čvora trebaju biti u lijevoj skupini, i tako dalje. Nastavljamo dodjeljivati čvorovima skupine dok u komponenti povezanosti čvora s kojim smo počeli još ima čvorova kojima nismo dodijelili susjede. Zatim ponavljamo ovu radnju za sve komponente povezanosti.
Ako postoji grana između čvorova koji su završili u istoj skupini, nije teško pronaći u grafu neparni ciklus, što je općenito poznato (i dovoljno očigledno) da je nemoguće u bipartitnom grafu. Inače, imamo ispravnu podjelu na skupine, a to znači da je graf bipartitan.
Kao pravilo, ovaj algoritam se implementira pomoću ili . U imperativnim jezicima obično se koristi dubinsko pretraživanje, koje je malo jednostavnije i ne zahtijeva dodatne strukture podataka. Također, odabrao sam dubinsko pretraživanje kao tradicionalnije.
Tako smo došli do sljedeće sheme. Obilazimo čvorove grafa koristeći dubinsko pretraživanje i dodjeljujemo im skupine, mijenjajući broj skupine prilikom prelaska preko grane. Ako pokušavamo dodijeliti skupinu čvoru kojem je već dodijeljena skupina, možemo slobodno tvrditi da graf nije bipartitan. U trenutku kada su svim čvorovima dodijeljene skupine i pogledali smo sve grane, imamo dobru podjelu.
Čistoća izračuna
U Haskellu pretpostavljamo da su svi izračuni čisti. Međutim, da je to zaista tako, ne bismo imali mogućnost ispisati nešto na ekran. Uopće, čisti izračuni su toliko lenji da ne postoji ni jedan čisti razlog da se nešto izračuna. Svi izračuni koji se odvijaju u programu, na neki način, prisiljeni su u „nečistu” monadu IO.
Monade su način predstavljanja izračuna s efektima u Haskellu. Objašnjenje kako oni rade izlazi iz okvira ove objave. Dobar i jasan opis možete pročitati na engleskom .
Ovde želim napomenuti da, iako su neke monade, poput IO, implementirane pomoću magije kompajlera, gotovo sve ostale su implementirane programerski, a svi izračuni u njima su čisti.
Postoji mnogo efekata i za svaki je određena svoj monada. To je vrlo snažna i lepa teorija: sve monade implementiraju isti interfejs. Govorićemo o sledeće tri monade:
- Either e a — izračunavanje koje vraća vrednost tipa a ili baca izuzetak tipa e. Ponašanje ove monade veoma podseća na rad sa izuzecima u imperativnim jezicima: greške se mogu uhvatiti ili proslediti dalje. Osnovna razlika je u tome što je monada potpuno logički implementirana u standardnoj biblioteci na istoj Haskellu, dok se u imperativnim jezicima obično koriste mehanizmi operativnog sistema.
- State s a — izračunavanje koje vraća vrednost tipa a i ima pristup promenljivom stanju tipa s.
- Maybe a. Monada Maybe izražava izračunavanje koje se može prekinuti vraćanjem Nothing u bilo kojem trenutku. Međutim, govorićemo o implementaciji klase MonadPlus za tip Maybe, koja izražava suprotan efekat: to je izračunavanje koje se može prekinuti vraćanjem konkretne vrednosti u bilo kojem trenutku.
Implementacija algoritma
Imamo dva tipa podataka, Graph a i Bigraph a b, pri čemu prvi predstavlja grafove sa čvorovima označenim vrednostima tipa a, a drugi predstavlja bipartitne grafove sa čvorovima leve strane označenim vrednostima tipa a i čvorovima desne strane označenim vrednostima tipa b.
To nisu tipovi iz biblioteke Alga. U Algi ne postoji predstava za nenapravine bipartitne grafove. Tipove sam napravio ovako radi preglednosti.
Takođe će nam biti potrebne pomoćne funkcije sa sledećim potpisima:
-- Popis susjeda ovog vrha.
susjedi :: Ord a => a -> Graf a -> [a]
-- Izgraditi bipartitni graf na temelju grafa i funkcije koja za svaki vrh
-- vraća njegovu članstvo i oznaku u novoj članstvu, ignorirajući sukobljene rubove.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graf a
-> Bigraf b c
-- Popis vrhova u grafu
popisVrhova :: Ord a => Graf a -> [a]
Potpis funkcije koju ćemo napisati izgleda ovako:
tip NeparniCiklus a = [a]
detectParts :: Ord a => Graf a -> Either (NeparniCiklus a) (Bigraf a a)Nije teško primijetiti da, ako tijekom dubinskog pretraživanja pronađemo sukobljeni rub, neparni ciklus leži na vrhu stoga rekurzije. Stoga, da bismo ga obnovili, trebamo odrezati sve do prvog pojavljivanja posljednjeg vrha iz stoga rekurzije.
Implementirat ćemo dubinsko pretraživanje, održavajući asocijativni niz identifikatora članstva za svaki vrh. Stog rekurzije bit će automatski održavan kroz implementaciju klase Functor odabrane monade: samo će trebati dodati sve vrhove s puta u rezultat koji se vraća iz rekurzivne funkcije.
Moja prva ideja bila je koristiti monadu Either, koja izgleda kao da implementira upravo one efekte koji su nam potrebni. Prva implementacija koju sam napisao bila je vrlo blizu ovoj opciji. Ustvari, imao sam pet različitih implementacija u nekom trenutku, a na kraju sam se odlučio za drugu.
Prvo, trebamo održavati asocijativni niz identifikatora članstva - to je nešto o State-u. Drugo, trebamo biti sposobni stati u slučaju otkrivanja sukoba. To može biti ili Monad za Either, ili MonadPlus za Maybe. Glavna razlika je u tome što Either može vratiti vrijednost u slučaju da izračunavanje nije zaustavljeno, dok Maybe u tom slučaju vraća samo informaciju o tome. Budući da nam ne treba posebna vrijednost u slučaju uspjeha (ona je već pohranjena u State-u), biramo Maybe. A u trenutku kada trebamo kombinirati efekte dviju monada, pojavljuju se , koji upravo kombiniraju te efekte.
Zašto sam odabrao takav složeni tip? Dva razloga. Prvo, implementacija se ispostavlja vrlo sličnom imperativnoj. Drugo, trebamo manipulirati vrijednošću koja se vraća u slučaju sukoba, prilikom povratka iz rekurzije za obnavljanje neparnog ciklusa, a to je mnogo jednostavnije učiniti unutar Maybe monade.
Tako dobivamo ovu implementaciju.
{-# 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)
Blok where — to je jezgra algoritma. Pokušat ću objasniti što se događa unutar njega.
- inVertex — ovo je dio pretraživanja u dubinu, u kojem prvi put posjećujemo čvor. Ovdje dodjeljujemo čvoru broj dijela i pokrećemo onEdge za sve susjede. Također je to mjesto gdje obnavljamo stog poziva: ako msum vrati vrijednost, dodajemo čvor v.
- onEdge je dio gdje posjećujemo rub. Poziva se dvaput za svaki rub. Ovdje provjeravamo je li čvor s druge strane posjećen te ga posjećujemo ako nije. Ako jest posjećen, provjeravamo je li rub konfliktan. Ako jest, vraćamo vrijednost — samu vrh stoga rekurzije, na koju se zatim prilikom povratka naknadno nanose svi ostali čvorovi.
- processVertex provjerava za svaki čvor je li posjećen i pokreće inVertex na njemu ako nije.
- dfs pokreće processVertex na svim čvorovima.
To je to.
Povijest riječi INLINE
Riječ INLINE nije bila u prvoj implementaciji algoritma, pojavila se kasnije. Kada sam pokušavao pronaći bolju implementaciju, otkrio sam da na nekim grafovima verzija bez INLINE radi znatno sporije. S obzirom na to da funkcije trebaju semantički raditi isto, to me jako iznenadilo. Čak je još čudnije što na drugom računalu s drugom verzijom GHC nije bilo primjetne razlike.
Nakon što sam proveo tjedan dana čitajući ispis GHC Core, uspio sam ispraviti problem jednim redkom s eksplicitnim INLINE-om. U nekom trenutku između GHC 8.4.4 i GHC 8.6.5 optimizator to više nije radio automatski.
Nisam očekivao naići na takvu prljavštinu u programiranju u Haskell-u. Međutim, optimizatori i u naše vrijeme ponekad griješe, a davanje savjeta njima je naš zadatak. Na primjer, ovdje znamo da bi funkcija trebala biti in-line, jer je in-line u imperativnoj verziji, i to je razlog da damo savjet prevoditelju.
Što je bilo dalje?
Nakon toga implementirao sam Hopcroft-Karp algoritam s drugim monadama, i time je program završio.
Zahvaljujući Google Summer of Code-u, stekao sam praktično iskustvo u funkcionalnom programiranju, što mi je ne samo pomoglo da prođem na praksu u Jane Street sljedećeg ljeta (nisam siguran koliko je to mjesto poznato čak i među onima koji znaju za Habr, ali to je jedno od rijetkih gdje ljeti možete raditi funkcionalno programiranje), već me i upoznalo s nevjerojatnim svijetom primjene te paradigme u praksi, koja se značajno razlikuje od mog iskustva s tradicionalnim jezicima.
Izvor: habr.com
