Sidste sommer deltog jeg i — et program for studerende fra Google. Hvert år vælger arrangørerne adskillige Open Source-projekter, herunder fra velkendte organisationer som og . For at arbejde på disse projekter inviterer Google studerende fra hele verden.
Som deltager i Google Summer of Code 2019 lavede jeg et projekt inden for biblioteket sammen med organisationen , der arbejder på udviklingen af Haskell-sproget — et af de mest kendte funktionelle programmeringssprog. Alga er et bibliotek, der giver repræsentation for grafer i Haskell. Det bruges for eksempel i — et bibliotek fra Github, der bygger semantiske træer, opkalds- og afhængighedsgrafer og kan sammenligne dem. Mit projekt bestod i at tilføje en type-sikret repræsentation for bipartite grafer og algoritmer til denne repræsentation.
I dette indlæg vil jeg beskrive min implementering af algoritmen til kontrol af grafbipartith på Haskell. Selvom algoritmen er en af de mest grundlæggende, tog det mig flere iterationer at få en smuk implementering i funktionel stil, hvilket krævede ret meget arbejde. Resultatet blev en implementering med monad-transformere.
Om mig
Mit navn er Vasily Alferov, og jeg er studerende på fjerde år på Peter den Stores Universitet. Tidligere har jeg skrevet i bloggen og . Lige nu er jeg i praktik ved i Norge, hvor jeg arbejder med tilgange til opgaven . Mine interesser inkluderer parametrede algoritmer og funktionel programmering.
Om algoritmeimplementeringen
Forord
Studerende, der deltager i programmet, anbefales kraftigt at føre en blog. Jeg fik en platform til bloggen . Denne artikel er en oversættelse , som jeg skrev dér i juli på engelsk, med en kort indledning.
Pull Request med koden, som omtales, kan findes .
Resultaterne af mit arbejde kan læses (på engelsk) .
Indlægget forudsætter, at læseren er bekendt med grundlæggende begreber inden for funktionel programmering, selvom jeg vil prøve at minde om alle anvendte termer, når tiden kommer.
Kontrol af grafer for bipartithed
Algoritmen til at kontrollere et graf for bipartithed præsenteres normalt i algoritmekurser som en af de enkleste grafalgoritmer. Ideen er ligetil: først placerer vi på en eller anden måde hjørnerne i venstre eller højre del, og når vi opdager en konfliktende kant, hævder vi, at grafen ikke er bipartit.
Lidt mere detaljeret: først placerer vi et hjørne i venstre del. Åbenlyst skal alle naboer til dette hjørne være i højre del. Derefter skal alle naboer til naboerne til dette hjørne være i venstre del, og så videre. Vi fortsætter med at tildele hjørner til dele, så længe der er hjørner i den sammenhængende komponent, vi startede med, som endnu ikke har fået tildelt naboer. Derefter gentager vi denne handling for alle sammenhængende komponenter.
Hvis der er en kant mellem to hjørner, der er havnet i samme del, er det ikke svært at finde en ulige cykel i grafen, hvilket er velkendt (og ganske åbenlyst) umuligt i en bipartit graf. Ellers har vi en korrekt opdeling i dele, hvilket betyder, at grafen er bipartit.
Som regel implementeres denne algoritme ved hjælp af eller . I imperative sprog anvender man som regel dybdesøgning, da det er lidt enklere og ikke kræver yderligere datstrukturer. Jeg har også valgt dybdesøgning som den mere traditionelle tilgang.
Hermed er vi kommet til følgende skema. Vi gennemgår hjørnerne af grafen ved hjælp af dybdesøgning og tildeler dem dele, mens vi skifter partitionsnummer, når vi bevæger os over en kant. Hvis vi forsøger at tildele en del til et hjørne, der allerede er tildelt en del, kan vi roligt konkludere, at grafen ikke er bipartit. I det øjeblik, hvor alle hjørner er tildelt en del, og vi har set på alle kanterne, har vi en god opdeling.
Rensning af beregninger
I Haskell antager vi, at alle beregninger er rene. Men hvis det virkelig var tilfældet, ville vi ikke have mulighed for at udskrive noget på skærmen. Generelt er rene beregninger så dovne, at der ikke findes nogen ren årsag til at foretage beregninger. Alle beregninger, der finder sted i programmet, bliver på en eller anden måde forceret ind i den "urene" IO-monade.
Monader er en måde at repræsentere beregninger med effekter i Haskell. Forklaringen på, hvordan de fungerer, går ud over dette indlæg. En god og klar beskrivelse kan læses på engelsk. .
Her vil jeg bemærke, at mens nogle monader, såsom IO, er implementeret via compiler-magi, så er næsten alle andre implementeret programmæssigt, og alle beregninger i dem er rene.
Der findes mange effekter, og hver har sin egen monade. Dette er en meget stærk og smuk teori: alle monader implementerer det samme interface. Vi vil tale om følgende tre monader:
- Either e a — en beregning, der returnerer en værdi af typen a eller kaster en undtagelse af typen e. Adfærden af denne monade ligner meget arbejdet med undtagelser i imperativsprog: fejl kan fanges eller videregives. Den væsentligste forskel er, at monaden er fuldstændig logisk implementeret i standardbiblioteket i Haskell, mens der i imperativsprog typisk anvendes operativsystemets mekanismer.
- State s a — en beregning, der returnerer en værdi af typen a og har adgang til en ændrbar tilstand af typen s.
- Maybe a. Monaden Maybe udtrykker en beregning, der kan blive afbrudt når som helst ved at returnere Nothing. Vi vil dog tale om implementeringen af klassen MonadPlus for typen Maybe, der udtrykker den modsatte effekt: det er en beregning, der kan blive afbrudt når som helst ved at returnere en bestemt værdi.
Implementeringen af algoritmen
Vi har to datatyper, Graph a og Bigraph a b, hvor den første repræsenterer grafer med noder mærket med værdier af typen a, mens den anden repræsenterer bipartite grafer med noder på venstre side mærket med værdier af typen a og noder på højre side mærket med værdier af typen b.
Disse er ikke typer fra Alga. Der er ingen repræsentation for urettede bipartite grafer i Alga. Jeg har lavet typerne således for tydelighed.
Vi vil også have brug for hjælpefunktioner med følgende signaturer:
-- Liste af naboer til denne knude.
neighbours :: Ord a => a -> Graph a -> [a]
-- Byg en bipartit graf ud fra grafen og en funktion, for hver knude
-- der udgiver dens del og markering i den nye del, ignorerer konfliktende kanter.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Liste over knuder i grafen
vertexList :: Ord a => Graph a -> [a]
Signaturen for den funktion, vi skal skrive, ser således ud:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Det er ikke svært at bemærke, at hvis vi under dybde-først-søgningen fandt en konfliktende kant, ligger den ulige cyklus øverst på recursionsstakken. Således, for at genskabe den, skal vi skære alt fra stakken indtil den første optræden af den sidste knude.
Vi implementerer dybde-først-søgning ved at vedholde et associativt array af delnummer for hver knude. Recursionsstakken vil automatisk blive vedligeholdt gennem implementeringen af Functor-klassen for den valgte monade: vi skal blot placere alle knuder fra stien i resultatet, som returneres fra den rekursive funktion.
Min første idé var at bruge monaden Either, som tilsyneladende implementerer netop de effekter, vi har brug for. Den første implementering, jeg skrev, var meget tæt på denne version. Faktisk havde jeg fem forskellige implementeringer på et tidspunkt, og jeg endte med at vælge en anden.
For det første skal vi vedholde et associativt array af indholds-id'er — det handler om State. For det andet skal vi kunne stoppe i tilfælde af at opdage en konflikt. Dette kan være enten Monad for Either eller MonadPlus for Maybe. Den primære forskel er, at Either kan returnere en værdi, hvis beregningen ikke blev stoppet, mens Maybe i så fald kun returnerer information om dette. Da vi ikke har brug for en separat værdi i tilfælde af succes (den er allerede gemt i State), vælger vi Maybe. Og lige når vi skal kombinere effekterne af to monader, dukker , som netop kombinerer disse effekter, op.
Hvorfor valgte jeg en så kompleks type? To grunde. For det første, implementeringen ligner meget den imperativ. For det andet, vi skal manipulere værdien, der returneres i tilfælde af konflikten, når vi tilbagegår fra rekursionen for at genskabe en ulige cyklus, og det er meget lettere at gøre det i Maybe monaden.
Dermed får vi en sådan implementering.
{-# 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)
Blokken where — er kernen i algoritmen. Jeg vil forsøge at forklare, hvad der foregår inden i den.
- inVertex — er delen af dybdesøgningen, hvor vi besøger en spids for første gang. Her tildeler vi spidsen et parts-nummer og starter onEdge for alle naboer. Det er også her, vi genskaber stakken af kald: hvis msum returnerede en værdi, tilføjer vi spidsen v der.
- onEdge er den del, hvor vi besøger kanten. Den kaldes to gange for hver kant. Her tjekker vi, om toppen fra den anden side er besøgt, og besøger den, hvis den ikke er. Hvis den er besøgt, tjekker vi, om kanten er konfliktfyldt. Hvis den er, returnerer vi værdien — toppen af rekursionsstakken, hvor alle de øvrige toppe derefter vil blive tilføjet ved tilbagevenden.
- processVertex tjekker for hver topp, om den er besøgt, og starter inVertex på den, hvis den ikke er.
- dfs starter processVertex på alle toppe.
Det var alt.
Historien bag ordet INLINE
Ordet INLINE var ikke med i den første implementering af algoritmen, det dukkede op senere. Da jeg prøvede at finde en bedre implementering, opdagede jeg, at i nogle grafer fungerer versionen uden INLINE mærkbart langsommere. Med tanke på, at semantisk set skal funktionerne fungere ens, forundrede det mig meget. Endnu mærkeligere var det, at på en anden maskine med en anden version af GHC var der ikke nogen mærkbar forskel.
Efter at have brugt en uge på at læse output fra GHC Core, kunne jeg løse problemet med en enkelt linje ved at bruge eksplicit INLINE. På et tidspunkt mellem GHC 8.4.4 og GHC 8.6.5 stoppede optimereren med at gøre dette automatisk.
Jeg havde ikke forventet at finde sådan en rod i programmering i Haskell. Dog laver optimerere stadig nogle fejl selv i dag, og det er vores opgave at give dem tips. For eksempel ved vi her, at funktionen skal være inlinet, da den er inlinet i den imperative version, og det er grundlaget for at give compileren et hint.
Hvad skete der derefter?
Derefter implementerede jeg Hopcroft-Karp algoritmen med andre monader, og programmet sluttede her.
Takket være Google Summer of Code fik jeg praktisk erfaring med funktionel programmering, som ikke kun hjalp mig med at få en praktikplads hos Jane Street den følgende sommer (jeg er ikke sikker på, hvor kendt dette sted er, selv blandt det velkendte publikum på Habr, men det er et af de få steder, hvor man kan beskæftige sig med funktionel programmering om sommeren), men også introducerede mig til den fantastiske verden af anvendelse af denne paradigm i praksis, som er betydeligt forskellig fra min oplevelse med traditionelle sprog.
Kilde: habr.com
