Viime kesänä osallistuin - Googlen opiskelijoille tarkoitettu ohjelma. Järjestäjät valitsevat vuosittain useita Open Source -projekteja, muun muassa tunnetuilta organisaatioilta, kuten и . Google kutsuu opiskelijoita kaikkialta maailmasta työskentelemään näissä projekteissa.
Osallistuessani Google Summer of Code 2019 -tapahtumaan tein projektin kirjastossa organisaation kanssa , joka kehittää Haskell-kieltä - yhtä tunnetuimmista toiminnallisista ohjelmointikielistä. Alga on kirjasto, joka edustaa graafisten esitys Haskellissa. Sitä käytetään mm — Github-kirjasto, joka rakentaa semanttisia puita, puhelu- ja riippuvuuskaavioita koodin perusteella ja voi verrata niitä. Projektini oli lisätä tyyppiturvallinen esitys kaksiosaisille kaavioille ja algoritmeja tälle esitykselle.
Tässä viestissä puhun algoritmin toteuttamisesta graafin kaksiosaisuuden tarkistamiseksi Haskellissa. Vaikka algoritmi onkin yksi alkeellisimmista, sen kauniisti toteuttaminen toiminnallisella tyylillä vei useita iteraatioita ja vaati melko paljon työtä. Tämän seurauksena päädyin toteuttamaan monadimuuntajia.
Tietoja minusta
Nimeni on Vasily Alferov, olen neljännen vuoden opiskelija Pietarin HSE:ssä. Aiemmin blogissa kirjoitin и . Tällä hetkellä olen työharjoittelussa osoitteessa Norjassa, jossa työskentelen ongelman lähestymistapojen parissa . Kiinnostukseni kohteena ovat parametroidut algoritmit ja toiminnallinen ohjelmointi.
Tietoja algoritmin toteutuksesta
Esipuhe
Ohjelmaan osallistuvia opiskelijoita kannustetaan blogiin. He tarjosivat minulle alustan blogia varten . Tämä artikkeli on käännös kirjoitin siellä heinäkuussa englanniksi lyhyellä esipuheella.
Vedä pyyntö kyseisellä koodilla löytyy .
Voit lukea työni tuloksista (englanniksi) .
Tämän postauksen tarkoituksena on perehdyttää lukija toiminnallisen ohjelmoinnin peruskäsitteisiin, vaikka yritänkin muistaa kaikki käytetyt termit kun aika tulee.
Kaavioiden kaksiosaisuuden tarkistaminen
Algoritmi graafin kaksiosaisuuden tarkistamiseksi annetaan yleensä algoritmeja käsittelevässä kurssissa yhtenä yksinkertaisimmista graafialgoritmeista. Hänen ajatuksensa on suoraviivainen: ensin laitamme pisteet jotenkin vasempaan tai oikeaan osuuteen, ja kun ristiriitainen reuna löytyy, väitämme, että graafi ei ole kaksiosainen.
Hieman yksityiskohtia: laitamme ensin pisteen vasempaan osuuteen. Ilmeisesti kaikkien tämän kärjen naapureiden on sijaittava oikeassa lohkossa. Lisäksi kaikkien tämän kärjen naapureiden tulee sijaita vasemmassa lohkossa ja niin edelleen. Jatkamme osuuksien osoittamista kärkipisteille niin kauan kuin aloittamamme kärjen yhdistetyssä komponentissa on vielä pisteitä, joille emme ole osoittaneet naapureita. Toistamme sitten tämän toiminnon kaikille liitetyille komponenteille.
Jos samaan osioon osuvien kärkien välillä on reuna, graafista ei ole vaikea löytää paritonta sykliä, mikä on laajalti tunnettu (ja aivan ilmeisen mahdotonta kaksiosaisessa graafissa). Muuten meillä on oikea osio, mikä tarkoittaa, että graafi on kaksiosainen.
Tyypillisesti tämä algoritmi toteutetaan käyttämällä tai . Pakollisissa kielissä käytetään yleensä syvällistä hakua, koska se on hieman yksinkertaisempi eikä vaadi lisätietorakenteita. Valitsin myös syvähaun, koska se on perinteisempi.
Siten päädyimme seuraavaan kaavioon. Kuljemme graafin kärjet käyttämällä syvyyshakua ja annamme niille osuuksia muuttamalla osuuden numeroa liikkuessamme reunaa pitkin. Jos yritämme määrittää osuuden kärkipisteelle, jolle on jo määritetty osuus, voimme turvallisesti sanoa, että graafi ei ole kaksiosainen. Heti kun kaikki kärjet ovat jaettu ja olemme katsoneet kaikki reunat, meillä on hyvä osio.
Laskelmien puhtaus
Haskellissa oletetaan, että kaikki laskelmat ovat puhdas. Jos näin olisi, meillä ei kuitenkaan olisi mitään mahdollisuutta tulostaa näytölle. Ollenkaan, puhdas laskelmat ovat niin laiskoja, että niitä ei ole puhdas syitä laskea jotain. Kaikki ohjelmassa tapahtuvat laskelmat on jotenkin pakotettu "epäpuhdas" monad IO.
Monadit ovat tapa esittää laskelmia tehosteita Haskellissa. Niiden toiminnan selittäminen ei kuulu tämän viestin piiriin. Hyvä ja selkeä kuvaus on luettavissa englanniksi .
Tässä haluan huomauttaa, että vaikka jotkin monadit, kuten IO, toteutetaan kääntäjän magian avulla, melkein kaikki muut on toteutettu ohjelmistossa ja kaikki laskelmat niissä ovat puhtaita.
Efektejä on paljon ja jokaisella on oma monadinsa. Tämä on erittäin vahva ja kaunis teoria: kaikki monadit toteuttavat saman käyttöliittymän. Puhumme seuraavista kolmesta monadista:
- Joko ea on laskutoimitus, joka palauttaa tyypin a arvon tai heittää tyypin e poikkeuksen. Tämän monadin käyttäytyminen on hyvin samanlaista kuin poikkeusten käsittely pakollisilla kielillä: virheet voidaan havaita tai siirtää eteenpäin. Suurin ero on, että monadi on täysin loogisesti toteutettu Haskellin standardikirjastossa, kun taas pakolliset kielet käyttävät yleensä käyttöjärjestelmän mekanismeja.
- Tila sa on laskutoimitus, joka palauttaa tyypin a arvon ja jolla on pääsy tyypin s muuttuvaan tilaan.
- Ehkä. Ehkä-monadi ilmaisee laskennan, joka voidaan keskeyttää milloin tahansa palauttamalla Ei mitään. Puhumme kuitenkin Ehkä-tyypin MonadPlus-luokan toteutuksesta, joka ilmaisee päinvastaisen vaikutuksen: se on laskenta, joka voidaan keskeyttää milloin tahansa palauttamalla tietyn arvon.
Algoritmin toteutus
Meillä on kaksi tietotyyppiä, Graph a ja Bigraph ab, joista ensimmäinen edustaa kaavioita, joiden kärjet on merkitty tyypin a arvoilla, ja toinen edustaa kaksiosaisia kaavioita, joiden vasemmanpuoleiset kärjet on merkitty arvoilla a ja oikea. -sivupisteet, jotka on merkitty tyypin b arvoilla.
Nämä eivät ole Alga-kirjaston tyyppejä. Algalla ei ole esitystapaa suuntaamattomille kaksiosaisille graafille. Tein selvyyden vuoksi tällaiset tyypit.
Tarvitsemme myös aputoimintoja seuraavilla allekirjoituksilla:
-- Список соседей данной вершины.
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 helppo nähdä, että jos syvyys-ensimmäisen haun aikana löysimme ristiriitaisen reunan, on pariton sykli rekursiopinon päällä. Siksi sen palauttamiseksi meidän on leikattava pois kaikki rekursiopinosta viimeisen huippupisteen ensimmäiseen esiintymiseen asti.
Toteutamme syvyyshaun ylläpitämällä assosiatiivista jakonumeroiden joukkoa kullekin kärjelle. Rekursiopinoa ylläpidetään automaattisesti valitsemamme monadin Functor-luokan toteutuksen avulla: meidän tarvitsee vain laittaa kaikki polun kärjet rekursiivisen funktion palauttamaan tulokseen.
Ensimmäinen ajatukseni oli käyttää joko-monadia, joka näyttää toteuttavan juuri tarvitsemamme tehosteet. Ensimmäinen kirjoittamani toteutus oli hyvin lähellä tätä vaihtoehtoa. Itse asiassa minulla oli viisi erilaista toteutusta yhdessä vaiheessa ja lopulta päädyin toiseen.
Ensinnäkin meidän on ylläpidettävä assosiatiivinen joukko osaketunnisteita - tämä liittyy osavaltioon. Toiseksi meidän on kyettävä lopettamaan, kun konflikti havaitaan. Tämä voi olla joko Monad for joko tai MonadPlus for Maybe. Suurin ero on, että joko voi palauttaa arvon, jos laskentaa ei ole pysäytetty, ja Maybe palauttaa tässä tapauksessa vain tiedot tästä. Koska emme tarvitse erillistä arvoa menestykseen (se on jo tallennettu State-tilaan), valitsemme Maybe. Ja sillä hetkellä, kun meidän on yhdistettävä kahden monadin vaikutukset, ne tulevat esiin , jotka yhdistävät tarkasti nämä vaikutukset.
Miksi valitsin niin monimutkaisen tyypin? Kaksi syytä. Ensinnäkin toteutus osoittautuu hyvin samankaltaiseksi kuin pakollinen. Toiseksi meidän on manipuloitava palautusarvoa ristiriidan sattuessa palatessamme takaisin rekursiosta parittoman silmukan palauttamiseksi, mikä on paljon helpompaa tehdä Maybe-monadissa.
Näin saamme tämän toteutuksen.
{-# 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)
Missä-lohko on algoritmin ydin. Yritän selittää, mitä sen sisällä tapahtuu.
- inVertex on syvyysensimmäisen haun osa, jossa käymme kärjessä ensimmäistä kertaa. Tässä annamme kärkipisteelle jakonumeron ja suoritamme onEdgen kaikissa naapureissa. Tässä myös palautetaan kutsupino: jos msum palautti arvon, työnnetään vertex v sinne.
- onEdge on osa, jossa käymme reunassa. Sitä kutsutaan kahdesti jokaiselle reunalle. Täällä tarkistamme, onko toisella puolella olevassa kärjessä käyty, ja vierailemme siinä, jos ei. Jos käymme, tarkistamme, onko reuna ristiriitainen. Jos on, palautamme arvon - rekursiopinon yläosan, johon kaikki muut kärjet sijoitetaan palautuksen yhteydessä.
- processVertex tarkistaa jokaisen kärjen osalta, onko siinä vieraillut, ja suorittaa inVertexin siinä, jos ei.
- dfs suorittaa processVertexin kaikissa pisteissä.
Siinä kaikki.
Sanan INLINE historia
Sana INLINE ei ollut algoritmin ensimmäisessä toteutuksessa, vaan se ilmestyi myöhemmin. Kun yritin löytää parempaa toteutusta, huomasin, että ei-INLINE-versio oli joissakin kaavioissa huomattavasti hitaampi. Ottaen huomioon, että semanttisesti funktioiden pitäisi toimia samalla tavalla, tämä yllätti minut suuresti. Vielä kummallisempaa, toisessa koneessa, jossa oli eri versio GHC:stä, ei havaittu eroa.
Vietettyäni viikon GHC Core -tulosteen lukemisen jälkeen pystyin korjaamaan ongelman yhdellä selkeällä INLINE-rivillä. Jossain vaiheessa GHC 8.4.4 ja GHC 8.6.5 välillä optimoija lakkasi tekemästä tätä itsestään.
En odottanut kohtaavani tällaista likaa Haskell-ohjelmoinnissa. Kuitenkin vielä nykyäänkin optimoijat tekevät joskus virheitä, ja meidän tehtävämme on antaa heille vihjeitä. Esimerkiksi täällä tiedämme, että funktion tulisi olla rivitettynä, koska se on upotettu pakottavassa versiossa, ja tämä on syy antaa kääntäjälle vihje.
Mitä seuraavaksi tapahtui?
Sitten toteutin Hopcroft-Karp-algoritmin muiden monadien kanssa, ja siihen ohjelma päättyi.
Google Summer of Coden ansiosta sain käytännön kokemusta toiminnallisesta ohjelmoinnista, mikä ei vain auttanut minua pääsemään harjoittelupaikkaan Jane Streetillä seuraavana kesänä (en ole varma, kuinka tunnettu tämä paikka on edes Habrin asiantuntevan yleisön keskuudessa, mutta se on yksi niistä harvoista, joissa voit kesä harjoittaa toiminnallista ohjelmointia), mutta myös tutustutti minut tämän paradigman käytännön soveltamisen ihmeelliseen maailmaan, joka eroaa merkittävästi kokemuksestani perinteisillä kielillä.
Lähde: will.com