I participated last summer in Google Summer of Code — a student program from Google. Every year, the organizers select several Open Source projects, including ones from well-known organizations such as Boost.org og The Linux Foundation. To work on these projects, Google invites students from around the world. 

As a participant in Google Summer of Code 2019, I worked on a project within the library Alga in collaboration with the organization Haskell.org, which focuses on the development of the Haskell language — one of the most recognized functional programming languages. Alga is a library that provides type-safe representations for graphs in Haskell. It is used, for example, in semantic — a library from GitHub that builds semantic trees, call graphs, and dependency graphs based on code, and can compare them. My project involved adding a type-safe representation for bipartite graphs and algorithms for that representation. 

In this post, I will describe my implementation of the algorithm for checking bipartiteness of a graph in Haskell. Although the algorithm is one of the most basic, its elegant implementation in a functional style took me several iterations and required quite a bit of work. As a result, I settled on an implementation with monadic transformers. 

Om meg

My name is Vasily Alfyorov, I am a fourth-year student at the Higher School of Economics in St. Petersburg. Previously on the blog, I wrote about my project on parameterized algorithms og about my trip to ZuriHac. Right now, I am doing an internship at Bergen University in Norway, where I am working on approaches to the problem of List Coloring. My interests include parameterized algorithms and functional programming.

On the implementation of the algorithm

Forord

Students participating in the program are strongly encouraged to maintain a blog. I was provided with a platform for my blog, Summer of Haskell. This article is a translation artikkel, written by me there in July in English, with a brief preface. 

The Pull Request with the code in question can be found here.

You can read about the results of my work (in English) her.

The post assumes the reader has a basic understanding of functional programming concepts, though I will try to remind all the terms used when the time comes.

Checking graphs for bipartiteness 

Algoritmen for å sjekke om en graf er bipartitt blir vanligvis presentert i algoritmekurs som en av de enkleste grafalgoritmene. Ideen er enkel: først plasserer vi på en eller annen måte toppene i venstre eller høyre del, og når vi oppdager en konfliktkant, bekrefter vi at grafen ikke er bipartitt.

Litt mer detalj: først plasserer vi en topp i venstre del. Det er åpenbart at alle nabotoppene til denne toppen må ligge i høyre del. Deretter må alle naboene til nabotoppene ligge i venstre del, og så videre. Vi fortsetter å tildele topper til delene til det ikke er noen flere topper igjen i komponenten med tilknytning til toppen vi begynte med. Deretter gjentar vi denne handlingen for alle tilknyttede komponenter.

Hvis det er en kant mellom topper som havner i samme del, er det ikke vanskelig å finne en odde syklus i grafen, noe som er velkjent (og ganske åpenbart) umulig i en bipartitt graf. Ellers har vi et gyldig delingsforhold, og derfor er grafen bipartitt.

Som regel implementeres denne algoritmen med breddesøk eller dybdesøk. I imperativer språk blir dybdesøk vanligvis brukt, da det er litt enklere og ikke krever ekstra datastrukturer. Jeg valgte også dybdesøk som den mer tradisjonelle løsningen.

Dermed har vi kommet frem til følgende ordning. Vi traverserer grafens topper med dybdesøk og tilordner dem til deler, og endrer delnummeret når vi beveger oss over en kant. Hvis vi prøver å tilordne en del til en topp som allerede har fått en del, kan vi trygt påstå at grafen ikke er bipartitt. I det øyeblikket alle topper har fått en del og vi har sett på alle kanter, har vi et godt delingsforhold.

Renslighet i beregninger

I Haskell antar vi at alle beregninger er rene. Men hvis dette virkelig var tilfelle, ville vi ikke hatt muligheten til å skrive noe ut på skjermen. Generelt er rene beregninger så late at det ikke finnes noen ren grunn til å beregne noe. Alle beregninger som skjer i programmet, blir på en eller annen måte tvunget inn i den "uren" IO-monaden.

Monader er en måte å representere beregninger med effekter i Haskell. Forklaringen på hvordan de fungerer, går utover dette innlegget. En god og klar beskrivelse kan leses på engelsk here.

Her vil jeg bemerke at mens noen monader, som IO, er implementert ved hjelp av kompilatorens magi, er nesten alle andre implementert programmatisk og all beregning innen dem er ren.

Det finnes mange typer effekter, og hver har sin egen monade. Dette er en veldig sterk og vakker teori: alle monader implementerer det samme grensesnittet. Vi vil snakke om de tre følgende monadene:

• Either e a — en beregning som returnerer en verdi av type a eller kaster et unntak av type e. Adferden til denne monaden ligner på arbeidet med unntak i imperativ programmering: feil kan fanges eller videresendes. Den viktigste forskjellen er at monaden er fullt logisk implementert i standardbiblioteket i Haskell, mens imperativ programmering vanligvis bruker operativsystemets mekanismer.
• State s a — en beregning som returnerer en verdi av type a og har tilgang til en modifiserbar tilstand av type s.
• Maybe a. Maybe-monaden uttrykker en beregning som når som helst kan bli avbrutt med retur av Nothing. Men vi vil snakke om implementeringen av MonadPlus-klassen for Maybe-typen, som uttrykker den motsatte effekten: dette er en beregning som kan bli avbrutt med retur av en spesifikk verdi.

Implementering av algoritmen

Vi har to datatyper, Graph a og Bigraph a b, der den første representerer grafer med noder merket med verdier av typen a, mens den andre representerer bipartite grafer med noder i venstre del merket med verdier av typen a og noder i høyre del merket med verdier av typen b.

Disse er ikke typer fra Alga-biblioteket. Det finnes ingen representasjon for ikke-rettede bipartite grafer i Alga. Typene ble laget slik for å være klare.

Vi vil også trenge hjelpefunksjoner med følgende signaturer:

-- Listen til naboene til dette toppunktet.
neighbours :: Ord a => a -> Graph a -> [a]

-- Bygg et bipartitt graf basert på grafen og funksjonen som for hver toppunkt
-- gir dens del og merke i den nye delen, og ignorerer konfliktende kanter.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
                             -> Graph a
                             -> Bigraph b c

-- Listen over toppunktene i grafen
vertexList :: Ord a => Graph a -> [a]
Signaturen til funksjonen vi skal skrive ser slik ut:

type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)

Det er lett å se at hvis vi i løpet av dybde-søkingen finner en konfliktende kant, så ligger den oddetelig syklusen øverst i rekursjonsstakken. For å gjenopprette den, må vi kutte av alt fra rekursjonsstakken frem til det første forekomsten av det siste toppunktet.

Vi implementerer dybde-søk med en assosiativ matrise av delnummer for hvert toppunkt. Rekursjonsstakken vil bli automatisk vedlikeholdt gjennom implementeringen av klassen Functor i den monaden vi velger: vi må bare legge alle toppunktene fra stien inn i resultatet som returneres fra den rekursive funksjonen.

Min første idé var å bruke monaden Either, som ser ut til å implementere nettopp de effektene vi trenger. Den første implementeringen jeg skrev var veldig nær denne varianten. Faktisk hadde jeg fem forskjellige implementeringer på et tidspunkt, og jeg endte opp med en annen.

For det første må vi vedlikeholde en assosiativ matrise av delidentifikatorer - dette handler om State. For det andre må vi kunne stoppe når vi oppdager en konflikt. Dette kan være enten Monad for Either, eller MonadPlus for Maybe. Den hovedforskjellen er at Either kan returnere en verdi hvis beregningen ikke ble stoppet, mens Maybe kun returnerer informasjon om det. Ettersom vi ikke trenger en separat verdi ved suksess (den er allerede lagret i State), velger vi Maybe. Og i det øyeblikket vi trenger å kombinere effektene av to monader, dukker monad-transformere, som nettopp kombinerer disse effektene.

Hvorfor valgte jeg en så kompleks type? To grunner. For det første, implementasjonen blir svært lik den imperativer. For det andre, må vi manipulere verdien som returneres i tilfelle konflikt, når vi går tilbake fra rekursjon for å gjenopprette en odde syklus, og det er mye enklere å gjøre i Maybe-monaden.

Dermed får vi en slik implementasjon.

{-# 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 kjernen i algoritmen. Jeg vil forsøke å forklare hva som skjer inni den.

• inVertex er delen av dybde-først søk der vi besøker en toppunkt for første gang. Her gir vi toppunktet et partisjonsnummer og kjører onEdge for alle naboene. Dette er også stedet hvor vi gjenoppretter kallstakken: hvis msum returnerte en verdi, legger vi til toppunktet v der.
• onEdge — det er delen der vi besøker kanten. Den blir kalt to ganger for hver kant. Her sjekker vi om vi har besøkt toppen fra den andre siden, og besøker den hvis ikke. Hvis den er besøkt, sjekker vi om kanten er konfliktfylt. Hvis den er, returnerer vi verdien — toppen av rekursjonsstakken der de andre toppene vil henge under retur.
• processVertex sjekker om hver topp er besøkt, og starter inVertex på den hvis ikke.
• dfs starter processVertex på alle topper.

That's all.

Historien om ordet INLINE

Ordet INLINE fantes ikke i den første implementeringen av algoritmen, det dukket opp senere. Da jeg prøvde å finne en bedre implementering, oppdaget jeg at for noen grafer fungerte versjonen uten INLINE merkbart saktere. Med tanke på at semantisk må funksjonene oppføre seg likt, overrasket dette meg sterkt. Enda merkeligere var det at på en annen maskin med en annen versjon av GHC var det ikke merkbare forskjeller.

Etter å ha brukt en uke på å lese utdataene fra GHC Core, klarte jeg å fikse problemet med én linje med eksplisitt INLINE. På et tidspunkt mellom GHC 8.4.4 og GHC 8.6.5 sluttet optimalisatoren å gjøre dette automatisk.

Jeg forventet ikke å møte slik rot i programmering med Haskell. Likevel gjør optimizere fortsatt feil selv i vår tid, og det er vår oppgave å gi dem hint. For eksempel vet vi her at funksjonen må bli inlinet, ettersom den er inlinet i den imperativ versjonen, og dette er en grunn til å gi kompilatoren et hint.

Hva skjedde videre?

Videre implementerte jeg Hopcroft-Karp-algoritmen med andre monader, og programmet var ferdig der.

Takket være Google Summer of Code fikk jeg praktisk erfaring med funksjonell programmering, noe som ikke bare hjalp meg med å gå videre til en praksisplass hos Jane Street neste sommer (usikker på hvor kjent dette stedet er, selv blant den kjente publikum på Habr, men det er et av de få stedene hvor man kan jobbe med funksjonell programmering om sommeren), men også introduserte meg for den fascinerende verden av anvendelsen av denne paradigmen i praksis, som er betydelig forskjellig fra min erfaring med tradisjonelle språk.

Kilde: habr.com