Afgelopen zomer heb ik meegedaan - een programma voor studenten van Google. Elk jaar selecteren de organisatoren verschillende Open Source-projecten, onder meer van bekende organisaties als и . Google nodigt studenten van over de hele wereld uit om aan deze projecten te werken.
Als deelnemer aan Google Summer of Code 2019 heb ik een project gedaan binnen de bibliotheek met de organisatie , dat de Haskell-taal ontwikkelt - een van de beroemdste functionele programmeertalen. Alga is een bibliotheek die vertegenwoordigt weergave voor grafieken in Haskell. Het wordt bijvoorbeeld gebruikt in — een Github-bibliotheek die semantische bomen, oproep- en afhankelijkheidsgrafieken bouwt op basis van code en deze kan vergelijken. Mijn project was om een typeveilige representatie toe te voegen voor bipartiete grafieken en algoritmen voor die representatie.
In dit bericht zal ik het hebben over mijn implementatie van een algoritme voor het controleren van een grafiek op bipartiteit in Haskell. Ook al is het algoritme een van de meest basale, het kostte me verschillende iteraties om het prachtig in een functionele stijl te implementeren en het vergde behoorlijk wat werk. Als gevolg hiervan heb ik gekozen voor een implementatie met monadetransformatoren.
Over mij
Mijn naam is Vasily Alferov, ik ben een vierdejaars student aan de HSE in St. Petersburg. Eerder in de blog schreef ik и . Momenteel loop ik stage bij in Noorwegen, waar ik werk aan benaderingen van het probleem . Mijn interesses omvatten geparametriseerde algoritmen en functioneel programmeren.
Over de implementatie van het algoritme
Voorwoord
Studenten die aan het programma deelnemen, worden sterk aangemoedigd om te bloggen. Ze boden me een platform voor de blog . Dit artikel is een vertaling , door mij daar in juli geschreven in het Engels, met een kort voorwoord.
Pull Request met de betreffende code is te vinden .
U kunt lezen over de resultaten van mijn werk (in het Engels) .
Dit bericht is bedoeld om de lezer vertrouwd te maken met de basisconcepten van functioneel programmeren, hoewel ik zal proberen alle gebruikte termen te herinneren als de tijd daar is.
Grafieken controleren op bipartiteit
Een algoritme voor het controleren van een grafiek op bipartiteit wordt meestal gegeven in een cursus over algoritmen als een van de eenvoudigste grafiekalgoritmen. Zijn idee is eenvoudig: eerst plaatsen we op de een of andere manier hoekpunten in het linker- of rechterdeel, en wanneer een conflicterende rand wordt gevonden, beweren we dat de grafiek niet tweeledig is.
Iets meer detail: eerst plaatsen we een hoekpunt in het linkerdeel. Het is duidelijk dat alle buren van dit hoekpunt in de rechter lob moeten liggen. Verder moeten alle buren van de buren van dit hoekpunt in de linkerkwab liggen, enzovoort. We gaan door met het toewijzen van aandelen aan hoekpunten zolang er nog hoekpunten zijn in de verbonden component van het hoekpunt waarmee we zijn begonnen en waaraan we geen buren hebben toegewezen. Deze actie herhalen we vervolgens voor alle aangesloten componenten.
Als er een rand is tussen hoekpunten die in dezelfde partitie vallen, is het niet moeilijk om een vreemde cyclus in de grafiek te vinden, wat algemeen bekend (en overduidelijk) onmogelijk is in een bipartiete grafiek. Anders hebben we een correcte partitie, wat betekent dat de grafiek tweeledig is.
Meestal wordt dit algoritme geïmplementeerd met behulp van of . In imperatieve talen wordt meestal diepte-eerst zoeken gebruikt, omdat dit iets eenvoudiger is en geen extra datastructuren vereist. Ik heb ook voor diepte-eerst zoeken gekozen, omdat dit traditioneler is.
Zo kwamen we tot het volgende schema. We doorkruisen de hoekpunten van de grafiek met behulp van diepte-eerst zoeken en wijzen er aandelen aan toe, waarbij we het nummer van het aandeel veranderen terwijl we langs de rand bewegen. Als we proberen een aandeel toe te wijzen aan een hoekpunt waaraan al een aandeel is toegewezen, kunnen we gerust zeggen dat de grafiek niet tweeledig is. Op het moment dat alle hoekpunten een aandeel krijgen en we naar alle randen hebben gekeken, hebben we een goede partitie.
Zuiverheid van berekeningen
Bij Haskell gaan we ervan uit dat alle berekeningen dat zijn schoon. Als dit echter echt het geval zou zijn, zouden we niets op het scherm kunnen afdrukken. Helemaal niet, schoon berekeningen zijn zo lui dat er niet één is schoon redenen om iets te berekenen. Alle berekeningen die in het programma voorkomen, worden op de een of andere manier gedwongen "onrein" monade IO.
Monaden zijn een manier om berekeningen mee weer te geven Effecten in Haskell. Uitleggen hoe ze werken valt buiten het bestek van dit bericht. Een goede en duidelijke beschrijving is in het Engels te lezen .
Hier wil ik erop wijzen dat hoewel sommige monaden, zoals IO, worden geïmplementeerd via compilermagie, bijna alle andere in software worden geïmplementeerd en dat alle berekeningen daarin puur zijn.
Er zijn veel effecten en elk heeft zijn eigen monade. Dit is een zeer sterke en mooie theorie: alle monaden implementeren dezelfde interface. We zullen het hebben over de volgende drie monaden:
- Ofwel is ea een berekening die een waarde van type a retourneert, ofwel een uitzondering van type e genereert. Het gedrag van deze monade lijkt sterk op de afhandeling van uitzonderingen in imperatieve talen: fouten kunnen worden opgemerkt of doorgegeven. Het belangrijkste verschil is dat de monade volledig logisch is geïmplementeerd in de standaardbibliotheek in Haskell, terwijl imperatieve talen meestal besturingssysteemmechanismen gebruiken.
- State sa is een berekening die een waarde van type a retourneert en toegang heeft tot de veranderlijke status van type s.
- Misschien een. De Misschien-monade drukt een berekening uit die op elk moment kan worden onderbroken door Niets terug te geven. We zullen het echter hebben over de implementatie van de klasse MonadPlus voor het type Maybe, die het tegenovergestelde effect tot uitdrukking brengt: het is een berekening die op elk moment kan worden onderbroken door een specifieke waarde terug te geven.
Implementatie van het algoritme
We hebben twee gegevenstypen, Graph a en Bigraph ab, waarvan de eerste grafieken vertegenwoordigt met hoekpunten die zijn gelabeld met waarden van type a, en de tweede bipartiete grafieken vertegenwoordigt met hoekpunten aan de linkerkant die zijn gelabeld met waarden van type a en rechts -zijhoekpunten gelabeld met waarden van type b.
Dit zijn geen typen uit de Algabibliotheek. Alga heeft geen weergave voor ongerichte bipartiete grafieken. Voor de duidelijkheid heb ik de typen zo gemaakt.
We hebben ook helperfuncties nodig met de volgende handtekeningen:
-- Список соседей данной вершины.
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)Het is gemakkelijk in te zien dat als we tijdens de diepte-eerst-zoektocht een conflicterende rand vinden, de vreemde cyclus bovenop de recursiestapel ligt. Om het te herstellen, moeten we dus alles afsnijden, vanaf de recursiestapel tot aan de eerste keer dat het laatste hoekpunt voorkomt.
We implementeren diepte-eerst zoeken door voor elk hoekpunt een associatieve reeks deelnummers bij te houden. De recursiestapel wordt automatisch onderhouden door de implementatie van de Functor-klasse van de monade die we hebben gekozen: we hoeven alleen maar alle hoekpunten van het pad in het resultaat te plaatsen dat wordt geretourneerd door de recursieve functie.
Mijn eerste idee was om de 'Of'-monade te gebruiken, die precies de effecten lijkt te implementeren die we nodig hebben. De eerste implementatie die ik schreef kwam heel dicht in de buurt van deze optie. Sterker nog, ik had op een gegeven moment vijf verschillende implementaties en uiteindelijk koos ik voor een andere.
Ten eerste moeten we een associatieve reeks van share-ID's onderhouden - dit heeft iets met staat te maken. Ten tweede moeten we kunnen stoppen wanneer er een conflict wordt gedetecteerd. Dit kan Monad voor Beide zijn, of MonadPlus voor Misschien. Het belangrijkste verschil is dat Ofwel een waarde kan retourneren als de berekening niet is gestopt, en dat Misschien in dit geval alleen informatie hierover retourneert. Omdat we geen aparte waarde nodig hebben voor succes (deze is al opgeslagen in State), kiezen we Misschien. En op het moment dat we de effecten van twee monaden moeten combineren, komen ze naar voren , die deze effecten precies combineren.
Waarom heb ik voor zo'n complex type gekozen? Twee redenen. Ten eerste blijkt de implementatie sterk op imperatief te lijken. Ten tweede moeten we de retourwaarde manipuleren in geval van een conflict wanneer we terugkeren van recursie om de vreemde lus te herstellen, wat veel gemakkelijker is om te doen in de Maybe-monade.
Zo krijgen we deze 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 <- 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)
Het Where-blok is de kern van het algoritme. Ik zal proberen uit te leggen wat er binnenin gebeurt.
- inVertex is het deel van diepte-eerst zoeken waarbij we het hoekpunt voor de eerste keer bezoeken. Hier wijzen we een deelnummer toe aan het hoekpunt en voeren we onEdge uit op alle buren. Dit is ook waar we de call-stack herstellen: als msum een waarde retourneert, duwen we daar vertex v.
- onEdge is het gedeelte waar we de rand bezoeken. Het wordt voor elke rand twee keer aangeroepen. Hier controleren we of het hoekpunt aan de andere kant is bezocht, en bezoeken we het indien niet. Bij bezoek controleren wij of de rand conflicteert. Als dat zo is, retourneren we de waarde: de top van de recursiestapel, waar alle andere hoekpunten bij terugkeer worden geplaatst.
- processVertex controleert voor elk hoekpunt of het is bezocht en voert inVertex daarop uit als dat niet het geval is.
- dfs voert processVertex uit op alle hoekpunten.
Dat is alles.
Geschiedenis van het woord INLINE
Het woord INLINE zat niet in de eerste implementatie van het algoritme; het verscheen later. Toen ik probeerde een betere implementatie te vinden, ontdekte ik dat de niet-INLINE-versie in sommige grafieken merkbaar langzamer was. Gezien het feit dat de functies semantisch hetzelfde zouden moeten werken, verbaasde dit mij enorm. Nog vreemder: op een andere machine met een andere versie van GHC was er geen merkbaar verschil.
Nadat ik een week lang de GHC Core-uitvoer had gelezen, kon ik het probleem oplossen met één regel expliciet INLINE. Op een gegeven moment tussen GHC 8.4.4 en GHC 8.6.5 stopte de optimizer hier vanzelf mee.
Ik had niet verwacht dat ik zulke vuiligheid zou tegenkomen in de Haskell-programmering. Maar zelfs vandaag de dag maken optimizers soms fouten, en het is onze taak om ze hints te geven. Hier weten we bijvoorbeeld dat de functie inline moet zijn omdat deze in de imperatieve versie is inline, en dit is een reden om de compiler een hint te geven.
Wat gebeurde er daarna?
Vervolgens implementeerde ik het Hopcroft-Karp-algoritme met andere monaden, en dat was het einde van het programma.
Dankzij Google Summer of Code heb ik praktische ervaring opgedaan met functioneel programmeren, waardoor ik de volgende zomer niet alleen stage kon lopen bij Jane Street (ik weet niet zeker hoe bekend deze plek zelfs is onder het deskundige publiek van Habr, maar het is er ook een van de weinige waar je in de zomer kunt deelnemen aan functioneel programmeren), maar liet me ook kennismaken met de wondere wereld van het toepassen van dit paradigma in de praktijk, aanzienlijk anders dan mijn ervaring in traditionele talen.
Bron: www.habr.com