Eelmisel suvel osalesin — Google'i üliõpilaste programm. Igal aastal vali korraldajad välja mitu avatud lähtekoodiga projekti, sealhulgas tuntud organisatsioonidelt nagu ja . Neid projekte ellu viima kutsub Google üliõpilasi üle kogu maailma.
Google Summer of Code 2019 osalejana töötasin ma projekti kallal, mis oli seotud raamatukoguga koos organisatsiooniga , mis tegeleb Haskelli, ühe kõige tuntuma funktsionaalprogrammeerimise keele arendamisega. Alga on raamatukogu, mis pakub esitust Haskelli graafide jaoks. Seda kasutatakse näiteks — Githubi raamatukogus, mis loob koodi põhjal semantilisi puid, kõnede ja sõltuvuste graafe, oskab neid võrrelda. Minu projekti eesmärk oli lisada sinna tüübusaldusväärne esitamine kahepoolsetele graafidele ja algoritmid selle esitluse jaoks.
Postituses räägin oma implementeerimisest graafi bipolaarsuse kontrollimise algoritmist Haskellis. Kuigi algoritm on üks põhilisi, võttis selle kaunis funktsionaalne rakendus minu arvates mitmeid iteratsioone ja nõudis tohutult palju tööd. Lõpuks peatusin ma monaadide transformeerijatega implementeerimise juures.
Minust
Minu nimi on Vasili Alfjov, olen Peterburi Ülikooli neljanda kursuse üliõpilane. Olen varem blogis kirjutanud ja . Praegu olen praktikandina Norras, kus tegelen teema . Minu huvide valdkondade hulka kuuluvad parametriseeritud algoritmid ja funktsionaalne programmeerimine.
Algoritmi rakendamine
Eessõna
Programmis osalevatele üliõpilastele soovitatakse aktiivselt blogi pidada. Minu blogile on antud platvorm . See artikkel on tõlge , mille kirjutasin sinna juulis ingliskeelsena, koos väikese ettekujutusega.
Pull Requesti koodiga, millest jutt, on saadaval .
Minu töö tulemustest saab lugeda (inglise keeles) .
Post tutvustab lugejat funktsionaalprogrammeerimise põhialustega, kuigi püüan meelde tuletada kõik kasutatavad terminid, kui nende päev on käes.
Grafide bipolaarsuse kontrollimine
Grafi bipolaarsuse kontrollimise algoritm antakse tavaliselt algoritmide kursuses kui üks lihtsamaid graafialgoritme. Selle idee on sirgjooneline: kõigepealt paigutame tipud kas vasakusse või paremasse osasse ning konfliktse servi avastamisel väidame, et graaf ei ole bipolaarne.
Natuke täpsemalt: kõigepealt paneme mingi tipu vasakusse ossa. Ilmselgelt peavad selle tipu kõik naabrid olema paremas osas. Jätkame, määrates tipud osadele, kuni seotuse komponendis, millega alustasime, on veel tippe, kellele me naabreid ei ole määranud. Seejärel kordame seda tegevust kõigi seotuse komponentide puhul.
Kui kahe tipu vahel on serv, mis kuuluvad samasse rühma, ei ole keeruline leida graafis paaritud tsüklit, mis on üldiselt tuntud (ja piisavalt ilmselge), et see ei saa olla paarigrafis. Vastasel juhul on meil õige jagunemine rühmadesse, mis tähendab, et graaf on paariline.
Tavaliselt rakendatakse seda algoritmi või . Imperatiivsetes keeltes kasutatakse tavaliselt sügavuaruandlust, mis on veidi lihtsam ja ei vaja täiendavaid andmestruktuure. Olen ka valinud sügavuaruandluse, kuna see on traditsioonilisem.
Seega jõuame järgmise skeemini. Me läbime graafi tipud sügavuaruande abil ja määrame neile rühmad, muutes rühma numbri serva läbimisel. Kui püüame määrata rühma tipule, millele on juba rühm määratud, saab julgelt väita, et graaf ei ole paariline. Hetkel, kui kõigile tipudele on määratud rühm ja oleme kõik servad üle vaadanud, on meil hea jagunemine.
Arvutuste puhtus
Haskellis eeldame, et kõik arvutused on puhtad. Kuid kui see tõesti nii oleks, ei oleks meil võimalust ekraanile midagi printida. Üldiselt, puhtad arvutused on nii laiskad, et ei ole ühtegi puhta põhjust, et midagi arvutada. Kõik programmis toimuvad arvutused sunnitakse niikuinii "räpasesse" IO monaadisse.
Monaadid on viis arvutuste esitlemiseks koos efektidega Haskellis. Selgitus, kuidas need töötavad, ületab selle postituse piire. Head ja selget selgitust saab lugeda inglise keeles. .
Siinkohal tahan märkida, et kuigi mõned monaadid, nagu IO, on realiseeritud kompilaatori maagia kaudu, siis peaaegu kõik teised on reaalselt programmi sees ja kõik arvutused neis on puhtad.
Efekte on väga palju ja igaühe jaoks on loodud oma monaad. see on väga tugev ja ilus teooria: kõik monaadid realiseerivad sama liidest. Räägime kolmest järgmisest monaadist:
- Kas a — arvutus, mis tagastab tüüpi a või viskab tüübi e erandi. Selle monadi käitumine on väga sarnane erandite käsitlemisele imperatiivsetes keeltes: vead võivad olla kinni püütud või edasi antud. Peamine erinevus on see, et monad on täielikult loogiliselt realiseeritud standardteegis samas Haskellis, samas kui imperatiivsetes keeltes kasutatakse tavaliselt operatsioonisüsteemi mehhanisme.
- State s a — arvutus, mis tagastab tüübi a väärtuse ja omab juurdepääsu muudetavale olekule tüübiga s.
- Maybe a. Monad Maybe väljendab arvutust, mis võib igal hetkel katkeda, tagastades Nothing. Kuid räägime MonadPlus klassi rakendamisest, mis on mõeldud Maybe tüübile, väljendades vastupidist efekti: see on arvutus, mis võib igal hetkel katkeda, tagastades konkreetse väärtuse.
Algrütmide rakendamine
Meil on kaks andmetüüpi: Graph a ja Bigraph a b, millest esimene esindab grafit, mille tipud on märgitud a tüüpi väärtustega, ning teine esindab bipartit graafe, mille vasaku poole tipud on märgitud a tüüpi väärtustega ja parema poole tipud b tüüpi väärtustega.
Need ei ole Alga teegist pärinevad tüübid. Algas ei ole esindust suundumata bipartit graafide jaoks. Muudsin tüübid selliseks, et neid oleks lihtsam visualiseerida.
Samuti vajame abifunktsioone järgmiste signatuuridega:
-- Antud tipu naabrid.
neighbours :: Ord a => a -> Graph a -> [a]
-- Ehita bipartit graaf graafi ja funktsiooni põhjal, mis iga tipu jaoks
-- tagastab selle poole ja tähistuse uues pooles, jättes tähelepanuta konfliktseid servi.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Tipude loend graafis
vertexList :: Ord a => Graph a -> [a]
Funktsiooni signatuur, mida me kirjutame, näeb välja nii:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Ei ole raske märgata, et kui sügavuse otsimise protsessis leiame konfliktse serva, asub paaritu ring rekursioonide stalki peal. Seega, et seda taastada, peame katkestama rekursioonist kõik kuni viimase tipu esmakordse leidmiseni.
Rakendame sügavuse otsimist, toetades iga tipu jaoks associatiivse massi, mis sisaldab indekseid. Rekursioonistakk hoitakse automaatselt meie valitud monadi Functori klassi rakenduse kaudu: lihtsalt peame paigutama kõik teed tipud tulemusena, mis tagastatakse rekursiivsest funktsioonist.
Minu esimene idee oli kasutada Either monadi, mis tundub olevat täpselt need efektid, mida me vajame. Esimene, mille ma kirjutasin, oli väga lähedane sellele versioonile. Tegelikult oli mul mingil hetkel viis erinevat rakendust ja lõpuks otsustasin teise kasuks.
Esiteks peame toetama assotsiatiivset massiivi osade identifikaatoritest — see on seotud State'iga. Teiseks, peame olema võimelised peatuma, kui konflikt avastatakse. See võib olla kas Monad Either või MonadPlus Maybe. Peamine erinevus on see, et Either võib tagastada väärtuse, kui arvutus ei ole peatunud, aga Maybe tagastab sel juhul vaid teavet. Kuna me ei vaja eraldi väärtust eduka tulemuse puhul (see on juba State'is talletatud), valime Maybe. Ja kui hetk on käes, et kombineerida kahe monadi efekte, siis ilmnevad , mis just nende efekte kombineerivad.
Miks ma valisin nii keerulise tüübi? Kaks põhjust. Esiteks, rakendus on väga sarnane imperatiivsele. Teiseks, meil on vaja manipuleerida väärtusega, mis tagastatakse konflikti korral, tagasitulekul rekurssist, et taastada paaritu tsükkel, ja seda on oluliselt lihtsam teha Maybe monadis.
Nii saame sellise rakenduse.
{-# 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 — see algoritmi tuum. Püüan selgitada, mis selle sees toimub.
- inVertex — osa sügavusest otsingust, kus me tipptaseme esmakordselt külastame. Siin anname tipptasemele osaluse numbri ja käivitame kõikide naabrite jaoks onEdge. See on ka koht, kus taastame kutsumiste virna: kui msum on väärtuse tagastanud, riputame sinna tipptaseme v.
- onEdge — see on osa, kus me külastame serva. See kutsutakse tagasi kaks korda iga serva jaoks. Siin kontrollime, kas tipptase on teiselt poolt külastatud ja külastame seda, kui mitte. Kui on külastatud, kontrollime, kas serv on konfliktne. Kui on, tagastame väärtuse — rekursiooni virna ülemise, kuhu seejärel kõik teised tipptasemed riputatakse tagasi.
- processVertex kontrollib iga tipptaseme puhul, kas see on külastatud, ja käivitab inVertex, kui ei.
- dfs käivitab processVertex kõikidel tipptasemetel.
Sellega on kõik.
Sõna INLINE ajalugu
Sõna INLINE ei olnud algses algoritmi rakenduses, see ilmus hiljem. Kui ma püüdsin leida paremat rakendust, avastasin, et teatud graafide puhul töötab INLINE'ita versioon märgatavalt aeglasemalt. Arvestades, et semantiliselt peavad funktsioonid töötama ühtemoodi, üllatas see mind väga. Veelgi kummalisem oli, et teisel masinal teise GHC versiooniga ei olnud mingit erinevust märgata.
Pärast nädalat GHC Core väljalugemise lugemist, suutsin lahendada probleemi ühe rea üheselt mõistetava INLINE'iga. Mõnesuguse hetke jooksul GHC 8.4.4 ja GHC 8.6.5 vahel lõpetas optimeerija selle tegemise iseseisvalt.
Ma ei oodanud kohtuda sellise räpasusega Haskellis programmeerimisel. Kuid optimeerijad teevad isegi tänapäeval aeg-ajalt vigu ning nendele vihjete andmine on meie ülesanne. Näiteks teame siin, et funktsioon peaks olema sisustatud, kuna see on sisustatud imperatiivsesse versiooni, ja see on põhjus anda kompilaatorile vihje.
Mis edasi juhtus?
Edasi viisin Hopcroft-Karpa algoritmi rakenduse juba teiste monaadidega, ja sellega programm lõppes.
Google Summer of Code'i tänu olen saanud praktilisi kogemusi funktsionaalses programmeerimises, mis aitas mul saada suvel Jane Streetis praktikaks (ei ole kindel, kui tuntud see koht isegi Hubri teadlikule publikule, kuid see on üks väheseid, kus suvel funktsionaalset programmeerimist õppida), ja tutvustas mind hämmastavasse maailma, kus seda paradigmat praktikas rakendatakse, mis on oluliselt erinev minu kogemustest traditsioonilistes keeltes.
Allikas: habr.com
