Eelmisel suvel osalesin — programm, mis on suunatud üliõpilastele Google'ilt. Igal aastal valivad korraldajad mitu avatud lähtekoodiga projekti, sealhulgas sellistelt tuntud organisatsioonidelt nagu ja . Nende projektide kallal töötamiseks kutsub Google üle kogu maailma üliõpilasi.
Google'i suveprogramm 2019 ürituse raames tegin projekti raames teeki koos organisatsiooniga , mis tegeleb Haskelli keele arendamisega — ühe tuntuma funktsionaalse programmeerimiskeelega. Alga — teek, mis esindab esitust graafide jaoks Haskellis. Seda kasutatakse näiteks — Githubi teek, mis ehitab koodi põhjal semantilisi puid, kutsungigraafe ja sõltuvusgraafe ning oskab neid võrrelda. Minu projekt seisnes tüübikindla esitlemise lisamises kaheastmelistele graafidele ja nende esitlemise algoritmidele.
Selles postituses räägin oma rakenduse loomise algoritmist, mis kontrollib graafi kaheosalisust Haskellis. Kuigi algoritm on üks põhialgoritmidest, nõudis selle ilus rakendus funktsionaalses stiilis mitu iteratsiooni ja üsna palju tööd. Lõpuks valisin teostuse, mis kasutab monaadimuundureid.
Kohal
Minu nimi on Vasili Alferov, olen Saint-Peterburgi kõrgkooli neljanda kursuse üliõpilane. Varem olen blogis kirjutanud ja . Praegu olen praktikal Norras, kus tegelevan lähenemistega ülesandele . Minu huvisfäär hõlmab parametreeritud algoritme ja funktsionaalset programmeerimist.
Algoritmi teostamine
Eessõna
Üliõpilastele, kes osalevad programmis, soovitatakse tungivalt pidada blogi. Blogi jaoks anti mulle platvorm . See artikkel on tõlge , mille kirjutasin sinna juulis inglise keeles, koos väikese sissejuhatusega.
Pull Request, kus on mainitud kood, on leitav .
Minu töö tulemuste kohta saab lugeda (inglise keeles) .
Postitus eeldab, et lugejal on põhiteadmised funktsionaalsest programmeerimisest, kuigi üritan meelde tuletada kõiki kasutatavaid termineid, kui nende juurde jõuame.
Graafide kaheosalisuse kontrollimine
Graafide bipartite'iks kontrollimise algoritm antakse tavaliselt algoritmide kursuses kui üks lihtsamaid graafi algoritme. Selle idee on otsene: kõigepealt paigutame tipud vasakusse või paremasse osasse ja kui me avastame konfliktse serva, järeldame, et graaf ei ole bipartite.
Natuke lähemalt: kõigepealt paigutame mingi tipu vasakusse ossa. Ilmselt peavad kõik selle tipu naabrid olema paremas osas. Edasi, kõik naabrid selle tipu naabrile peavad olema vasakus osas ja nii edasi. Me jätkame tipude osade määramist seni, kuni algsesse ühendusse jääb veel tippe, kellele me ei ole naabreid määranud. Seejärel kordame seda tegurit kõigis ühendustes.
Kui kahe tipu vahel on serv, mis kuuluvad samasse ossa, on lihtne leida graafis paaritu tsükkel, mis on üldiselt teadaolevalt (ja üsna ilmselgelt) võimatu bipartite graafis. Vastasel juhul on meil korrektne jaotus osade kaupa, mistõttu on graaf bipartite.
Tavaliselt rakendatakse seda algoritmi selle abil, või . Imperatiivsetes keeltes kasutatakse tavaliselt sügavust uurimist, kuna see on veidi lihtsam ja ei vaja täiendavaid andmestruktuure. Olen ka valinud sügavust uurimise, kuna see on traditsioonilisem.
Nii oleme jõudnud järgmise skeemini. Me külastame graafi tippe sügavuse uurimise abil ja määrame neile osad, muutes osa numbrit serva mööda liikudes. Kui me püüame määrata osa tipule, kellel on juba osa määratud, saame julgelt väita, et graaf ei ole bipartite. Sel hetkel, kui kõikidele tipudele on määratud osa ja me oleme vaadanud kõiki servi, on meil hea jaotus.
Arvutuste puhtus.
Haskellis eeldame, et kõik arvutused on puhtad. Kuid kui see tõepoolest nii oleks, ei oleks meil võimalik midagi ekraanile printida. Üldiselt, puhtad arvutused on nii laisad, et ei eksisteeri ühtegi puhtat põhjust, miks midagi arvutada. Kõik arvutused, mis programmis toimuvad, sunnitakse mingil moel "ebapuhtasse" IO monaadis.
Monaadid on viis esindada arvutusi koos mõjudega. Haskellis. Nende tööpõhimõtte selgitamine jääb sellest postitusest välja. Häid ja arusaadavaid selgitusi võib lugeda inglise keeles. .
Siinkohal tahan märkida, et kuigi mõned monaadid, nagu IO, on realiseeritud kompilaatori maagia kaudu, on peaaegu kõik teised realiseeritud programmeerimise kaudu ja kõik nende arvutused on puhtad.
Efekte on väga palju ja igale on loodud oma monaad. See on väga tugev ja ilus teooria: kõik monaadid realiseerivad sama liidese. Räägime järgmistest kolmest monaadist:
- Either e a — arvutus, mis tagastab väärtuse tüübist a või viskab erandi tüübist e. Selle monaadi käitumine on väga sarnane eranditega töötamisele imperatiivsetes keeltes: vigu saab kinni püüda või edasi anda. Peamine erinevus on see, et monaad on täielikult loogiliselt realiseeritud standardraamatukogus Haskellis, samas kui imperatiivsetes keeltes kasutatakse tavaliselt operatsioonisüsteemi mehhanisme.
- State s a — arvutus, mis tagastab väärtuse tüübist a ja omab juurdepääsu muutuvale olekule tüübist s.
- Maybe a. Monaad Maybe väljendab arvutust, mis võib igal hetkel katkeda Nothing'i tagastamisega. Siiski räägime Maybe tüübi MonadPlus klassi realiseerimisest, mis väljendab vastupidist efekti: see on arvutus, mis võib igal hetkel katkeda konkreetse väärtuse tagastamisega.
Algoritmi realiseerimine
Meil on kaks andmetüüpi, Graph a ja Bigraph a b, millest esimene esindab graafe, mille tipus on märgitud väärtused tüübist a, ja teine esindab kahepoolseid graafe, mille vasakpoolsed tipud on märgitud väärtustega tüübist a ja parempoolsed tipud väärtustega tüübist b.
Need ei ole tüübid raamatukogust Alga. Algas pole esindust suunamata kahepoolsetele graafidele. Tüübid on sellised, et oleks selgem.
Samuti on meil vaja abifunktsioone järgmiste allkirjadega:
-- Naabri tippide nimekiri.
neighbours :: Ord a => a -> Graph a -> [a]
-- Koostada bipartiidne graaf graafist ja funktsioonist, mis tagastab iga tipu
-- oma taseme ja tähise uues tasemes, ignoreerides konfliktseid servasid.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Tippide nimekiri graafis
vertexList :: Ord a => Graph a -> [a]
Funktsiooni allkiri, mida me kirjutame, näeb välja selline:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Ei ole keeruline märgata, et kui sügavotsingu käigus leidub konfliktne serv, on paaritukursus rekursiooni virnas. Seega, et seda taastada, peame katkestama rekursiooni virnas kõik kuni viimase tipu esimese esinemiseni.
Rakendame sügavotsingut, toetades assotsiatiivset massiivi taseme numbrite jaoks iga tipu jaoks. Rekursiooni virna hoitakse automaatselt meie valitud monaadi Functor klassi rakenduse kaudu: peame lihtsalt paigutama kõik teed tippude sisse, mis tulevad rekursiivsest funktsioonist.
Minu esialgne idee oli kasutada monaadit Either, mis justkui rakendab just neid efekte, mida me vajame. Esimene kirjutatud rakendus oli sellele variandile väga lähedane. Tegelikult oli mul mingil hetkel viis erinevat rakendust ja lõpuks otsustasin teise kasuks.
Esiteks peame toetama assotsiatiivset massiivi taseme identifikaatorite jaoks — see on midagi, mis puudutab State. Teiseks peame olema võimelised peatuma konfliktide tuvastamisel. See võib olla kas Monad Either jaoks või MonadPlus Maybe jaoks. Peamine erinevus on see, et Either võib tagastada väärtuse juhul, kui arvutamine ei ole peatatud, samas kui Maybe tagastab sellisel juhul vaid teabe selle kohta. Kuna me ei vaja eduka juhtumi jaoks eraldi väärtust (see on juba State'is talletatud), valime Maybe. Ja hetkel, kui peame kombineerima kahe monaadi efekte, ilmnevad , mis just need efektid kombineerivad.
Miks ma valisin nii keerulise tüübi? Kaks põhjust. Esiteks, teostus sarnaneb väga imperatiivsele. Teiseks, peame manipuleerima väärtusega, mis tagastatakse konflikti korral, tagasiviimisel rekursioonist ebaühtlase tsükli taastamiseks, ja seda on palju lihtsam teha Maybe monadis.
Nii saame sellise teostuse.
{-# 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)
Block where on see on algoritmi tuum. Püüan seletada, mis toimub selle sees.
- inVertex on osake süvitsi otsingust, kus me külastame tipptaset esmakordselt. Siin määrame tipule osa numbri ja käivitame onEdge kõigi naabrite jaoks. Samuti on see koht, kus me taastame kõne steki: kui msum tagastas väärtuse, kinnitame sinna tipu v.
- onEdge — see on the edge. It is called twice for each edge. Here we check if the vertex on the other side has been visited and visit it if not. If it has been visited, we check if the edge is conflicting. If it is, we return the value — the very top of the recursion stack, where all other vertices will be suspended upon return.
- processVertex checks for each vertex whether it has been visited and launches inVertex on it if not.
- dfs launches processVertex on all vertices.
Sellega on kõik.
History of the word INLINE
The word INLINE was not present in the first implementation of the algorithm; it appeared later. When I tried to find a better implementation, I found that on some graphs the version without INLINE was noticeably slower. Considering that semantically the functions should work the same, this surprised me greatly. Even more strangely, on another machine with a different version of GHC, no difference was noticeable.
After spending a week reading the GHC Core output, I was able to fix the problem with one line of explicit INLINE. At some point between GHC 8.4.4 and GHC 8.6.5, the optimizer stopped doing it automatically.
I did not expect to encounter such messiness in Haskell programming. However, optimizers still sometimes make mistakes even today, and giving them hints is our task. For example, here we know that the function should be inlined, as it is in the imperative version, and this is a reason to give the compiler a hint.
What happened next?
Next, I implemented the Hopcroft-Karp algorithm using different monads, and that concluded the program.
Thanks to Google Summer of Code, I gained practical experience in functional programming, which not only helped me secure an internship at Jane Street the following summer (not sure how well-known this place is even among the informed audience of Habr, but it is one of the few places where you can engage in functional programming during the summer), but also introduced me to the fascinating world of applying this paradigm in practice, significantly different from my experience with traditional languages.
Allikas: habr.com
