Minulé leto som sa zúčastnil - program pre študentov od spoločnosti Google. Organizátori každoročne vyberajú niekoľko Open Source projektov, a to aj od takých známych organizácií, ako sú и . Google pozýva študentov z celého sveta, aby pracovali na týchto projektoch.
Ako účastník Google Summer of Code 2019 som robil projekt v rámci knižnice s organizáciou , ktorá vyvíja jazyk Haskell – jeden z najznámejších funkcionálnych programovacích jazykov. Alga je knižnica, ktorá predstavuje reprezentácia pre grafy v Haskell. Používa sa napríklad v — knižnica Github, ktorá vytvára sémantické stromy, grafy volaní a závislostí na základe kódu a dokáže ich porovnávať. Mojím projektom bolo pridať typovo bezpečnú reprezentáciu pre bipartitné grafy a algoritmy pre túto reprezentáciu.
V tomto príspevku budem hovoriť o mojej implementácii algoritmu na kontrolu bipartitnosti grafu v Haskell. Aj keď je algoritmus jedným z najzákladnejších, jeho implementácia vo funkčnom štýle mi zabrala niekoľko iterácií a vyžadovala si pomerne veľa práce. V dôsledku toho som sa rozhodol pre implementáciu s monádovými transformátormi.
O mne
Volám sa Vasilij Alferov, som študentom štvrtého ročníka na HSE v Petrohrade. Predtým v blogu, ktorý som napísal и . Momentálne som na stáži u v Nórsku, kde pracujem na prístupoch k problému . Medzi moje záujmy patria parametrizované algoritmy a funkcionálne programovanie.
O implementácii algoritmu
Predslov
Študentom, ktorí sa zúčastňujú programu, dôrazne odporúčame blogovať. Poskytli mi platformu pre blog . Tento článok je prekladom , ktorú som tam napísal v júli v angličtine, s krátkym predslovom.
Môžete nájsť požiadavku na stiahnutie s príslušným kódom .
O výsledkoch mojej práce si môžete prečítať (v angličtine) .
Účelom tohto príspevku je oboznámiť čitateľa so základnými pojmami vo funkčnom programovaní, aj keď sa pokúsim pripomenúť všetky použité pojmy, keď príde čas.
Kontrola bipartitnosti grafov
Algoritmus na kontrolu bipartitnosti grafu je zvyčajne uvedený v kurze o algoritmoch ako jeden z najjednoduchších grafových algoritmov. Jeho myšlienka je jednoduchá: najprv nejakým spôsobom vložíme vrcholy do ľavého alebo pravého podielu a keď sa nájde konfliktná hrana, tvrdíme, že graf nie je bipartitný.
Trochu podrobnejšie: najprv vložíme nejaký vrchol do ľavého podielu. Je zrejmé, že všetci susedia tohto vrcholu musia ležať v pravom laloku. Ďalej, všetci susedia susedov tohto vrcholu musia ležať v ľavom laloku atď. Pokračujeme v priraďovaní podielov k vrcholom, pokiaľ sú v pripojenom komponente vrcholu, s ktorým sme začali, ešte vrcholy, ku ktorým sme nepriradili susedov. Túto akciu potom zopakujeme pre všetky pripojené komponenty.
Ak existuje hrana medzi vrcholmi, ktoré spadajú do rovnakej partície, nie je ťažké nájsť v grafe nepárny cyklus, čo je všeobecne známe (a celkom evidentne) nemožné v bipartitnom grafe. V opačnom prípade máme správne rozdelenie, čo znamená, že graf je bipartitný.
Typicky sa tento algoritmus implementuje pomocou alebo . V imperatívnych jazykoch sa zvyčajne používa hĺbkové vyhľadávanie, pretože je o niečo jednoduchšie a nevyžaduje ďalšie dátové štruktúry. Vybral som si tiež vyhľadávanie do hĺbky, pretože je tradičnejšie.
Tak sme sa dostali k nasledujúcej schéme. Prechádzame vrcholy grafu pomocou hĺbkového vyhľadávania a priraďujeme k nim podiely, pričom meníme číslo podielu, keď sa pohybujeme po okraji. Ak sa pokúsime priradiť podiel k vrcholu, ktorý už má podiel priradený, môžeme pokojne povedať, že graf nie je bipartitný. V momente, keď je všetkým vrcholom priradený podiel a my sme sa pozreli na všetky hrany, máme dobrú partíciu.
Čistota výpočtov
V Haskell predpokladáme, že všetky výpočty sú čisté. Ak by to však naozaj tak bolo, nemali by sme ako vytlačiť čokoľvek na obrazovku. Vôbec, čistý výpočty sú také lenivé, že neexistuje ani jeden čisté dôvody niečo vypočítať. Všetky výpočty vyskytujúce sa v programe sú nejakým spôsobom nútené "nečistý" monad IO.
Monády predstavujú spôsob, ako reprezentovať výpočty pomocou účinky v meste Haskell. Vysvetlenie, ako fungujú, je nad rámec tohto príspevku. Dobrý a jasný popis je možné prečítať v angličtine .
Tu chcem poukázať na to, že kým niektoré monády, ako napríklad IO, sú implementované cez kompilátorovú mágiu, takmer všetky ostatné sú implementované softvérovo a všetky výpočty v nich sú čisté.
Existuje veľa efektov a každý má svoju vlastnú monádu. Toto je veľmi silná a krásna teória: všetky monády implementujú rovnaké rozhranie. Budeme hovoriť o nasledujúcich troch monádach:
- Buď je ea výpočet, ktorý vráti hodnotu typu a, alebo vyvolá výnimku typu e. Správanie tejto monády je veľmi podobné obsluhe výnimiek v imperatívnych jazykoch: chyby možno zachytiť alebo preniesť ďalej. Hlavným rozdielom je, že monáda je úplne logicky implementovaná v štandardnej knižnici v Haskell, zatiaľ čo imperatívne jazyky zvyčajne používajú mechanizmy operačného systému.
- Stav sa je výpočet, ktorý vracia hodnotu typu a a má prístup k meniteľnému stavu typu s.
- Možno a. Monáda Maybe vyjadruje výpočet, ktorý možno kedykoľvek prerušiť vrátením Nič. Budeme sa však baviť o implementácii triedy MonadPlus pre typ Maybe, ktorá vyjadruje opačný efekt: ide o výpočet, ktorý je možné kedykoľvek prerušiť vrátením konkrétnej hodnoty.
Implementácia algoritmu
Máme dva typy údajov, Graph a a Bigraph ab, z ktorých prvý predstavuje grafy s vrcholmi označenými hodnotami typu a a druhý predstavuje bipartitné grafy s ľavostrannými vrcholmi označenými hodnotami typu a a vpravo. -bočné vrcholy označené hodnotami typu b.
Toto nie sú typy z knižnice Alga. Alga nemá reprezentáciu pre neorientované bipartitné grafy. Pre prehľadnosť som urobil takéto typy.
Budeme tiež potrebovať pomocné funkcie s nasledujúcimi podpismi:
-- Список соседей данной вершины.
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)Je ľahké vidieť, že ak sme počas hĺbkového vyhľadávania našli konfliktnú hranu, nepárny cyklus leží na vrchu rekurzného zásobníka. Preto, aby sme ho obnovili, musíme odrezať všetko od zásobníka rekurzie až po prvý výskyt posledného vrcholu.
Implementujeme hĺbkové vyhľadávanie udržiavaním asociatívneho poľa čísel zdieľania pre každý vrchol. Zásobník rekurzie bude automaticky udržiavaný prostredníctvom implementácie triedy Functor monády, ktorú sme si vybrali: budeme musieť vložiť všetky vrcholy z cesty do výsledku vráteného z rekurzívnej funkcie.
Mojou prvou myšlienkou bolo použiť buď monádu, ktorá podľa všetkého implementuje presne tie efekty, ktoré potrebujeme. Prvá implementácia, ktorú som napísal, bola veľmi blízko tejto možnosti. V skutočnosti som mal v jednom bode päť rôznych implementácií a nakoniec som sa rozhodol pre inú.
Po prvé, musíme udržiavať asociatívne pole identifikátorov zdieľania - to je niečo o štáte. Po druhé, musíme byť schopní zastaviť sa, keď sa zistí konflikt. Môže to byť buď Monad pre Either, alebo MonadPlus pre Maybe. Hlavný rozdiel je v tom, že Buď môže vrátiť hodnotu, ak výpočet nebol zastavený, a Maybe v tomto prípade vráti iba informácie o tomto. Keďže pre úspech nepotrebujeme samostatnú hodnotu (je už uložená v State), zvolíme Možno. A v momente, keď potrebujeme spojiť účinky dvoch monád, vychádzajú , ktoré presne kombinujú tieto účinky.
Prečo som si vybral taký komplexný typ? Dva dôvody. Po prvé, implementácia sa ukazuje ako veľmi podobná imperatívu. Po druhé, musíme manipulovať s návratovou hodnotou v prípade konfliktu pri návrate z rekurzie, aby sme obnovili nepárnu slučku, čo je oveľa jednoduchšie urobiť v Monáde Maybe.
Tak získame túto implementáciu.
{-# 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 kde je jadrom algoritmu. Pokúsim sa vysvetliť, čo sa v ňom deje.
- inVertex je časť hĺbkového vyhľadávania, kde po prvýkrát navštívime vrchol. Tu priradíme vertexu číslo zdieľania a spustíme onEdge na všetkých susedoch. Tu tiež obnovíme zásobník hovorov: ak msum vrátil hodnotu, vložíme tam vrchol v.
- onEdge je časť, kde navštívime hranu. Pre každú hranu sa volá dvakrát. Tu skontrolujeme, či bol vrchol na druhej strane navštívený a ak nie, navštívime ho. Pri návšteve skontrolujeme, či je okraj v rozpore. Ak je, vrátime hodnotu – samý vrch zásobníka rekurzie, kde sa potom po návrate umiestnia všetky ostatné vrcholy.
- processVertex skontroluje pre každý vrchol, či bol navštívený, a ak nie, spustí na ňom inVertex.
- dfs spustí processVertex na všetkých vrcholoch.
To je všetko.
História slova INLINE
Slovo INLINE nebolo pri prvej implementácii algoritmu, objavilo sa až neskôr. Keď som sa snažil nájsť lepšiu implementáciu, zistil som, že neINLINE verzia bola na niektorých grafoch citeľne pomalšia. Vzhľadom na to, že sémanticky by funkcie mali fungovať rovnako, ma to veľmi prekvapilo. Čo je ešte zvláštnejšie, na inom stroji s inou verziou GHC nebol badateľný rozdiel.
Po týždni strávenom čítaním výstupu GHC Core sa mi podarilo problém vyriešiť jedným riadkom explicitného INLINE. V určitom bode medzi GHC 8.4.4 a GHC 8.6.5 to optimalizátor prestal robiť sám.
Nečakal som, že sa v programovaní Haskellu stretnem s takouto špinou. Aj dnes však optimalizátori niekedy robia chyby a našou úlohou je dať im rady. Napríklad tu vieme, že funkcia by mala byť vložená, pretože je vložená v imperatívnej verzii, a to je dôvod, aby sme kompilátorovi pomohli.
Čo sa stalo ďalej?
Potom som implementoval Hopcroft-Karpov algoritmus s inými monádami a to bol koniec programu.
Vďaka Google Summer of Code som nadobudol praktické skúsenosti s funkčným programovaním, ktoré mi pomohli nielen získať stáž na Jane Street nasledujúce leto (nie som si istý, nakoľko je toto miesto známe aj medzi Habrovým znalým publikom, ale je to jedno z mála, kde sa môžete v lete venovať funkcionálnemu programovaniu), ale zároveň ma zaviedli do úžasného sveta aplikácie tejto paradigmy v praxi, výrazne odlišnej od mojich skúseností s tradičnými jazykmi.
Zdroj: hab.com