Lansko poletje sem sodeloval - program za študente iz Googla. Vsako leto organizatorji izberejo več odprtokodnih projektov, tudi iz tako znanih organizacij, kot je и . Google k sodelovanju pri teh projektih vabi študente z vsega sveta.
Kot udeleženec Google Summer of Code 2019 sem naredil projekt v okviru knjižnice z organizacijo , ki razvija jezik Haskell – enega najbolj znanih funkcijskih programskih jezikov. Alga je knjižnica, ki predstavlja predstavitev za grafe v Haskell-u. Uporablja se na primer v — knjižnica Github, ki gradi semantična drevesa, grafe klicev in odvisnosti na podlagi kode in jih lahko primerja. Moj projekt je bil dodati tipsko varno predstavitev za bipartitne grafe in algoritme za to predstavitev.
V tem prispevku bom govoril o svoji implementaciji algoritma za preverjanje bipartitnosti grafa v Haskell-u. Čeprav je algoritem eden najosnovnejših, sem za njegovo čudovito implementacijo v funkcionalnem slogu potreboval več iteracij in precej dela. Posledično sem se odločil za izvedbo z monadnimi transformatorji.
O sebi
Moje ime je Vasily Alferov, sem študent četrtega letnika na HSE v Sankt Peterburgu. Prej v blogu sem pisal и . Trenutno sem na praksi pri na Norveškem, kjer se ukvarjam s pristopi k problemu . Zanimajo me parametrizirani algoritmi in funkcionalno programiranje.
O izvajanju algoritma
Predgovor
Študente, ki sodelujejo v programu, močno spodbujamo k bloganju. Priskrbeli so mi platformo za blog . Ta članek je prevod , ki sem ga tam julija napisal v angleščini, s kratkim predgovorom.
Najdete lahko Pull Request z zadevno kodo .
O rezultatih mojega dela si lahko preberete (v angleščini) .
Ta objava je namenjena seznanitvi bralca z osnovnimi koncepti funkcionalnega programiranja, čeprav se bom poskušal spomniti vseh uporabljenih izrazov, ko bo čas.
Preverjanje dvodelnosti grafov
Algoritem za preverjanje bipartitnosti grafa je običajno podan v tečaju algoritmov kot eden najpreprostejših algoritmov za graf. Njegova zamisel je enostavna: najprej nekako postavimo vozlišča v levi ali desni delež, in ko najdemo konfliktni rob, trdimo, da graf ni dvodelen.
Še malo podrobnosti: najprej postavimo neko oglišče v levi delež. Očitno morajo vsi sosedje tega vozlišča ležati v desnem režnju. Nadalje morajo vsi sosedje sosedov tega vozlišča ležati v levem režnju in tako naprej. Nadaljujemo z dodeljevanjem deležev vozliščem, dokler v povezani komponenti vozlišča, s katerim smo začeli, še vedno obstajajo vozlišča, ki jim nismo dodelili sosedov. To dejanje nato ponovimo za vse povezane komponente.
Če obstaja rob med vozlišči, ki spadajo v isto particijo, ni težko najti lihega cikla v grafu, kar je splošno znano (in povsem očitno) nemogoče v bipartitnem grafu. V nasprotnem primeru imamo pravilno razbitje, kar pomeni, da je graf dvodelen.
Običajno se ta algoritem izvaja z uporabo ali . V imperativnih jezikih se običajno uporablja iskanje v globino, saj je nekoliko preprostejše in ne zahteva dodatnih podatkovnih struktur. Izbral sem tudi iskanje najprej v globino, saj je bolj tradicionalno.
Tako smo prišli do naslednje sheme. Prečkamo vozlišča grafa z iskanjem najprej v globino in jim dodelimo deleže, pri čemer spreminjamo številko deleža, ko se premikamo po robu. Če poskušamo dodeliti delež vozlišču, ki že ima dodeljen delež, lahko mirno rečemo, da graf ni bipartiten. V trenutku, ko je vsem vozliščem dodeljen delež in smo pogledali vse robove, imamo dobro particijo.
Čistost izračunov
V Haskellu predpostavljamo, da so vsi izračuni čisto. Vendar, če bi bilo res tako, ne bi mogli ničesar natisniti na zaslon. Nasploh, čisto izračuni so tako leni, da jih ni čisto razlogi, da bi nekaj izračunali. Vsi izračuni, ki se pojavljajo v programu, so nekako vsiljeni "nečist" monada IO.
Monade so način za predstavitev izračunov učinki v Haskell. Razlaga njihovega delovanja presega obseg te objave. Dober in jasen opis je mogoče prebrati v angleščini .
Tukaj želim poudariti, da medtem ko so nekatere monade, kot je IO, implementirane s pomočjo čarovnije prevajalnika, so skoraj vse druge implementirane v programski opremi in vsi izračuni v njih so čisti.
Efektov je veliko in vsak ima svojo monado. To je zelo močna in lepa teorija: vse monade izvajajo isti vmesnik. Govorili bomo o naslednjih treh monadah:
- Bodisi ea je izračun, ki vrne vrednost tipa a ali vrže izjemo tipa e. Vedenje te monade je zelo podobno obravnavanju izjem v imperativnih jezikih: napake je mogoče ujeti ali posredovati naprej. Glavna razlika je v tem, da je monada popolnoma logično implementirana v standardni knjižnici v Haskellu, medtem ko imperativni jeziki običajno uporabljajo mehanizme operacijskega sistema.
- Stanje sa je izračun, ki vrne vrednost tipa a in ima dostop do spremenljivega stanja tipa s.
- Mogoče a. Monada Maybe izraža računanje, ki ga je mogoče kadar koli prekiniti z vrnitvijo nič. Govorili pa bomo o implementaciji razreda MonadPlus za tip Maybe, ki izraža nasprotni učinek: gre za izračun, ki ga lahko kadar koli prekinemo z vrnitvijo določene vrednosti.
Implementacija algoritma
Imamo dva tipa podatkov, Graph a in Bigraph ab, od katerih prvi predstavlja grafe z vozlišči, označenimi z vrednostmi tipa a, drugi pa dvodelne grafe z levimi vozlišči, označenimi z vrednostmi tipa a in desnimi. - stranske točke, označene z vrednostmi tipa b.
To niso vrste iz knjižnice Alga. Alga nima predstavitve za neusmerjene bipartitne grafe. Takšne vrste sem naredil zaradi jasnosti.
Potrebovali bomo tudi pomožne funkcije z naslednjimi podpisi:
-- Список соседей данной вершины.
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)Preprosto je videti, da če med iskanjem najprej v globino najdemo nasprotujoč si rob, lihi cikel leži na vrhu rekurzijskega sklada. Zato moramo, da ga obnovimo, odrezati vse od rekurzijskega sklada do prvega pojava zadnjega vozlišča.
Iskanje v globino izvajamo tako, da vzdržujemo asociativno matriko števil deležev za vsako vozlišče. Rekurzivni sklad se bo samodejno vzdrževal z implementacijo razreda Functor monade, ki smo jo izbrali: v rezultat, vrnjen iz rekurzivne funkcije, bomo morali samo postaviti vsa oglišča s poti.
Moja prva ideja je bila uporaba monade Either, za katero se zdi, da izvaja točno tiste učinke, ki jih potrebujemo. Prva izvedba, ki sem jo napisal, je bila zelo blizu tej možnosti. Pravzaprav sem imel na eni točki pet različnih izvedb in na koncu sem se odločil za drugo.
Najprej moramo vzdrževati asociativno matriko identifikatorjev delnic - to je nekaj o stanju. Drugič, znati se moramo ustaviti, ko zaznamo konflikt. To je lahko Monad za Either ali MonadPlus za Maybe. Glavna razlika je v tem, da lahko Either vrne vrednost, če izračun ni bil ustavljen, Maybe pa v tem primeru vrne samo informacije o tem. Ker za uspeh ne potrebujemo ločene vrednosti (je že shranjena v State), izberemo Mogoče. In v trenutku, ko moramo združiti učinke dveh monad, pridejo ven , ki te učinke natančno združujejo.
Zakaj sem izbral tako zapleten tip? Dva razloga. Prvič, izvedba se izkaže za zelo podobno imperativu. Drugič, manipulirati moramo z vrnjeno vrednostjo v primeru konflikta pri vračanju iz rekurzije, da obnovimo liho zanko, kar je veliko lažje narediti v monadi Maybe.
Tako dobimo to izvedbo.
{-# 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 jedro algoritma. Poskušal bom razložiti, kaj se dogaja v njem.
- inVertex je del iskanja v globino, kjer prvič obiščemo točko. Tukaj dodelimo skupno številko točki in zaženemo onEdge na vseh sosedih. Tukaj tudi obnovimo klicni sklad: če je msum vrnil vrednost, tja potisnemo vozlišče v.
- onEdge je del, kjer obiščemo rob. Kliče se dvakrat za vsak rob. Tukaj preverimo, ali je bilo oglišče na drugi strani obiskano, in ga obiščemo, če ni. Ob obisku preverimo, ali je rob konflikten. Če je, vrnemo vrednost - sam vrh rekurzijskega sklada, kamor bodo nato po vrnitvi postavljena vsa ostala oglišča.
- processVertex za vsako točko preveri, ali je bila obiskana, in na njej zažene inVertex, če ni.
- dfs izvaja processVertex na vseh točkah.
To je vse.
Zgodovina besede INLINE
Besede INLINE ni bilo v prvi implementaciji algoritma, pojavila se je kasneje. Ko sem poskušal najti boljšo izvedbo, sem ugotovil, da je različica brez INLINE na nekaterih grafih opazno počasnejša. Glede na to, da bi morale funkcije pomensko delovati enako, me je to zelo presenetilo. Še bolj čudno, na drugem stroju z drugo različico GHC ni bilo opazne razlike.
Potem ko sem preživel teden dni ob branju izhoda GHC Core, sem lahko rešil težavo z eno vrstico eksplicitnega INLINE. Na neki točki med GHC 8.4.4 in GHC 8.6.5 je optimizator sam od sebe prenehal s tem.
Nisem pričakoval, da bom naletel na takšno umazanijo pri programiranju Haskell. Vendar pa optimizatorji tudi danes delajo napake in naša naloga je, da jim damo namige. Na primer, tukaj vemo, da bi morala biti funkcija vstavljena, ker je vstavljena v imperativni različici, in to je razlog, da damo prevajalniku namig.
Kaj se je zgodilo potem?
Potem sem implementiral Hopcroft-Karpov algoritem z drugimi monadami in to je bil konec programa.
Zahvaljujoč Googlovemu poletju kodiranja sem pridobil praktične izkušnje s funkcionalnim programiranjem, ki mi niso le pomagale, da sem naslednje poletje dobil pripravništvo na Jane Street (nisem prepričan, kako dobro je to mesto znano celo med Habrovo dobro obveščeno publiko, vendar je eno od redkih, kjer se lahko poleti ukvarjaš s funkcionalnim programiranjem), ampak me je tudi uvedel v čudovit svet uporabe te paradigme v praksi, ki se bistveno razlikuje od mojih izkušenj s tradicionalnimi jeziki.
Vir: www.habr.com