Minulém poletju sem sodeloval v — programu za študente podjetja Google. Letno organizatorji izberejo nekaj projektov Open Source, vključno s tistimi znanih organizacij, kot so in . Za delo na teh projektih Google povabi študente z vsega sveta.
Kot udeleženec Google Summer of Code 2019 sem delal na projektu v okviru knjižnice z organizacijo , ki se ukvarja z razvojem jezika Haskell — ene najbolj znanih funkcionalnih programskih jezikov. Alga — knjižnica, ki predstavlja predstavljanje grafov v Haskellu. Uporablja se, na primer, v — knjižnici podjetja Github, ki gradi semantična drevesa, grafov klicev in odvisnosti ter jih zna primerjati. Moj projekt je bil dodajanje tipovno varnega predstavitve za dvočlene grafe in algoritme za to predstavitev.
V objavi bom predstavil svojo implementacijo algoritma za preverjanje grafa na dvočnost v Haskellu. Kljub temu, da je algoritma ena najbolj osnovnih, je bila njegova lepa implementacija v funkcionalnem slogu zame precej zamudna in zahtevala veliko dela. Na koncu sem se odločil za implementacijo s transformatorji monad.
O meni
Moje ime je Vasiliy Alfërov, sem študent četrtega letnika na Peterburški višji šoli. Prej sem na blogu pisal in . Ravno zdaj sem na praktikantskem usposabljanju na na Norveškem, kjer se ukvarjam z metodami za nalogo . Moji interesi vključujejo parametizirane algoriteme in funkcionalno programiranje.
O implementaciji algoritma
Predgovor
Študentom, ki sodelujejo v programu, se toplo priporoča, da vodijo blog. Za moj blog so mi zagotovili platformo . Ta članek je prevod , ki sem ga napisal tja julija v angleščini, z majhnim uvodom.
Pull Request s kodo, o kateri teče beseda, lahko najdete .
O rezultatih svojega dela lahko preberete (v angleščini) .
Objava predvideva, da je bralec seznanjen z osnovnimi pojmi funkcionalnega programiranja, čeprav se bom potrudil, da spomnim na vse uporabljene termine, ko bo prišel čas.
Preverjanje grafov na dvočnost
Algoritem za preverjanje grafov na bipartitnost se običajno predstavi v tečaju algoritmov kot enega najpreprostejših grafovskih algoritmov. Njegova ideja je enostavna: najprej kako koli položimo vozlišča v levo ali desno skupino, nato pa, ko odkrijemo konfliktno rob, trdimo, da graf ni bipartiten.
Malce podrobneje: najprej položimo neko vozlišče v levo skupino. Očitno morajo vsi sosedje tega vozlišča ležati v desni skupini. Nadalje morajo vsi sosedje sosedov tega vozlišča ležati v levi skupini in tako naprej. Nadaljujemo s dodeljevanjem skupin vozliščem, dokler v komponenti povezanosti vozlišča, s katerim smo začeli, še obstajajo vozlišča, ki nimajo dodeljenih sosedov. Nato to dejanje ponovimo za vse komponente povezanosti.
Če obstaja rob med vozlišči, ki sta prišli v isto skupino, ni težko najti v grafu lično cikla, kar je splošno znano (in kar je dovolj očitno) kot nemogoče v bipartitnem grafu. Drugače imamo pravilno razdelitev na skupine, kar pomeni, da je graf bipartiten.
Običajno se ta algoritem implementira s ili . V imperativnih jezikih se običajno uporablja globinsko iskanje, ki je nekoliko preprostejše in ne zahteva dodatnih podatkovnih struktur. Tudi jaz sem izbral globinsko iskanje kot bolj tradicionalno.
Tako smo prišli do naslednje sheme. S pomočjo globinskega iskanja prehajamo vozlišča grafa in jim dodeljujemo skupine, pri čemer spremenimo številko skupine, ko preidemo preko roba. Če poskušamo dodeliti skupino vozlišču, katerega skupina je že dodeljena, lahko mirno trdimo, da graf ni bipartiten. Ob trenutku, ko so vsem vozliščem dodeljene skupine in smo pogledali vse robove, imamo dobro razdelitev.
Čistost izračunov
V Haskellu predpostavljamo, da so vsi izračuni čisti. Vendar, če bi to dejansko bilo tako, ne bi imeli možnosti natisniti česar koli na ekran. Na splošno, čisti izračuni so tako leni, da ni nobene čiste razlage za izračun. Vsi izračuni, ki se odvijajo v programu, so nekako prisiljeni v »nečisto« monado IO.
Monade so način predstavitve izračunov z učinki v Haskellu. Razlaga, kako delujejo, presega to objavo. Dobre in jasne razlage lahko preberete v angleščini. .
Tukaj želim poudariti, da medtem ko so nekatere monade, kot je IO, uresničene s pomočjo čarovnije prevajalnika, so skoraj vse druge uresničene programsko in vse izračune v njih so čisti.
Učinki so lahko zelo različni, vsak ima svojo monado. To je zelo močna in lepa teorija: vse monade implementirajo isti vmesnik. Govorili bomo o naslednjih treh monadah:
- Either e a — izračun, ki vrne vrednost tipa a ali vrže izjemo tipa e. Obnašanje te monade je zelo podobno delu z izjemami v imperativnih jezikih: napake lahko ujamemo ali preusmerimo. Glavna razlika je, da je monada popolnoma logično implementirana v standardni knjižnici v istem Haskellu, medtem ko v imperativnih jezikih običajno uporabljamo mehanizme operacijskega sistema.
- State s a — izračun, ki vrne vrednost tipa a in ima dostop do spremenljivega stanja tipa s.
- Maybe a. Monada Maybe izraža izračun, ki ga je mogoče kadar koli prekiniti z vrnitvijo Nothing. Vendar bomo govorili o implementaciji razreda MonadPlus za tip Maybe, ki izraža nasproten učinek: to je izračun, ki ga je mogoče kadar koli prekiniti z vrnitvijo konkretne vrednosti.
Implementacija algoritma
Imamo dva tipa podatkov, Graph a in Bigraph a b, pri čemer prvi predstavlja grafe z vozlišči, označenimi z vrednostmi tipa a, drugi pa predstavlja bipartitne grafe z vozlišči leve strani, označenimi z vrednostmi tipa a, in vozlišči desne strani, označenimi z vrednostmi tipa b.
To niso tipi iz knjižnice Alga. V Algi ni predstavitve za nenaperjene bipartitne grafe. Te tipe sem zasnoval za boljšo preglednost.
Potrebovali bomo tudi pomožne funkcije z naslednjimi signaturami:
-- Seznam sosedov te točke.
neighbours :: Ord a => a -> Graph a -> [a]
-- Zgradite bipartitni graf iz grafa in funkcije, ki za vsako točko
-- vrne njen del in oznako v novi del, pri čemer ignorira konfliktne robove.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Seznam točk v grafu
vertexList :: Ord a => Graph a -> [a]
Podpis funkcije, ki jo bomo napisali, izgleda takole:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Ni težko opaziti, da če med iskanjem globine najdemo konfliktni rob, se liha zanka nahaja na vrhu sklada rekurzije. Zato, da jo obnovimo, moramo odrezati vse pri skladu rekurzije do prvega pojava zadnje točke.
Izvedli bomo iskanje globine, pri čemer bomo vzdrževali asociativno tabelo števil del za vsako točko. Sklad rekurzije bo avtomatsko podprt skozi implementacijo razreda Functor izbrane monade: preprosto bomo morali dodati vse točke iz poti v rezultat, ki ga vrne rekursivna funkcija.
Prva ideja je bila uporabiti monado Either, ki naj bi uresničila učinke, ki jih potrebujemo. Prva izvedba, ki sem jo napisal, je bila zelo bližnja tej različici. Dejansko sem v nekem trenutku imel pet različnih izvedb, na koncu pa sem se odločil za drugo.
Najprej moramo vzdrževati asociativno tabelo identifikatorjev del — to je nekaj, kar se nanaša na State. Drugič, moramo biti sposobni ustaviti se v primeru odkritja konflikta. To je lahko bodisi Monad za Either, bodisi MonadPlus za Maybe. Glavna razlika je, da lahko Either vrne vrednost, če izračun ni bil ustavljen, medtem ko Maybe v takem primeru vrne le informacijo o tem. Ker ne potrebujemo ločene vrednosti v primeru uspeha (ta je že shranjena v State), izberemo Maybe. Ob trenutku, ko moramo kombinirati učinke dveh monad, se pokažejo , ki prav kombinirajo te učinke.
Zakaj sem izbral tako zapleteno vrsto? Dva razloga. Prvič, implementacija je zelo podobna imperativni. Drugič, potrebujemo manipulirati z vrednostjo, ki se vrne v primeru konflikta, pri vrnitvi iz rekurzije za obnovitev ličnega cikla, kar je veliko lažje izvajati z monado Maybe.
Tako dobimo takšno implementacijo.
{-# 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` je jedro algoritma. Poskušal bom razložiti, kaj se znotraj njega dogaja.
- inVertex je del iskanja po globini, kjer prvič obiščemo vozlišče. Tu dodelimo vozlišču številko dela in za vse sosede zagnamo onEdge. To je tudi mesto, kjer obnavljamo sklad klicev: če je msum vrnil vrednost, dodamo vozlišče v.
- onEdge — to je del, kjer obiščemo rob. Klican je dvakrat za vsak rob. Tukaj preverimo, ali je bil vrh obiskovan z druge strani in ga obiščemo, če ni. Če je bil obiskovan, preverimo, ali je rob konfliktni. Če je, vrnemo vrednost — vrhnjo vrednost na vrhu rekurzivnega sklada, na katero se nato ob vrnitvi pripnejo vsi ostali vrhovi.
- processVertex preverja za vsak vrh, ali je bil obiskovan, in ga zažene na inVertex, če ni.
- dfs zažene processVertex na vseh vrhovih.
To je vse.
Zgodovina besede INLINE
Besede INLINE ni bilo v prvi različici algoritma, pojavila se je kasneje. Ko sem poskušal najti boljšo implementacijo, sem odkril, da na nekaterih grafih različica brez INLINE deluje opazno počasneje. Glede na to, da bi morale funkcije semantično delovati enako, me je to zelo presenetilo. Še bolj nenavadno je bilo, da na drugem računalniku z drugo različico GHC ni bilo opazne razlike.
Potem ko sem preživel teden dni branja izhoda GHC Core, sem uspel rešiti težavo z enim stavkom z jasnim INLINE. Nekje med GHC 8.4.4 in GHC 8.6.5 optimizator tega ni več počel samodejno.
Nisem pričakoval, da bom naletel na tako umazanijo pri programiranju v Haskellu. Vendar pa optimizatorji tudi danes včasih naredijo napake, in dajati jim namige — je naša naloga. Na primer, tukaj vemo, da bi morala biti funkcija zainlinena, saj je bila zainlinena v imperativni različici, in to je razlog, da damo prevajalniku namig.
Kaj se je zgodilo naprej?
Nato sem implementiral Hopcroft-Karpov algoritem že z drugimi monadami in s tem je program končan.
Zahvaljujoč Google Summer of Code sem pridobil praktične izkušnje v funkcionalnem programiranju, ki so mi ne le pomagale priti na prakso v Jane Street naslednje poletje (nisem prepričan, kako znano je to mesto celo med poznavalci Habr, vendar je eno redkih, kjer se lahko poleti ukvarjate s funkcionalnim programiranjem), ampak so me tudi seznanile z neverjetnim svetom uporabe te paradigme v praksi, kar se je znatno razlikovalo od mojih izkušenj s tradicionalnimi jeziki.
Izvor: habr.com
