Sidste sommer deltog jeg i - et program for studerende fra Google. Hvert år udvælger arrangørerne flere Open Source projekter, blandt andet fra så kendte organisationer som и . Google inviterer studerende fra hele verden til at arbejde på disse projekter.
Som deltager i Google Summer of Code 2019 lavede jeg et projekt på biblioteket med organisationen , som udvikler Haskell-sproget - et af de mest berømte funktionelle programmeringssprog. Alga er et bibliotek, der repræsenterer repræsentation for grafer i Haskell. Det bruges f.eks - et Github-bibliotek, der bygger semantiske træer, opkalds- og afhængighedsgrafer baseret på kode og kan sammenligne dem. Mit projekt var at tilføje en typesikker repræsentation for todelte grafer og algoritmer til den repræsentation.
I dette indlæg vil jeg fortælle om min implementering af en algoritme til kontrol af en graf for bipartiteness i Haskell. Selvom algoritmen er en af de mest basale, tog det mig flere gentagelser at implementere den smukt i en funktionel stil og krævede en del arbejde. Som et resultat afgjorde jeg en implementering med monadetransformatorer.
Om Mig
Mit navn er Vasily Alferov, jeg er fjerdeårsstuderende ved St. Petersburg HSE. Tidligere på bloggen skrev jeg и . Lige nu er jeg i praktik kl i Norge, hvor jeg arbejder med tilgange til problemet . Mine interesser omfatter parametriserede algoritmer og funktionel programmering.
Om implementeringen af algoritmen
Forord
Studerende, der deltager i programmet, opfordres kraftigt til at blogge. De gav mig en platform til bloggen . Denne artikel er en oversættelse , skrevet af mig der i juli på engelsk, med et kort forord.
Pull Request med den pågældende kode kan findes .
Du kan læse om resultaterne af mit arbejde (på engelsk) .
Dette indlæg forudsætter, at læseren er bekendt med de grundlæggende begreber i funktionel programmering, selvom jeg vil forsøge at huske alle de anvendte termer, når tiden kommer.
Kontrol af grafer for bipartiteness
En algoritme til kontrol af en graf for todelthed gives normalt i et kursus om algoritmer som en af de enkleste grafalgoritmer. Hans idé er ligetil: Først sætter vi på en eller anden måde hjørner i venstre eller højre del, og når der findes en modstridende kant, hævder vi, at grafen ikke er todelt.
Lidt flere detaljer: først sætter vi noget toppunkt i den venstre del. Det er klart, at alle naboerne til dette toppunkt skal ligge i højre lap. Yderligere skal alle naboerne til naboerne til dette vertex ligge i venstre lap og så videre. Vi fortsætter med at tildele delinger til toppunkter, så længe der stadig er toppunkter i den tilsluttede komponent af toppunktet, vi startede med, som vi ikke har tildelt naboer til. Vi gentager derefter denne handling for alle tilsluttede komponenter.
Hvis der er en kant mellem hjørner, der falder ind i den samme partition, er det ikke svært at finde en ulige cyklus i grafen, hvilket er almindeligt kendt (og helt åbenlyst) umuligt i en todelt graf. Ellers har vi en korrekt partition, hvilket betyder, at grafen er todelt.
Typisk implementeres denne algoritme vha eller . På imperative sprog bruges dybde-først-søgning normalt, da det er lidt enklere og ikke kræver yderligere datastrukturer. Jeg valgte også dybde-først-søgning, da det er mere traditionelt.
Dermed kom vi frem til følgende skema. Vi krydser hjørnerne af grafen ved at bruge dybde-først-søgning og tildeler delinger til dem, og ændrer nummeret på delingen, når vi bevæger os langs kanten. Hvis vi forsøger at tildele en andel til et toppunkt, der allerede har en andel tildelt, kan vi roligt sige, at grafen ikke er todelt. I det øjeblik alle hjørner er tildelt en andel, og vi har set på alle kanterne, har vi en god partition.
Renhed af beregninger
I Haskell antager vi, at alle beregninger er ren. Men hvis dette virkelig var tilfældet, ville vi ikke have mulighed for at udskrive noget på skærmen. Overhovedet, ren beregninger er så dovne, at der ikke er en ren grunde til at beregne noget. Alle beregninger, der forekommer i programmet, er på en eller anden måde tvunget ind "uren" monaden IO.
Monader er en måde at repræsentere beregninger med effekter i Haskell. At forklare, hvordan de fungerer, er uden for dette indlægs rammer. En god og overskuelig beskrivelse kan læses på engelsk .
Her vil jeg pointere, at mens nogle monader, såsom IO, er implementeret gennem compiler-magi, er næsten alle andre implementeret i software, og alle beregninger i dem er rene.
Der er en masse effekter, og hver har sin egen monade. Dette er en meget stærk og smuk teori: alle monader implementerer den samme grænseflade. Vi vil tale om følgende tre monader:
- Enten er e a en beregning, der returnerer en værdi af type a eller kaster en undtagelse af type e. Denne monades adfærd ligner meget undtagelseshåndtering i imperative sprog: fejl kan fanges eller videregives. Den største forskel er, at monaden er fuldstændig logisk implementeret i standardbiblioteket i Haskell, mens imperative sprog normalt bruger operativsystemmekanismer.
- Tilstand s a er en beregning, der returnerer en værdi af type a og har adgang til foranderlig tilstand af type s.
- Måske a. Måske-monaden udtrykker en beregning, der til enhver tid kan afbrydes ved at returnere Intet. Vi vil dog tale om implementeringen af MonadPlus-klassen for Maybe-typen, som udtrykker den modsatte effekt: det er en beregning, der til enhver tid kan afbrydes ved at returnere en bestemt værdi.
Implementering af algoritmen
Vi har to datatyper, graf a og bigraf a b, hvoraf den første repræsenterer grafer med toppunkter mærket med værdier af type a, og den anden repræsenterer todelte grafer med venstre hjørner mærket med værdier af type a og højre -sidespidser mærket med værdier af type b.
Det er ikke typer fra Alga-biblioteket. Alga har ikke en repræsentation for urettede todelte grafer. Jeg lavede typer som denne for klarhedens skyld.
Vi skal også bruge hjælpefunktioner 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 let at se, at hvis vi under dybden-første-søgningen fandt en modstridende kant, ligger den ulige cyklus oven på rekursionsstakken. For at genoprette den skal vi derfor afskære alt fra rekursionsstakken op til den første forekomst af det sidste toppunkt.
Vi implementerer dybde-først-søgning ved at opretholde en associativ række af andelsnumre for hvert toppunkt. Rekursionsstakken vil automatisk blive vedligeholdt gennem implementeringen af Functor-klassen for den monade, vi har valgt: vi behøver kun at lægge alle hjørnerne fra stien ind i resultatet, der returneres fra den rekursive funktion.
Min første idé var at bruge enten monaden, som ser ud til at implementere præcis de effekter, vi har brug for. Den første implementering, jeg skrev, var meget tæt på denne mulighed. Faktisk havde jeg fem forskellige implementeringer på et tidspunkt og sluttede mig til en anden.
For det første skal vi vedligeholde et associativt array af aktieidentifikatorer - det er noget om stat. For det andet skal vi kunne stoppe, når en konflikt opdages. Dette kan enten være Monad for enten eller MonadPlus for måske. Den væsentligste forskel er, at enten kan returnere en værdi, hvis beregningen ikke er blevet stoppet, og Maybe returnerer kun information om dette i dette tilfælde. Da vi ikke har brug for en separat værdi for succes (den er allerede gemt i State), vælger vi Måske. Og i det øjeblik, hvor vi skal kombinere virkningerne af to monader, kommer de ud , som netop kombinerer disse effekter.
Hvorfor valgte jeg en så kompleks type? To grunde. For det første viser implementeringen sig at være meget lig imperativ. For det andet er vi nødt til at manipulere returværdien i tilfælde af konflikt, når vi vender tilbage fra rekursion for at genoprette den ulige løkke, hvilket er meget nemmere at gøre i Måske-monaden.
Dermed får vi denne 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 <- 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 kernen i algoritmen. Jeg vil forsøge at forklare, hvad der sker inde i den.
- inVertex er den del af dybde-først-søgning, hvor vi besøger toppunktet for første gang. Her tildeler vi et andelsnummer til toppunktet og kører onEdge på alle naboer. Det er også her, vi gendanner opkaldsstakken: hvis msum returnerede en værdi, skubber vi vertex v dertil.
- onEdge er den del, hvor vi besøger kanten. Det kaldes to gange for hver kant. Her tjekker vi om toppunktet på den anden side er besøgt, og besøger det hvis ikke. Hvis det besøges, tjekker vi, om kanten er modstridende. Hvis det er, returnerer vi værdien - selve toppen af rekursionsstakken, hvor alle andre hjørner så vil blive placeret ved returnering.
- processVertex kontrollerer for hvert vertex, om det er besøgt, og kører inVertex på det, hvis ikke.
- dfs kører processVertex på alle hjørner.
Det er alt.
Historien om ordet INLINE
Ordet INLINE var ikke i den første implementering af algoritmen; det dukkede op senere. Da jeg forsøgte at finde en bedre implementering, fandt jeg ud af, at den ikke-INLINE-version var mærkbart langsommere på nogle grafer. I betragtning af at semantisk set burde funktionerne fungere ens, overraskede dette mig meget. Endnu mærkeligere, på en anden maskine med en anden version af GHC var der ingen mærkbar forskel.
Efter at have brugt en uge på at læse GHC Core-outputtet, var jeg i stand til at løse problemet med en linje med eksplicit INLINE. På et tidspunkt mellem GHC 8.4.4 og GHC 8.6.5 stoppede optimizeren med at gøre dette på egen hånd.
Jeg forventede ikke at støde på sådan noget snavs i Haskell-programmering. Men selv i dag laver optimeringsværktøjer nogle gange fejl, og det er vores opgave at give dem hints. For eksempel ved vi her, at funktionen skal være inlinet, fordi den er inlinet i imperativversionen, og det er en grund til at give compileren et hint.
Hvad skete der så?
Så implementerede jeg Hopcroft-Karp-algoritmen med andre monader, og det var slutningen på programmet.
Takket være Google Summer of Code fik jeg praktisk erfaring med funktionel programmering, hvilket ikke kun hjalp mig med at komme i praktik på Jane Street den følgende sommer (jeg er ikke sikker på, hvor kendt dette sted selv er blandt Habrs kyndige publikum, men det er en af de få, hvor du kan sommer til at engagere dig i funktionel programmering), men introducerede mig også til den vidunderlige verden med at anvende dette paradigme i praksis, væsentligt anderledes end min erfaring med traditionelle sprog.
Kilde: www.habr.com