Vorig jaar zomer nam ik deel aan — een programma voor studenten van Google. Jaarlijks selecteren de organisatoren verschillende Open Source-projecten, waaronder die van bekende organisaties zoals en . Voor deze projecten nodigt Google studenten van over de hele wereld uit.
Als deelnemer aan Google Summer of Code 2019 werkte ik aan een project binnen de bibliotheek met de organisatie , die zich richt op de ontwikkeling van de programmeertaal Haskell — een van de meest bekende functionele programmeertalen. Alga is een bibliotheek die representaties voor grafen in Haskell biedt. Het wordt bijvoorbeeld gebruikt in — een bibliotheek van GitHub die semantische bomen, aanroep- en afhankelijkheidsgrafen opbouwt en in staat is ze te vergelijken. Mijn project bestond uit het toevoegen van een typeveilige representatie voor bipartiete grafen en algoritmen voor deze representatie.
In deze post zal ik mijn implementatie van het algoritme voor het controleren van een graf op bipartiteness in Haskell beschrijven. Ondanks dat het algoritme een van de meest basale is, kostte het me verschillende iteraties om een mooie implementatie in functionele stijl te bereiken, wat behoorlijk wat werk vergde. Uiteindelijk koos ik voor een implementatie met monadische transformatoren.
Over mij
Mijn naam is Vasily Alfёrov, ik ben een vierdejaars student aan de Higher School of Economics in St. Petersburg. Eerder schreef ik in deze blog en . Op dit moment ben ik op een stage aan de in Noorwegen, waar ik werk aan benaderingen van het probleem van . Mijn interesses omvatten geparametriseerde algoritmen en functioneel programmeren.
Over de implementatie van het algoritme
Voorwoord
Studenten die deelnemen aan het programma wordt sterk aangeraden om een blog te onderhouden. Voor mijn blog kreeg ik het platform . Dit artikel is een vertaling van , die ik daar in juli in het Engels schreef, met een kleine inleiding.
De Pull Request met de code waar het om gaat, is te vinden .
Over de resultaten van mijn werk is meer te lezen (in het Engels) .
De post veronderstelt dat de lezer bekend is met de basisconcepten van functioneel programmeren, hoewel ik zal proberen alle gebruikte termen op te frissen wanneer het moment daar is.
Controleren van grafen op bipartiteit
Het algoritme voor het controleren van een graaf op bipartiteit wordt meestal in cursussen algoritmen gegeven als een van de eenvoudigste grafalgoritmen. Het idee is eenvoudig: eerst plaatsen we op de een of andere manier de knopen in de linker of rechter partitie, en bij het ontdekken van een conflict-einde bevestigen we dat de graaf niet bipartiet is.
Om iets dieper in te gaan: we plaatsen eerst een bepaalde knoop in de linker partitie. Voor de hand liggend is dat alle buren van deze knoop zich in de rechter partitie moeten bevinden. Vervolgens moeten alle buren van de buren van deze knoop zich in de linker partitie bevinden, enzovoort. We blijven knopen toewijzen aan partities totdat er in de samenhangende component met de knoop waarmee we zijn begonnen, nog knopen zijn waarvoor we buren niet hebben toegewezen. Daarna herhalen we deze actie voor alle samenhangende componenten.
Als er een lijn is tussen knopen die in dezelfde partitie zijn geplaatst, is het niet moeilijk om in de graaf een oneven cyclus te vinden, wat algemeen bekend is (en vrij voor de hand liggend) onmogelijk is in een bipartiete graaf. Anders hebben we een correcte opsplitsing in partities, wat betekent dat de graaf bipartiet is.
Over het algemeen wordt dit algoritme geïmplementeerd met behulp van of . In imperatieve talen wordt meestal diepte-eerste zoekalgoritme gebruikt, omdat dit iets eenvoudiger is en geen extra datastructuren vereist. Ik koos ook voor diepte-eerste zoekalgoritme omdat dit meer traditioneel is.
Zo zijn we tot het volgende schema gekomen. We doorlopen de knopen van de graaf met behulp van diepte-eerste zoekalgoritme en wijzen ze partities toe, waarbij we het partitie-nummer veranderen wanneer we een lijn overgaan. Als we proberen een partitie toe te wijzen aan een knoop die al een partitie heeft, kunnen we met vertrouwen stellen dat de graaf niet bipartiet is. Op het moment dat alle knopen een partitie hebben gekregen en we naar alle lijnen hebben gekeken, hebben we een goede opsplitsing.
Reinheid van berekeningen
In Haskell veronderstellen we dat alle berekeningen rein zijn. Als dat echt zo was, zouden we niet in staat zijn om iets op het scherm af te drukken. Over het algemeen zijn pure berekeningen zo lui dat er geen enkele pure reden is om iets te berekenen. Alle berekeningen die in het programma plaatsvinden, worden op de een of andere manier geforceerd in een "onzuivere" IO-monade.
Monaden zijn een manier om berekeningen met effecten voor te stellen. In Haskell. An explanation of how they work goes beyond this post. A good and clear description can be found in English. .
Here I want to note that while some monads, such as IO, are implemented through compiler magic, almost all the others are implemented programmatically and all computations within them are pure.
There are many types of effects, each having its own monad. This is a very strong and beautiful theory: all monads implement the same interface. We will discuss the following three monads:
- Either e a — a computation that returns a value of type a or throws an exception of type e. The behavior of this monad is very similar to working with exceptions in imperative languages: errors can be caught or passed on. The main difference is that the monad is fully logically implemented in the standard library in Haskell, while in imperative languages, system mechanisms are usually used.
- State s a — a computation that returns a value of type a and has access to mutable state of type s.
- Maybe a. The Maybe monad expresses a computation that can be interrupted at any moment by returning Nothing. However, we will discuss the implementation of the MonadPlus class for the Maybe type, which expresses the opposite effect: this is a computation that can be interrupted at any moment by returning a specific value.
Implementation of the algorithm
We have two data types, Graph a and Bigraph a b, the first of which represents graphs with vertices labeled with values of type a, and the second represents bipartite graphs with vertices on the left side labeled with values of type a and vertices on the right side labeled with values of type b.
These are not types from the Alga library. Alga does not have a representation for undirected bipartite graphs. I made the types this way for clarity.
We will also need auxiliary functions with the following signatures:
-- Lijst van buren van deze top.
neighbours :: Ord a => a -> Graph a -> [a]
-- Bouw een bipartiete grafiek op basis van de grafiek en de functie, die voor elke top
-- haar deel en markering in het nieuwe deel geeft, waarbij conflicterende randen genegeerd worden.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Lijst van toppen in de grafiek
vertexList :: Ord a => Graph a -> [a]
De handtekening van de functie die we gaan schrijven ziet er als volgt uit:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Het is niet moeilijk op te merken dat als we tijdens een dieptezoektocht een conflicterende rand hebben gevonden, de oneven cyclus bovenop de recursiestack ligt. Om deze te herstellen, moeten we alles van de recursiestack afsnijden tot de eerste verschijning van de laatste top.
We implementeren dieptezoektocht door een associatieve array van deelnummer voor elke top te onderhouden. De recursiestack wordt automatisch onderhouden via de implementatie van de Functor-klasse van de monade die we hebben gekozen: we hoeven alleen maar alle toppen van het pad in het resultaat te plaatsen, dat wordt geretourneerd door de recursieve functie.
Mijn eerste idee was om de Either-monade te gebruiken, die precies die effecten lijkt te implementeren die we nodig hebben. De eerste implementatie die ik schreef, was heel dicht bij deze optie. Eigenlijk had ik op een gegeven moment vijf verschillende implementaties, en uiteindelijk besloot ik voor een andere.
Ten eerste moeten we een associatieve array van deelidentificatoren onderhouden — dit heeft te maken met State. Ten tweede moeten we in staat zijn om te stoppen als er een conflict wordt ontdekt. Dit kan een Monad voor Either zijn, of MonadPlus voor Maybe. Het belangrijkste verschil is dat Either een waarde kan retourneren als de berekening niet is gestopt, terwijl Maybe in dat geval alleen informatie daarover retourneert. Aangezien we geen aparte waarde nodig hebben in het geval van succes (die is al opgeslagen in State), kiezen we voor Maybe. En op het moment dat we de effecten van twee monaden moeten combineren, komen , die precies deze effecten combineren.
Waarom heb ik zo'n ingewikkeld type gekozen? Twee redenen. Ten eerste lijkt de implementatie erg op imperatieve programmering. Ten tweede moeten we het geretourneerde waarde in het geval van conflicten manipuleren, bij het terugkeren uit de recursie om een oneven cyclus te herstellen, en dat is veel eenvoudiger te doen in de Maybe-monade.
Zo krijgen we zo'n implementatie.
{-# 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)
De where-blok is de kern van het algoritme. Ik zal proberen uit te leggen wat er van binnen gebeurt.
- inVertex is het deel van de dieptezoektocht waarin we de top voor het eerst bezoeken. Hier wijzen we een partijnummer toe aan de top en starten we onEdge voor alle buren. Dit is ook de plek waar we de oproepstack herstellen: als msum een waarde retourneerde, voegen we daar de top v aan toe.
- onEdge is the part where we visit an edge. It is called twice for each edge. Here we check if the vertex on the other side has been visited, and we visit it if not. If it has been visited, we check whether the edge is conflicting. If it is, we return the value — the top of the recursion stack, where all other vertices are then stacked upon return.
- processVertex checks for each vertex if it has been visited, and runs inVertex on it if not.
- dfs runs processVertex on all vertices.
gebruik maken van het transportprotocol niet in de weg staat.
The History of the Word INLINE
The term INLINE was not in the first implementation of the algorithm; it appeared later. When I was trying to find a better implementation, I discovered that in some graphs, the version without INLINE worked noticeably slower. Considering that semantically the functions should work the same, this surprised me greatly. Even more strangely, on another machine with a different version of GHC, there was no noticeable difference.
After spending a week reading the GHC Core output, I was able to fix the problem with a single line of explicit INLINE. At some point between GHC 8.4.4 and GHC 8.6.5, the optimizer stopped doing this automatically.
I did not expect to encounter such mess in Haskell programming. However, optimizers even today sometimes make mistakes, and giving them hints is our job. For example, here we know that the function should be inlined, as it is in the imperative version, and that is a reason to give the compiler a hint.
What happened next?
Next, I implemented the Hopcroft-Karp algorithm using different monads, and that’s how the program ended.
Thanks to Google Summer of Code, I gained practical experience in functional programming, which not only helped me secure an internship at Jane Street the following summer (I’m not sure how well-known this place is even among the knowledgeable audience of Habr, but it is one of the few places where you can engage in functional programming during the summer), but also introduced me to the amazing world of applying this paradigm in practice, which is significantly different from my experience in traditional languages.
Bron: habr.com
