Prošlo ljeto sam sudjelovao u - program za studente iz Googlea. Svake godine organizatori odabiru nekoliko projekata otvorenog koda, uključujući projekte poznatih organizacija kao što su и . Google poziva studente iz cijelog svijeta da rade na ovim projektima.
Kao sudionik Google Summer of Code 2019. napravio sam projekt unutar knjižnice s organizacijom , koja razvija jezik Haskell - jedan od najpoznatijih funkcionalnih programskih jezika. Alga je knjižnica koja predstavlja prikaz za grafove u Haskell-u. Koristi se, na primjer, u — Github biblioteka koja gradi semantička stabla, grafove poziva i ovisnosti na temelju koda i može ih usporediti. Moj projekt je bio dodati reprezentaciju sigurnu za tip za bipartitne grafove i algoritme za tu reprezentaciju.
U ovom postu govorit ću o svojoj implementaciji algoritma za provjeru bipartitnosti grafa u Haskell-u. Iako je algoritam jedan od najosnovnijih, za njegovu prekrasnu implementaciju u funkcionalnom stilu trebalo mi je nekoliko iteracija i dosta posla. Kao rezultat toga, odlučio sam se za implementaciju s monad transformatorima.
O meni
Moje ime je Vasilij Alferov, student sam četvrte godine na HSE u Sankt Peterburgu. Ranije u blogu sam napisao и . Trenutno sam na praksi u u Norveškoj, gdje radim na pristupima problemu . Moji interesi uključuju parametrizirane algoritme i funkcionalno programiranje.
O implementaciji algoritma
predgovor
Studenti koji sudjeluju u programu snažno se potiču na blogovanje. Osigurali su mi platformu za blog . Ovaj članak je prijevod , koju sam napisao tamo u srpnju na engleskom jeziku, s kratkim predgovorom.
Pull Request s dotičnim kodom se može pronaći .
O rezultatima mog rada možete pročitati (na engleskom) .
Ovaj post je namijenjen upoznavanju čitatelja s osnovnim konceptima funkcionalnog programiranja, iako ću se pokušati prisjetiti svih korištenih pojmova kada za to dođe vrijeme.
Provjera bipartitnosti grafova
Algoritam za provjeru bipartitnosti grafa obično se daje u tečaju algoritama kao jedan od najjednostavnijih algoritama za grafove. Njegova ideja je jednostavna: prvo nekako stavimo vrhove u lijevi ili desni dio, a kada se pronađe sukobljeni brid, tvrdimo da graf nije bipartitan.
Još malo detalja: prvo stavimo neki vrh u lijevi dio. Očito, svi susjedi ovog vrha moraju ležati u desnom režnju. Nadalje, svi susjedi susjeda ovog vrha moraju ležati u lijevom režnju, i tako dalje. Nastavljamo s dodjeljivanjem dionica vrhovima sve dok još postoje vrhovi u povezanoj komponenti vrha s kojim smo započeli, a kojima nismo dodijelili susjede. Zatim ponavljamo ovu radnju za sve povezane komponente.
Ako postoji brid između vrhova koji padaju u istu particiju, nije teško pronaći neparan ciklus u grafu, što je nadaleko poznato (i sasvim očito) nemoguće u bipartitnom grafu. Inače, imamo ispravnu particiju, što znači da je graf bipartitan.
Obično se ovaj algoritam implementira pomoću ili . U imperativnim jezicima obično se koristi dubinsko pretraživanje jer je malo jednostavnije i ne zahtijeva dodatne strukture podataka. Također sam odabrao dubinsko pretraživanje jer je tradicionalnije.
Tako smo došli do sljedeće sheme. Prelazimo vrhove grafa koristeći pretragu najprije u dubinu i dodjeljujemo im udjele, mijenjajući broj udjela dok se krećemo duž ruba. Ako pokušamo dodijeliti dionicu vrhu kojem je već dodijeljena dionica, možemo sa sigurnošću reći da graf nije bipartitan. Onog trenutka kada se svim vrhovima dodijeli udio i kada pogledamo sve rubove, imamo dobru particiju.
Čistoća izračuna
U Haskell-u pretpostavljamo da su svi izračuni čist. Međutim, da je to doista tako, ne bismo imali načina ispisati bilo što na ekranu. Uopće, čist kalkulacije su toliko lijene da ih nema čist razloga da se nešto izračuna. Svi izračuni koji se događaju u programu su nekako prisiljeni "nečist" monada IO.
Monade su način predstavljanja izračuna učinci u Haskell-u. Objašnjavanje načina na koji rade je izvan dosega ovog posta. Dobar i jasan opis može se pročitati na engleskom jeziku .
Ovdje želim istaknuti da dok su neke monade, kao što je IO, implementirane kroz magiju prevoditelja, gotovo sve druge su implementirane u softveru i svi izračuni u njima su čisti.
Ima puno efekata i svaki ima svoju monadu. Ovo je vrlo snažna i lijepa teorija: sve monade implementiraju isto sučelje. Govorit ćemo o sljedeće tri monade:
- Ili je ea izračun koji vraća vrijednost tipa a ili izbacuje iznimku tipa e. Ponašanje ove monade vrlo je slično rukovanju iznimkama u imperativnim jezicima: pogreške se mogu uhvatiti ili proslijediti. Glavna razlika je u tome što je monada potpuno logično implementirana u standardnoj biblioteci u Haskell-u, dok imperativni jezici obično koriste mehanizme operativnog sustava.
- Stanje sa je izračun koji vraća vrijednost tipa a i ima pristup promjenjivom stanju tipa s.
- možda a. Monada Maybe izražava računanje koje se može prekinuti u bilo kojem trenutku vraćanjem Ništa. No, govorit ćemo o implementaciji klase MonadPlus za tip Maybe, koja izražava suprotan učinak: to je izračun koji se može prekinuti u bilo kojem trenutku vraćanjem određene vrijednosti.
Implementacija algoritma
Imamo dva tipa podataka, Graph a i Bigraph ab, od kojih prvi predstavlja grafove s vrhovima označenim vrijednostima tipa a, a drugi predstavlja bipartitne grafove s lijevim vrhovima označenim vrijednostima tipa a i desnim -bočni vrhovi označeni vrijednostima tipa b.
Ovo nisu tipovi iz biblioteke Alga. Alga nema reprezentaciju za neusmjerene bipartitne grafove. Napravio sam ovakve vrste radi jasnoće.
Trebat će nam i pomoćne funkcije sa sljedećim potpisima:
-- Список соседей данной вершины.
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)Lako je vidjeti da ako smo tijekom dubinske pretrage pronašli konfliktni rub, neparni ciklus leži na vrhu rekurzivnog stoga. Dakle, da bismo ga vratili, moramo odrezati sve od rekurzijskog stoga do prvog pojavljivanja posljednjeg vrha.
Implementiramo dubinsko pretraživanje održavajući asocijativni niz brojeva udjela za svaki vrh. Rekurzivni stog automatski će se održavati kroz implementaciju klase Functor monade koju smo odabrali: samo ćemo trebati staviti sve vrhove iz staze u rezultat koji vraća rekurzivna funkcija.
Moja prva ideja bila je upotrijebiti monadu Either, za koju se čini da implementira upravo one efekte koji su nam potrebni. Prva implementacija koju sam napisao bila je vrlo bliska ovoj opciji. Zapravo, u jednom sam trenutku imao pet različitih implementacija i na kraju sam se odlučio za drugu.
Prvo, moramo održavati asocijativni niz identifikatora dijeljenja - ovo je nešto o državi. Drugo, moramo biti u mogućnosti zaustaviti se kad se otkrije sukob. Ovo može biti Monad za Ili ili MonadPlus za Možda. Glavna razlika je u tome što Ili može vratiti vrijednost ako izračun nije zaustavljen, a Možda vraća samo informacije o tome u ovom slučaju. Budući da nam nije potrebna zasebna vrijednost za uspjeh (već je pohranjena u State), odabiremo Možda. I u trenutku kada trebamo spojiti učinke dviju monada, one izlaze , koji upravo kombiniraju ove učinke.
Zašto sam odabrao tako složen tip? Dva razloga. Prvo, ispada da je provedba vrlo slična imperativu. Drugo, trebamo manipulirati povratnom vrijednošću u slučaju sukoba kada se vraćamo iz rekurzije kako bismo vratili neparnu petlju, što je puno lakše učiniti u Maybe monadi.
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 <- 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)
Blok where je srž algoritma. Pokušat ću objasniti što se unutar njega događa.
- inVertex je dio dubinske pretrage gdje prvi put posjećujemo vrh. Ovdje dodjeljujemo dionički broj vrhu i izvodimo onEdge na svim susjedima. Ovdje također vraćamo stog poziva: ako je msum vratio vrijednost, tamo guramo vrh v.
- onEdge je dio gdje posjećujemo rub. Poziva se dva puta za svaki rub. Ovdje provjeravamo je li vrh s druge strane posjećen i posjećujemo ga ako nije. Ako se posjeti, provjeravamo je li rub u sukobu. Ako jest, vraćamo vrijednost - sam vrh rekurzivnog stoga, gdje će se nakon povratka smjestiti svi ostali vrhovi.
- processVertex provjerava za svaki vrh je li posjećen i pokreće inVertex na njemu ako nije.
- dfs pokreće processVertex na svim vrhovima.
To je sve.
Povijest riječi INLINE
Riječ INLINE nije bila u prvoj implementaciji algoritma, pojavila se kasnije. Kad sam pokušao pronaći bolju implementaciju, otkrio sam da je verzija koja nije INLINE bila primjetno sporija na nekim grafikonima. S obzirom da bi semantički funkcije trebale raditi isto, to me jako iznenadilo. Što je još čudnije, na drugom stroju s drugom verzijom GHC-a nije bilo primjetne razlike.
Nakon što sam proveo tjedan dana čitajući GHC Core izlaz, uspio sam riješiti problem s jednim redom eksplicitnog INLINE-a. U nekom trenutku između GHC 8.4.4 i GHC 8.6.5 optimizator je to sam prestao raditi.
Nisam očekivao da ću naići na takvu prljavštinu u Haskell programiranju. Međutim, i danas optimizatori ponekad griješe, a naš je posao da im damo savjete. Na primjer, ovdje znamo da funkcija treba biti ugrađena jer je ugrađena u imperativnoj verziji, a to je razlog da prevoditelju damo savjet.
Što se dogodilo sljedeće?
Zatim sam implementirao Hopcroft-Karp algoritam s drugim monadama i to je bio kraj programa.
Zahvaljujući Google Summer of Code stekao sam praktično iskustvo u funkcionalnom programiranju, što mi je pomoglo ne samo da sljedećeg ljeta dobijem staž u Jane Street (nisam siguran koliko je ovo mjesto poznato čak i među upućenom publikom Habra, ali jedno je od od rijetkih gdje možete ljetovati da biste se bavili funkcionalnim programiranjem), ali me također uveo u prekrasan svijet primjene ove paradigme u praksi, bitno drugačije od mog iskustva u tradicionalnim jezicima.
Izvor: www.habr.com