I fjor sommer var jeg med på - et program for studenter fra Google. Hvert år velger arrangørene flere Open Source-prosjekter, blant annet fra så kjente organisasjoner som и . Google inviterer studenter fra hele verden til å jobbe med disse prosjektene.
Som deltaker i Google Summer of Code 2019 gjorde jeg et prosjekt på biblioteket med organisasjonen , som utvikler Haskell-språket - et av de mest kjente funksjonelle programmeringsspråkene. Alga er et bibliotek som representerer representasjon for grafer i Haskell. Den brukes for eksempel i — et Github-bibliotek som bygger semantiske trær, samtale- og avhengighetsgrafer basert på kode og kan sammenligne dem. Mitt prosjekt var å legge til en typesikker representasjon for todelte grafer og algoritmer for den representasjonen.
I dette innlegget vil jeg snakke om min implementering av en algoritme for å sjekke en graf for todelthet i Haskell. Selv om algoritmen er en av de mest grunnleggende, tok det meg flere iterasjoner å implementere den vakkert i en funksjonell stil og krevde ganske mye arbeid. Som et resultat bestemte jeg meg for en implementering med monadetransformatorer.
Om meg
Mitt navn er Vasily Alferov, jeg er fjerdeårsstudent ved St. Petersburg HMS. Tidligere i bloggen skrev jeg и . Akkurat nå er jeg på praksis hos i Norge, hvor jeg jobber med tilnærminger til problemet . Mine interesser inkluderer parameteriserte algoritmer og funksjonell programmering.
Om implementeringen av algoritmen
Forord
Studenter som deltar i programmet oppfordres sterkt til å blogge. De ga meg en plattform for bloggen . Denne artikkelen er en oversettelse , skrevet av meg der i juli på engelsk, med et kort forord.
Pull-forespørsel med den aktuelle koden kan bli funnet .
Du kan lese om resultatene av arbeidet mitt (på engelsk) .
Dette innlegget er ment å gjøre leseren kjent med de grunnleggende konseptene innen funksjonell programmering, selv om jeg skal prøve å huske alle begrepene som brukes når den tid kommer.
Sjekker grafer for todelthet
En algoritme for å sjekke en graf for todelthet gis vanligvis i et kurs om algoritmer som en av de enkleste grafalgoritmene. Ideen hans er grei: Først legger vi på en eller annen måte toppunkter i venstre eller høyre del, og når en motstridende kant blir funnet, hevder vi at grafen ikke er todelt.
Litt mer detalj: først legger vi noen toppunkt i venstre del. Det er klart at alle naboene til dette toppunktet må ligge i høyre lapp. Videre må alle naboene til naboene til dette toppunktet ligge i venstre lapp, og så videre. Vi fortsetter å tilordne deler til toppunkter så lenge det fortsatt er toppunkter i den tilkoblede komponenten av toppunktet vi startet med som vi ikke har tildelt naboer til. Vi gjentar deretter denne handlingen for alle tilkoblede komponenter.
Hvis det er en kant mellom hjørner som faller inn i samme partisjon, er det ikke vanskelig å finne en oddetall syklus i grafen, som er allment kjent (og ganske åpenbart) umulig i en todelt graf. Ellers har vi en riktig partisjon, som betyr at grafen er todelt.
Vanligvis er denne algoritmen implementert ved hjelp av eller . På imperative språk brukes vanligvis dybde-først-søk da det er litt enklere og ikke krever ytterligere datastrukturer. Jeg valgte også dybde-først-søk da det er mer tradisjonelt.
Dermed kom vi til følgende opplegg. Vi krysser toppene av grafen ved å bruke dybde-først-søk og tildeler delinger til dem, og endrer nummeret på delingen når vi beveger oss langs kanten. Hvis vi prøver å tilordne en del til et toppunkt som allerede har en del tildelt, kan vi trygt si at grafen ikke er todelt. I det øyeblikket alle hjørnene blir tildelt en del og vi har sett på alle kantene, har vi en god partisjon.
Renhet av beregninger
I Haskell antar vi at alle beregninger er ren. Men hvis dette virkelig var tilfelle, ville vi ikke ha noen måte å skrive ut noe på skjermen. I det hele tatt, ren beregninger er så late at det ikke er en ren grunner til å beregne noe. Alle beregninger som forekommer i programmet blir på en eller annen måte tvunget inn "uren" monaden IO.
Monader er en måte å representere beregninger med effekter i Haskell. Å forklare hvordan de fungerer er utenfor rammen av dette innlegget. En god og oversiktlig beskrivelse kan leses på engelsk .
Her vil jeg påpeke at mens noen monader, som IO, er implementert gjennom kompilatormagi, er nesten alle andre implementert i programvare og alle beregninger i dem er rene.
Det er mange effekter og hver har sin egen monad. Dette er en veldig sterk og vakker teori: alle monader implementerer det samme grensesnittet. Vi vil snakke om følgende tre monader:
- Enten er ea en beregning som returnerer en verdi av type a eller kaster et unntak av type e. Oppførselen til denne monaden er veldig lik unntakshåndtering i imperative språk: feil kan fanges opp eller overføres. Hovedforskjellen er at monaden er fullstendig logisk implementert i standardbiblioteket i Haskell, mens imperative språk vanligvis bruker operativsystemmekanismer.
- State sa er en beregning som returnerer en verdi av type a og har tilgang til muterbar tilstand av type s.
- Kanskje a. Kanskje-monaden uttrykker en beregning som kan avbrytes når som helst ved å returnere Ingenting. Vi vil imidlertid snakke om implementeringen av MonadPlus-klassen for Maybe-typen, som uttrykker den motsatte effekten: det er en beregning som kan avbrytes når som helst ved å returnere en spesifikk verdi.
Implementering av algoritmen
Vi har to datatyper, Graph a og Bigraph ab, hvorav den første representerer grafer med toppunkter merket med verdier av type a, og den andre representerer todelte grafer med toppunkter på venstre side merket med verdier av type a og høyre -side toppunkter merket med verdier av type b.
Dette er ikke typer fra Alga-biblioteket. Alga har ikke en representasjon for urettede todelte grafer. Jeg laget typene som dette for klarhetens skyld.
Vi trenger også hjelpefunksjoner med følgende signaturer:
-- Список соседей данной вершины.
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)Det er lett å se at hvis vi under dybden-første-søket fant en motstridende kant, ligger den odde syklusen på toppen av rekursjonsstakken. For å gjenopprette den, må vi derfor kutte av alt fra rekursjonsstabelen til den første forekomsten av det siste toppunktet.
Vi implementerer dybde-først-søk ved å opprettholde et assosiativt utvalg av deltall for hvert toppunkt. Rekursjonsstakken vil automatisk opprettholdes gjennom implementeringen av Functor-klassen til monaden vi har valgt: vi trenger bare å sette alle toppunktene fra banen inn i resultatet som returneres fra den rekursive funksjonen.
Min første idé var å bruke Enten monaden, som ser ut til å implementere akkurat de effektene vi trenger. Den første implementeringen jeg skrev var veldig nær dette alternativet. Faktisk hadde jeg fem forskjellige implementeringer på ett tidspunkt og slo meg til slutt på en annen.
For det første må vi opprettholde et assosiativt utvalg av aksjeidentifikatorer - dette er noe med staten. For det andre må vi kunne stoppe når en konflikt oppdages. Dette kan enten være Monad for enten eller MonadPlus for Kanskje. Hovedforskjellen er at enten kan returnere en verdi hvis beregningen ikke er stoppet, og Maybe returnerer kun informasjon om dette i dette tilfellet. Siden vi ikke trenger en egen verdi for suksess (den er allerede lagret i State), velger vi Kanskje. Og i det øyeblikket vi trenger å kombinere effekten av to monader, kommer de ut , som nettopp kombinerer disse effektene.
Hvorfor valgte jeg en så kompleks type? To grunner. For det første viser implementeringen seg å være veldig lik imperativ. For det andre må vi manipulere returverdien i tilfelle konflikt når vi går tilbake fra rekursjon for å gjenopprette den odde løkken, noe som er mye lettere å gjøre i Kanskje-monaden.
Dermed får vi denne implementeringen.
{-# 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)
Where-blokken er kjernen i algoritmen. Jeg skal prøve å forklare hva som skjer inni den.
- inVertex er den delen av dybde-først-søk hvor vi besøker toppunktet for første gang. Her tildeler vi et andelsnummer til toppunktet og kjører onEdge på alle naboer. Det er også her vi gjenoppretter anropsstakken: hvis msum returnerte en verdi, skyver vi vertex v dit.
- onEdge er delen hvor vi besøker kanten. Det kalles to ganger for hver kant. Her sjekker vi om toppunktet på den andre siden er besøkt, og besøker det hvis ikke. Ved besøk sjekker vi om kanten er motstridende. Hvis det er det, returnerer vi verdien - selve toppen av rekursjonsstabelen, hvor alle andre toppunkter da vil bli plassert ved retur.
- processVertex sjekker for hvert toppunkt om det har blitt besøkt og kjører inVertex på det hvis ikke.
- dfs kjører processVertex på alle toppunkter.
Det er alt.
Historien om ordet INLINE
Ordet INLINE var ikke i den første implementeringen av algoritmen; det dukket opp senere. Da jeg prøvde å finne en bedre implementering, fant jeg ut at den ikke-INLINE-versjonen var merkbart tregere på noen grafer. Med tanke på at semantisk sett burde funksjonene fungere likt, overrasket dette meg sterkt. Enda merkeligere, på en annen maskin med en annen versjon av GHC var det ingen merkbar forskjell.
Etter å ha brukt en uke på å lese GHC Core-utgangen, klarte jeg å fikse problemet med én linje med eksplisitt INLINE. På et tidspunkt mellom GHC 8.4.4 og GHC 8.6.5 sluttet optimizeren å gjøre dette på egen hånd.
Jeg hadde ikke forventet å møte slik skitt i Haskell-programmering. Men selv i dag gjør optimerere noen ganger feil, og det er vår jobb å gi dem hint. For eksempel, her vet vi at funksjonen skal være innebygd fordi den er innebygd i imperativversjonen, og dette er en grunn til å gi kompilatoren et hint.
Hva skjedde etterpå?
Så implementerte jeg Hopcroft-Karp-algoritmen med andre monader, og det var slutten på programmet.
Takket være Google Summer of Code fikk jeg praktisk erfaring med funksjonell programmering, som ikke bare hjalp meg å få en praksisplass på Jane Street sommeren etter (jeg er ikke sikker på hvor kjent dette stedet er selv blant Habrs kunnskapsrike publikum, men det er en av de få hvor du kan sommeren til å engasjere deg i funksjonell programmering), men introduserte meg også til den fantastiske verdenen av å bruke dette paradigmet i praksis, vesentlig forskjellig fra min erfaring i tradisjonelle språk.
Kilde: www.habr.com