Eelmisel suvel võtsin osa - Google'i programm õpilastele. Igal aastal valivad korraldajad välja mitu avatud lähtekoodiga projekte, sealhulgas sellistelt tuntud organisatsioonidelt nagu и . Google kutsub õpilasi üle kogu maailma nende projektidega töötama.
Programmis Google Summer of Code 2019 osalejana tegin raamatukogus ühe projekti organisatsiooniga , mis arendab Haskelli keelt – üht kuulsaimat funktsionaalset programmeerimiskeelt. Alga on raamatukogu, mis esindab graafikute esitus Haskellis. Seda kasutatakse näiteks — Githubi teek, mis koostab koodi põhjal semantilisi puid, kõne- ja sõltuvusgraafikuid ning saab neid võrrelda. Minu projekti eesmärk oli lisada kahepoolsete graafikute jaoks tüübikindel esitus ja selle esituse algoritmid.
Selles postituses räägin oma algoritmi rakendamisest graafiku kahepoolseks kontrollimiseks Haskellis. Kuigi algoritm on üks elementaarsemaid, võttis selle ilusti funktsionaalses stiilis realiseerimine mitu kordamist ja nõudis päris palju tööd. Selle tulemusena otsustasin kasutada monaaditrafosid.
Minust
Minu nimi on Vassili Alferov, õpin Peterburi HSE neljandal kursusel. Varem blogis kirjutasin и . Hetkel olen praktikal kl Norras, kus töötan probleemile lähenemise kallal . Minu huvide hulka kuuluvad parameetritega algoritmid ja funktsionaalne programmeerimine.
Algoritmi rakendamisest
Eessõna
Programmis osalevatel õpilastel soovitatakse tungivalt ajaveebi pidada. Nad andsid mulle ajaveebi jaoks platvormi . See artikkel on tõlge , mille kirjutasin seal juulis inglise keeles, lühikese eessõnaga.
Kõnealuse koodiga tõmbamistaotluse leiate .
Minu töö tulemuste kohta saate lugeda (inglise keeles) .
Selle postituse eesmärk on tutvustada lugejale funktsionaalse programmeerimise põhimõisteid, kuigi proovin kõiki kasutatud termineid, kui aeg käes, meelde tuletada.
Graafikute kahepoolsuse kontrollimine
Algoritm graafiku kahepoolseks kontrollimiseks on tavaliselt antud algoritmide kursusel kui üks lihtsamaid graafialgoritme. Tema idee on sirgjooneline: kõigepealt paneme tipud kuidagi vasakpoolsesse või paremasse osasse ja kui leitakse vastuoluline serv, kinnitame, et graaf ei ole kahepoolne.
Natuke täpsemalt: kõigepealt paneme vasakpoolsesse aktsiasse mingi tipu. Ilmselgelt peavad kõik selle tipu naabrid asuma paremas lobus. Lisaks peavad kõik selle tipu naabrite naabrid asuma vasakus lobus ja nii edasi. Jätkame tippudele osade määramist seni, kuni alustatud tipu ühendatud komponendis on veel tippe, millele me pole naabreid määranud. Seejärel kordame seda toimingut kõigi ühendatud komponentidega.
Kui samasse partitsiooni langevate tippude vahel on serv, ei ole keeruline leida graafist paaritut tsüklit, mis on laialt tuntud (ja üsna ilmselgelt kahepoolses graafis võimatu). Vastasel juhul on meil õige partitsioon, mis tähendab, et graafik on kahepoolne.
Tavaliselt rakendatakse seda algoritmi kasutades või . Kohustuslikes keeltes kasutatakse tavaliselt sügavuspõhist otsingut, kuna see on veidi lihtsam ja ei nõua täiendavaid andmestruktuure. Valisin ka sügavuspõhise otsingu, kuna see on traditsioonilisem.
Seega jõudsime järgmise skeemini. Me läbime graafiku tipud sügavus-esimese otsingu abil ja määrame neile osad, muutes serva liikudes jagamise arvu. Kui proovime määrata jagamise tipule, millel on juba osa määratud, võib julgelt väita, et graaf ei ole kahepoolne. Hetkel, kui kõikidele tippudele määratakse jagamine ja oleme kõik servad üle vaadanud, on meil hea partitsioon.
Arvutuste puhtus
Haskellis eeldame, et kõik arvutused on puhas. Kui see aga tõesti nii oleks, poleks meil võimalust midagi ekraanile printida. Üleüldse, puhas arvutused on nii laisad, et seda polegi puhas põhjust midagi arvutada. Kõik programmis esinevad arvutused on kuidagi sunnitud "ebapuhas" monad IO.
Monaadid on viis arvutuste esitamiseks mõjusid aastal Haskell. Nende tööpõhimõtete selgitamine ei kuulu selle postituse ulatusse. Hea ja selge kirjeldus on loetav inglise keeles .
Siinkohal tahan juhtida tähelepanu sellele, et kui mõned monaadid, näiteks IO, realiseeritakse kompilaatorimaagia abil, siis peaaegu kõik teised on realiseeritud tarkvaras ja kõik arvutused neis on puhtad.
Efekte on palju ja igaühel neist on oma monaad. See on väga tugev ja ilus teooria: kõik monaadid rakendavad sama liidest. Räägime kolmest järgmisest monaadist:
- Kas e a on arvutus, mis tagastab a-tüüpi väärtuse või jätab e-tüüpi erandi. Selle monaadi käitumine on väga sarnane erandite käsitlemisega imperatiivsetes keeltes: vigu saab tabada või edasi anda. Peamine erinevus seisneb selles, et monaad on täiesti loogiliselt rakendatud Haskelli standardraamatukogus, samas kui kohustuslikud keeled kasutavad tavaliselt operatsioonisüsteemi mehhanisme.
- Olek s a on arvutus, mis tagastab a-tüüpi väärtuse ja millel on juurdepääs tüübi s muutuvale olekule.
- Võib-olla a. Võib-olla monaad väljendab arvutust, mille saab igal ajal katkestada, tagastades Nothing. Räägime aga klassi MonadPlus rakendamisest Maybe tüübi jaoks, mis väljendab vastupidist efekti: see on arvutus, mille saab igal ajal katkestada, tagastades konkreetse väärtuse.
Algoritmi rakendamine
Meil on kaks andmetüüpi, graafik a ja bigraaf a b, millest esimene kujutab graafikuid, mille tipud on märgistatud a-tüüpi väärtustega, ja teine on kahepoolsed graafikud vasakpoolsete tippudega, mis on märgistatud a-tüüpi ja paremate väärtustega. - külgmised tipud, mis on märgistatud b-tüüpi väärtustega.
Need ei ole Alga raamatukogu tüübid. Algal puudub suunamata kahepoolsete graafide esitus. Sellised tüübid tegin selguse huvides.
Vajame ka abifunktsioone järgmiste allkirjadega:
-- Список соседей данной вершины.
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)On lihtne näha, et kui sügavus-esimese otsingu käigus leidsime vastuolulise serva, asub paaritu tsükkel rekursioonipinu peal. Seega peame selle taastamiseks ära lõikama kõik alates rekursioonivirust kuni viimase tipu esmakordse esinemiseni.
Rakendame sügavuspõhist otsingut, säilitades iga tipu jaoks assotsiatiivse jagamisnumbrite massiivi. Rekursioonipinu säilitatakse automaatselt meie valitud monaadi Functor-klassi rakendamise kaudu: me peame panema ainult kõik tee tipud rekursiivse funktsiooni poolt tagastatud tulemusesse.
Minu esimene idee oli kasutada kummagi monaadi, mis näib rakendavat täpselt neid efekte, mida me vajame. Esimene teostus, mille ma kirjutasin, oli sellele võimalusele väga lähedal. Tegelikult oli mul ühel hetkel viis erinevat rakendust ja lõpuks otsustasin teisega.
Esiteks peame säilitama aktsiaidentifikaatorite assotsiatiivse massiivi – see on midagi osariigi kohta. Teiseks peame suutma lõpetada, kui konflikt avastatakse. See võib olla kas Monad for Ether või MonadPlus for Maybe. Peamine erinevus seisneb selles, et Kas võib tagastada väärtuse, kui arvutus pole peatatud, ja Maybe tagastab sel juhul ainult selle teabe. Kuna me ei vaja edu saavutamiseks eraldi väärtust (see on juba State'is salvestatud), valime Maybe. Ja sel hetkel, kui meil on vaja kahe monaadi mõjusid ühendada, tulevad need välja , mis need efektid täpselt ühendavad.
Miks ma valisin nii keerulise tüübi? Kaks põhjust. Esiteks osutub rakendamine väga sarnaseks imperatiiviga. Teiseks peame rekursioonist tagasi naastes konflikti korral manipuleerima tagastamisväärtusega, et taastada paaritu tsükkel, mida on Maybe monaadis palju lihtsam teha.
Nii saame selle 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 <- 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)
Kus plokk on algoritmi tuum. Püüan selgitada, mis selle sees toimub.
- inVertex on sügavus-esimese otsingu osa, kus külastame tippu esimest korda. Siin omistame tipule jagamisnumbri ja käivitame onEdge'i kõikidel naabritel. Siin taastame ka kõnepinu: kui msum tagastas väärtuse, lükkame sinna tipu v.
- onEdge on osa, kus me serva külastame. Seda kutsutakse iga serva jaoks kaks korda. Siin kontrollime, kas teisel pool asuvat tippu on külastatud, ja külastame seda, kui mitte. Külastamisel kontrollime, kas serv on vastuolus. Kui on, tagastame väärtuse – rekursioonipinu ülaosa, kuhu tagastamisel asetatakse kõik teised tipud.
- processVertex kontrollib iga tipu puhul, kas seda on külastatud, ja käivitab sellel inVertexi, kui mitte.
- dfs käivitab protsessiVertexi kõigis tippudes.
See on kõik.
Sõna INLINE ajalugu
Sõna INLINE ei olnud algoritmi esimeses teostuses, see ilmus hiljem. Kui proovisin leida paremat teostust, avastasin, et mitte-INLINE versioon oli mõnel graafikul märgatavalt aeglasem. Arvestades, et semantiliselt peaksid funktsioonid samamoodi töötama, üllatas see mind väga. Veelgi kummalisem on see, et teises masinas, millel oli erinev GHC versioon, polnud märgatavat erinevust.
Kui olin nädal aega lugenud GHC Core'i väljundit, suutsin probleemi ühe rea selgesõnalise INLINE abil lahendada. Mingil hetkel GHC 8.4.4 ja GHC 8.6.5 vahel lõpetas optimeerija selle iseenesest.
Ma ei oodanud, et kohtan Haskelli programmeerimisel sellist mustust. Kuid isegi tänapäeval teevad optimeerijad mõnikord vigu ja meie ülesanne on neile vihjeid anda. Näiteks siin teame, et funktsioon peaks olema reastatud, kuna see on kohustuslikus versioonis sees, ja see on põhjus anda kompilaatorile vihje.
Mis edasi sai?
Seejärel rakendasin Hopcroft-Karp algoritmi koos teiste monaadidega ja sellega programm lõppes.
Tänu Google Summer of Code'ile sain praktilise kogemuse funktsionaalse programmeerimise vallas, mis mitte ainult ei aidanud mul järgmisel suvel Jane Streetil praktikale pääseda (ma pole kindel, kui tuntud see koht on isegi Habri teadliku publiku seas, kuid see on üks vähestest, kus saate suvel tegeleda funktsionaalse programmeerimisega), vaid tutvustas mulle ka selle paradigma praktikas rakendamise imelist maailma, mis erineb oluliselt minu kogemustest traditsioonilistes keeltes.
Allikas: www.habr.com