Verlede somer het ek deelgeneem aan - 'n program vir studente van Google. Elke jaar kies die organiseerders verskeie Oopbronprojekte, insluitend van sulke bekende organisasies soos и . Google nooi studente van regoor die wêreld om aan hierdie projekte te werk.
As 'n deelnemer aan Google Summer of Code 2019 het ek 'n projek binne die biblioteek gedoen met die organisasie , wat besig is om die Haskell-taal te ontwikkel - een van die bekendste funksionele programmeertale. Alga is 'n biblioteek wat verteenwoordig voorstelling vir grafieke in Haskell. Dit word byvoorbeeld gebruik in - 'n Github-biblioteek wat semantiese bome, oproep- en afhanklikheidsgrafieke bou op grond van kode en dit kan vergelyk. My projek was om 'n tipe-veilige voorstelling vir tweeledige grafieke en algoritmes vir daardie voorstelling by te voeg.
In hierdie pos sal ek praat oor my implementering van 'n algoritme om 'n grafiek vir tweeledigheid in Haskell na te gaan. Selfs al is die algoritme een van die mees basiese, het die implementering daarvan pragtig in 'n funksionele styl my verskeie iterasies geneem en het nogal baie werk geverg. Gevolglik het ek op 'n implementering met monadetransformators besluit.
About Me
My naam is Vasily Alferov, ek is 'n vierdejaarstudent by St. Petersburg HSE. Vroeër in die blog het ek geskryf и . Op die oomblik is ek op 'n internskap by in Noorweë, waar ek besig is met benaderings tot die probleem . My belangstellings sluit in geparameteriseerde algoritmes en funksionele programmering.
Oor die implementering van die algoritme
voorwoord
Studente wat aan die program deelneem, word sterk aangemoedig om te blog. Hulle het my 'n platform vir die blog verskaf . Hierdie artikel is 'n vertaling , geskryf deur my daar in Julie in Engels, met 'n kort voorwoord.
Trek-versoek met die betrokke kode kan gevind word .
Jy kan lees oor die resultate van my werk (in Engels) .
Hierdie pos is bedoel om die leser vertroud te maak met die basiese konsepte in funksionele programmering, alhoewel ek sal probeer om al die terme wat gebruik word te onthou wanneer die tyd aanbreek.
Kontroleer grafieke vir tweeledigheid
'n Algoritme om 'n grafiek vir tweeledigheid na te gaan, word gewoonlik in 'n kursus oor algoritmes gegee as een van die eenvoudigste grafiekalgoritmes. Sy idee is eenvoudig: eers plaas ons op een of ander manier hoekpunte in die linker- of regterdeel, en wanneer 'n botsende rand gevind word, beweer ons dat die grafiek nie tweeledig is nie.
'n Bietjie meer detail: eers sit ons 'n hoekpunt in die linker deel. Dit is duidelik dat al die bure van hierdie hoekpunt in die regterlob moet lê. Verder moet al die bure van die bure van hierdie hoekpunt in die linkerlob lê, ensovoorts. Ons gaan voort om aandele aan hoekpunte toe te ken solank daar nog hoekpunte is in die gekoppelde komponent van die hoekpunt waarmee ons begin het waaraan ons nie bure toegewys het nie. Ons herhaal dan hierdie aksie vir alle gekoppelde komponente.
As daar 'n rand is tussen hoekpunte wat in dieselfde partisie val, is dit nie moeilik om 'n vreemde siklus in die grafiek te vind nie, wat algemeen bekend is (en heel duidelik) onmoontlik is in 'n tweeledige grafiek. Andersins het ons 'n korrekte partisie, wat beteken dat die grafiek tweeledig is.
Tipies word hierdie algoritme geïmplementeer met behulp van of . In imperatiewe tale word diepte-eerste soektog gewoonlik gebruik aangesien dit effens eenvoudiger is en nie bykomende datastrukture benodig nie. Ek het ook diepte-eerste soektog gekies aangesien dit meer tradisioneel is.
So het ons by die volgende skema gekom. Ons deurkruis die hoekpunte van die grafiek deur diepte-eerste soektog te gebruik en ken aandele aan hulle toe, en verander die nommer van die deel soos ons langs die rand beweeg. As ons probeer om 'n deel toe te ken aan 'n hoekpunt wat reeds 'n deel toegeken het, kan ons met veiligheid sê dat die grafiek nie tweeledig is nie. Die oomblik dat alle hoekpunte 'n aandeel toegeken word en ons na al die rande gekyk het, het ons 'n goeie partisie.
Suiwerheid van berekeninge
In Haskell neem ons aan dat alle berekeninge is skoon. As dit egter werklik die geval was, sou ons geen manier gehad het om iets op die skerm te druk nie. Enigsins, skoon berekeninge is so lui dat daar nie een is nie skoon redes om iets te bereken. Alle berekeninge wat in die program voorkom, word op een of ander manier ingedwing "onrein" monade IO.
Monades is 'n manier om berekeninge mee voor te stel effekte in Haskell. Om te verduidelik hoe hulle werk, is buite die bestek van hierdie pos. 'n Goeie en duidelike beskrywing kan in Engels gelees word .
Hier wil ek daarop wys dat terwyl sommige monaden, soos IO, deur samestellermagie geïmplementeer word, is byna al die ander in sagteware geïmplementeer en alle berekeninge daarin is suiwer.
Daar is baie effekte en elkeen het sy eie monade. Dit is 'n baie sterk en pragtige teorie: alle monaden implementeer dieselfde koppelvlak. Ons sal oor die volgende drie monaden praat:
- Óf ea is 'n berekening wat 'n waarde van tipe a gee of 'n uitsondering van tipe e gooi. Die gedrag van hierdie monade is baie soortgelyk aan uitsonderingshantering in imperatiewe tale: foute kan vasgevang of deurgegee word. Die belangrikste verskil is dat die monade heeltemal logies in die standaardbiblioteek in Haskell geïmplementeer word, terwyl imperatiewe tale gewoonlik bedryfstelselmeganismes gebruik.
- State sa is 'n berekening wat 'n waarde van tipe a terugstuur en toegang het tot veranderlike toestand van tipe s.
- Miskien a. Die Miskien-monade druk 'n berekening uit wat enige tyd onderbreek kan word deur Niks terug te gee. Ons sal egter praat oor die implementering van die MonadPlus-klas vir die Miskien-tipe, wat die teenoorgestelde effek uitdruk: dit is 'n berekening wat te eniger tyd onderbreek kan word deur 'n spesifieke waarde terug te gee.
Implementering van die algoritme
Ons het twee datatipes, Grafiek a en Bigraph ab, waarvan die eerste grafieke verteenwoordig met hoekpunte gemerk met waardes van tipe a, en die tweede tweeledige grafieke verteenwoordig met hoekpunte aan die linkerkant gemerk met waardes van tipe a en regs -kantpunte gemerk met waardes van tipe b.
Dit is nie tipes uit die Alga-biblioteek nie. Alga het nie 'n voorstelling vir ongerigte tweeledige grafieke nie. Ek het die tipes soos hierdie gemaak vir duidelikheid.
Ons sal ook helperfunksies met die volgende handtekeninge benodig:
-- Список соседей данной вершины.
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)Dit is maklik om te sien dat as ons tydens die diepte-eerste soektog 'n botsende rand gevind het, die vreemde siklus bo-op die rekursiestapel lê. Dus, om dit te herstel, moet ons alles van die rekursiestapel tot by die eerste voorkoms van die laaste hoekpunt afsny.
Ons implementeer diepte-eerste soektog deur 'n assosiatiewe reeks deelnommers vir elke hoekpunt te handhaaf. Die rekursiestapel sal outomaties in stand gehou word deur die implementering van die Functor-klas van die monade wat ons gekies het: ons sal net al die hoekpunte van die pad moet plaas in die resultaat wat van die rekursiewe funksie teruggestuur word.
My eerste idee was om die Een-monade te gebruik, wat blykbaar presies die effekte implementeer wat ons nodig het. Die eerste implementering wat ek geskryf het, was baie naby aan hierdie opsie. Trouens, ek het op 'n stadium vyf verskillende implementerings gehad en het uiteindelik op 'n ander een besluit.
Eerstens moet ons 'n assosiatiewe reeks aandeelidentifiseerders handhaaf - dit is iets oor staat. Tweedens moet ons kan stop wanneer 'n konflik bespeur word. Dit kan óf Monad vir óf, óf MonadPlus vir Miskien wees. Die belangrikste verskil is dat Beide 'n waarde kan terugstuur as die berekening nie gestop is nie, en Miskien gee in hierdie geval slegs inligting hieroor. Aangesien ons nie 'n aparte waarde vir sukses nodig het nie (dit is reeds in Staat gestoor), kies ons Miskien. En op die oomblik wanneer ons die effekte van twee monaden moet kombineer, kom hulle uit , wat hierdie effekte presies kombineer.
Hoekom het ek so 'n komplekse tipe gekies? Twee redes. Eerstens blyk die implementering baie soortgelyk aan noodsaaklik te wees. Tweedens moet ons die terugkeerwaarde manipuleer in geval van konflik wanneer ons terugkom van rekursie om die vreemde lus te herstel, wat baie makliker is om te doen in die Miskien-monade.
So kry ons hierdie 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)
Die waar-blok is die kern van die algoritme. Ek sal probeer verduidelik wat daarbinne gebeur.
- inVertex is die deel van diepte-eerste soektog waar ons die hoekpunt vir die eerste keer besoek. Hier ken ons 'n deelnommer aan die hoekpunt toe en hardloop onEdge op alle bure. Dit is ook waar ons die oproepstapel herstel: as msum 'n waarde teruggestuur het, druk ons hoekpunt v daarheen.
- onEdge is die deel waar ons die rand besoek. Dit word twee keer vir elke rand genoem. Hier kyk ons of die hoekpunt aan die ander kant besoek is, en besoek dit indien nie. As dit besoek word, kyk ons of die rand teenstrydig is. As dit is, gee ons die waarde terug - die heel bokant van die rekursiestapel, waar alle ander hoekpunte dan by terugkeer geplaas sal word.
- processVertex kontroleer vir elke hoekpunt of dit besoek is en loop inVertex daarop indien nie.
- dfs loop processVertex op alle hoekpunte.
Dit is al.
Geskiedenis van die woord INLINE
Die woord INLINE was nie in die eerste implementering van die algoritme nie; dit het later verskyn. Toe ek probeer om 'n beter implementering te vind, het ek gevind dat die nie-INLINE weergawe merkbaar stadiger op sommige grafieke was. As in ag geneem word dat die funksies semanties dieselfde moet werk, het dit my baie verras. Nog vreemder, op 'n ander masjien met 'n ander weergawe van GHC was daar geen merkbare verskil nie.
Nadat ek 'n week spandeer het om die GHC Core-uitset te lees, kon ek die probleem oplos met een lyn van eksplisiete INLINE. Op 'n sekere punt tussen GHC 8.4.4 en GHC 8.6.5 het die optimizer opgehou om dit op sy eie te doen.
Ek het nie verwag om sulke vuiligheid in Haskell-programmering teë te kom nie. Selfs vandag maak optimeerders egter soms foute, en dit is ons taak om vir hulle wenke te gee. Byvoorbeeld, hier weet ons dat die funksie ingelyn moet word omdat dit in die imperatiewe weergawe ingelyn is, en dit is 'n rede om die samesteller 'n wenk te gee.
Wat het volgende gebeur?
Toe het ek die Hopcroft-Karp-algoritme met ander monaden geïmplementeer, en dit was die einde van die program.
Danksy Google Summer of Code het ek praktiese ervaring in funksionele programmering opgedoen, wat my nie net gehelp het om die volgende somer 'n internskap by Janestraat te kry nie (ek is nie seker hoe bekend hierdie plek selfs onder Habr se kundige gehoor is nie, maar dit is een van die min waar jy kan somer om betrokke te raak by funksionele programmering), maar het my ook bekendgestel aan die wonderlike wêreld van die toepassing van hierdie paradigma in die praktyk, aansienlik anders as my ervaring in tradisionele tale.
Bron: will.com