Förra sommaren var jag med på - ett program för studenter från Google. Varje år väljer arrangörerna ut flera Open Source-projekt, bland annat från så välkända organisationer som и . Google bjuder in studenter från hela världen att arbeta med dessa projekt.
Som deltagare i Google Summer of Code 2019 gjorde jag ett projekt inom biblioteket med organisationen , som utvecklar Haskell-språket - ett av de mest kända funktionella programmeringsspråken. Alga är ett bibliotek som representerar representation för grafer i Haskell. Den används till exempel i — ett Github-bibliotek som bygger semantiska träd, samtals- och beroendegrafer baserat på kod och kan jämföra dem. Mitt projekt var att lägga till en typsäker representation för tvådelade grafer och algoritmer för den representationen.
I det här inlägget kommer jag att prata om min implementering av en algoritm för att kontrollera en graf för bipartiteness i Haskell. Även om algoritmen är en av de mest grundläggande, tog det mig flera iterationer att implementera den på ett vackert sätt i en funktionell stil och krävde ganska mycket arbete. Som ett resultat slog jag mig på en implementering med monadtransformatorer.
Om mig
Jag heter Vasily Alferov, jag är fjärdeårsstudent vid St. Petersburg HSE. Tidigare i bloggen skrev jag и . Just nu är jag på praktik på i Norge, där jag arbetar med förhållningssätt till problemet . Mina intressen inkluderar parametriserade algoritmer och funktionell programmering.
Om implementeringen av algoritmen
Förord
Studenter som deltar i programmet uppmuntras starkt att blogga. De gav mig en plattform för bloggen . Denna artikel är en översättning , skriven av mig där i juli på engelska, med ett kort förord.
Pull Request med koden i fråga kan hittas .
Du kan läsa om resultatet av mitt arbete (på engelska) .
Det här inlägget är tänkt att göra läsaren bekant med de grundläggande begreppen inom funktionell programmering, även om jag ska försöka återkalla alla termer som används när det är dags.
Kontrollera grafer för bipartiteness
En algoritm för att kontrollera en graf för tvådeladhet ges vanligtvis i en kurs om algoritmer som en av de enklaste grafalgoritmerna. Hans idé är okomplicerad: först sätter vi på något sätt hörn i vänster eller höger del, och när en motstridig kant hittas, hävdar vi att grafen inte är tvådelad.
Lite mer detalj: först lägger vi lite vertex i den vänstra delen. Uppenbarligen måste alla grannar till denna vertex ligga i höger lob. Vidare måste alla grannar till grannarna till denna vertex ligga i den vänstra loben, och så vidare. Vi fortsätter att tilldela andelar till vertex så länge det fortfarande finns hörn i den anslutna komponenten av vertexen vi började med som vi inte har tilldelat grannar. Vi upprepar sedan denna åtgärd för alla anslutna komponenter.
Om det finns en kant mellan hörn som faller in i samma partition är det inte svårt att hitta en udda cykel i grafen, vilket är allmänt känt (och helt uppenbart) omöjligt i en tvådelad graf. Annars har vi en korrekt partition, vilket betyder att grafen är tvådelad.
Vanligtvis implementeras denna algoritm med hjälp av eller . I imperativa språk används vanligtvis djup-först-sökning eftersom det är något enklare och inte kräver ytterligare datastrukturer. Jag valde också djup-först-sökning eftersom det är mer traditionellt.
Därmed kom vi till följande schema. Vi korsar grafens hörn med hjälp av djup-först-sökning och tilldelar andelar till dem, och ändrar numret på andelen när vi rör oss längs kanten. Om vi försöker tilldela en del till en vertex som redan har en del tilldelad, kan vi lugnt säga att grafen inte är tvådelad. I det ögonblick som alla hörn tilldelas en del och vi har tittat på alla kanter har vi en bra partition.
Renhet av beräkningar
I Haskell antar vi att alla beräkningar är rena. Men om detta verkligen var fallet skulle vi inte ha något sätt att skriva ut något på skärmen. Alls, ren beräkningar är så lata att det inte finns någon rena skäl att beräkna något. Alla beräkningar som sker i programmet tvingas på något sätt in "oren" monad IO.
Monader är ett sätt att representera beräkningar med effekter i Haskell. Att förklara hur de fungerar ligger utanför ramen för detta inlägg. En bra och tydlig beskrivning kan läsas på engelska .
Här vill jag påpeka att medan vissa monader, som IO, implementeras genom kompilatormagi, är nästan alla andra implementerade i mjukvara och alla beräkningar i dem är rena.
Det finns många effekter och var och en har sin egen monad. Detta är en mycket stark och vacker teori: alla monader implementerar samma gränssnitt. Vi kommer att prata om följande tre monader:
- Antingen är ea en beräkning som returnerar ett värde av typ a eller ger ett undantag av typ e. Beteendet hos denna monad är mycket likt undantagshantering i imperativa språk: fel kan fångas upp eller föras vidare. Den största skillnaden är att monaden är helt logiskt implementerad i standardbiblioteket i Haskell, medan imperativa språk vanligtvis använder operativsystemmekanismer.
- Tillstånd sa är en beräkning som returnerar ett värde av typ a och har tillgång till föränderligt tillstånd av typ s.
- Kanske en. Kanske-monaden uttrycker en beräkning som kan avbrytas när som helst genom att returnera Ingenting. Men vi kommer att prata om implementeringen av MonadPlus-klassen för typen Maybe, som uttrycker motsatt effekt: det är en beräkning som kan avbrytas när som helst genom att returnera ett specifikt värde.
Implementering av algoritmen
Vi har två datatyper, graf a och bigraf ab, av vilka den första representerar grafer med hörn märkta med värden av typ a, och den andra representerar tvådelade grafer med hörn på vänster sida märkta med värden av typ a och höger -sidohörn märkta med värden av typ b.
Det här är inte typer från Alga-biblioteket. Alga har ingen representation för oriktade tvådelade grafer. Jag gjorde sådana här typer för tydlighetens skull.
Vi kommer också att behöva hjälpfunktioner med följande 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 är lätt att se att om vi under sökningen med djupet-först hittade en motstridig kant, så ligger den udda cykeln ovanpå rekursionsstacken. För att återställa det måste vi alltså skära av allt från rekursionsstacken upp till den första förekomsten av den sista vertexen.
Vi implementerar djup-först-sökning genom att upprätthålla en associativ uppsättning andelsnummer för varje vertex. Rekursionsstacken kommer att bibehållas automatiskt genom implementeringen av Functor-klassen för den monad vi har valt: vi behöver bara lägga alla hörn från vägen till resultatet som returneras från den rekursiva funktionen.
Min första idé var att använda antingen monaden, som verkar implementera exakt de effekter som vi behöver. Den första implementeringen jag skrev var mycket nära detta alternativ. Faktum är att jag hade fem olika implementeringar vid ett tillfälle och så småningom bestämde jag mig för en annan.
Först måste vi upprätthålla en associativ uppsättning av andelsidentifierare - det här handlar om staten. För det andra måste vi kunna stoppa när en konflikt upptäcks. Detta kan vara antingen Monad för antingen eller MonadPlus för Kanske. Den största skillnaden är att antingen kan returnera ett värde om beräkningen inte har stoppats, och Maybe returnerar endast information om detta i detta fall. Eftersom vi inte behöver ett separat värde för framgång (det är redan lagrat i State) väljer vi Kanske. Och i det ögonblick då vi behöver kombinera effekterna av två monader kommer de ut , som exakt kombinerar dessa effekter.
Varför valde jag en så komplex typ? Två skäl. För det första visar sig implementeringen vara mycket lik imperativ. För det andra måste vi manipulera returvärdet i händelse av konflikt när vi går tillbaka från rekursion för att återställa den udda loopen, vilket är mycket lättare att göra i Maybe-monaden.
Därmed får vi denna 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-blocket är kärnan i algoritmen. Jag ska försöka förklara vad som händer inuti den.
- inVertex är den del av djup-först-sökning där vi besöker vertexet för första gången. Här tilldelar vi ett andelsnummer till vertexet och kör onEdge på alla grannar. Det är också här vi återställer anropsstacken: om msum returnerade ett värde, trycker vi dit vertex v.
- onEdge är den del där vi besöker kanten. Det kallas två gånger för varje kant. Här kontrollerar vi om vertexet på andra sidan har besökts, och besöker det om inte. Vid besök kontrollerar vi om kanten är motstridig. Om det är det, returnerar vi värdet - den allra översta delen av rekursionsstacken, där alla andra hörn sedan kommer att placeras vid retur.
- processVertex kontrollerar för varje vertex om den har besökts och kör inVertex på den om inte.
- dfs kör processVertex på alla hörn.
Det är allt.
Historia av ordet INLINE
Ordet INLINE fanns inte i den första implementeringen av algoritmen, det dök upp senare. När jag försökte hitta en bättre implementering fann jag att den icke-INLINE-versionen var märkbart långsammare på vissa grafer. Med tanke på att semantiskt sett borde funktionerna fungera likadant förvånade detta mig mycket. Ännu konstigt, på en annan maskin med en annan version av GHC var det ingen märkbar skillnad.
Efter att ha tillbringat en vecka med att läsa GHC Core-utgången kunde jag åtgärda problemet med en rad explicit INLINE. Vid någon tidpunkt mellan GHC 8.4.4 och GHC 8.6.5 slutade optimeraren att göra detta på egen hand.
Jag förväntade mig inte att stöta på sådan smuts i Haskell-programmering. Men även idag gör optimerare ibland misstag, och det är vår uppgift att ge dem tips. Till exempel, här vet vi att funktionen bör infogas eftersom den är inlagd i imperativversionen, och detta är en anledning att ge kompilatorn en hint.
Vad hände sedan?
Sedan implementerade jag Hopcroft-Karp-algoritmen med andra monader, och det var slutet på programmet.
Tack vare Google Summer of Code fick jag praktisk erfarenhet av funktionell programmering, vilket inte bara hjälpte mig att få en praktikplats på Jane Street följande sommar (jag är inte säker på hur välkänd den här platsen är ens bland Habrs kunniga publik, men det är en av de få där du kan sommar för att engagera dig i funktionell programmering), men också introducerade mig till den underbara världen att tillämpa detta paradigm i praktiken, väsentligt annorlunda än min erfarenhet av traditionella språk.
Källa: will.com