Ferline simmer haw ik meidien oan - in programma foar studinten fan Google. Alle jierren, de organisatoaren selektearje ferskate Open Source projekten, ynklusyf fan sokke bekende organisaasjes as и . Google noeget studinten fan oer de hiele wrâld út om oan dizze projekten te wurkjen.
As dielnimmer oan Google Summer of Code 2019 haw ik in projekt dien binnen de bibleteek mei de organisaasje , dy't de Haskell-taal ûntwikkelet - ien fan 'e meast ferneamde funksjonele programmeartalen. Alga is in bibleteek dy't fertsjintwurdiget foarstelling foar grafiken yn Haskell. It wurdt brûkt, bygelyks, yn - in Github-bibleteek dy't semantyske beammen, oprop- en ôfhinklikheidsgrafiken bouwt basearre op koade en kin se fergelykje. Myn projekt wie om in typefeilige foarstelling ta te foegjen foar bipartitegrafiken en algoritmen foar dy foarstelling.
Yn dizze post sil ik prate oer myn ymplemintaasje fan in algoritme foar it kontrolearjen fan in grafyk foar bipartiteness yn Haskell. Ek al is it algoritme ien fan 'e meast basale, it ymplementearjen fan it prachtich yn in funksjonele styl hat my ferskate iteraasjes koste en in protte wurk nedich. As gefolch haw ik my fêststeld op in ymplemintaasje mei monadetransformatoren.
Oer mysels
Myn namme is Vasily Alferov, ik bin in fjirde-jier studint oan Sint Petersburg HSE. Earder yn it blog skreau ik и . Op it stuit bin ik op staazje by yn Noarwegen, dêr't ik wurkje oan oanpak fan it probleem . Myn ynteresses omfetsje parameterisearre algoritmen en funksjonele programmearring.
Oer de ymplemintaasje fan it algoritme
Foarwurd
Learlingen dy't meidogge oan it programma wurde sterk oanmoedige om te bloggen. Se joegen my in platfoarm foar it blog . Dit artikel is in oersetting , skreaun troch my dêr yn july yn it Ingelsk, mei in koart foarwurd.
Pull Request mei de koade yn kwestje kin fûn wurde .
Jo kinne lêze oer de resultaten fan myn wurk (yn it Ingelsk) .
Dizze post is bedoeld om de lêzer fertroud te meitsjen mei de basisbegripen yn funksjonele programmearring, hoewol ik sil besykje alle termen dy't brûkt wurde werom te heljen as de tiid komt.
Kontrolearje grafiken foar bipartiteness
In algoritme foar it kontrolearjen fan in grafyk op bipartiteness wurdt meastentiids jûn yn in kursus oer algoritmen as ien fan 'e ienfâldichste grafyske algoritmen. Syn idee is rjochtfeardich: earst sette wy op ien of oare manier hoekpunten yn 'e lofter of rjochter diel, en as in tsjinstridige râne wurdt fûn, beweare wy dat de grafyk net bipartite is.
In bytsje mear detail: earst sette wy wat hoekpunt yn it linker diel. Fansels moatte alle buorlju fan dit toppunt yn 'e rjochter lobe lizze. Fierder moatte alle buorlju fan 'e buorlju fan dit toppunt lizze yn 'e lofterlobe, ensfh. Wy trochgean mei it tawizen fan oandielen oan hoekpunten sa lang as der noch hoekpunten binne yn 'e ferbûne komponint fan' e top wêrmei wy begon binne dat wy buorlju net hawwe tawiisd. Wy werhelje dizze aksje dan foar alle ferbûne komponinten.
As der in râne is tusken hoekpunten dy't yn deselde partition falle, is it net dreech om in ûneven syklus te finen yn 'e grafyk, dy't rûnom bekend (en frij fansels) ûnmooglik is yn in twapartijige grafyk. Oars hawwe wy in juste dieling, wat betsjut dat de grafyk twadiel is.
Typysk wurdt dit algoritme ymplementearre mei help fan of . Yn ymperatyf talen wurdt djipte-earst sykjen meastentiids brûkt, om't it wat ienfâldiger is en gjin ekstra gegevensstruktueren fereasket. Ik keas ek foar djipte-earste sykjen, om't it tradisjoneeler is.
Sa kamen wy ta it folgjende skema. Wy geane troch de hoekpunten fan 'e grafyk mei help fan djipte-earste sykjen en jouwe oandielen oan har, feroarje it oantal fan' e oandiel as wy lâns de râne bewege. As wy besykje te tawizen fan in oandiel oan in toppunt dat al hat in oandiel tawiisd, kinne wy feilich sizze dat de grafyk is net bipartite. It momint dat alle hoekpunten wurde tawiisd in oandiel en wy hawwe sjoen op alle rânen, wy hawwe in goede partition.
Reinheid fan berekkeningen
Yn Haskell geane wy der fan út dat alle berekkeningen binne skjin. As dit lykwols wier it gefal wie, soene wy gjin manier hawwe om neat op it skerm te printsjen. Heulendal, skjin berekkeningen binne sa lui dat der net ien is skjin redenen om wat te berekkenjen. Alle berekkeningen dy't foarkomme yn it programma wurde op ien of oare manier twongen yn "ûnrein" moade IO.
Monads binne in manier om berekkeningen mei te fertsjintwurdigjen effekten te Haskell. It útlizzen fan hoe't se wurkje is bûten it berik fan dizze post. In goede en dúdlike beskriuwing kin lêzen wurde yn it Ingelsk .
Hjir wol ik oanjaan dat wylst guon monaden, lykas IO, wurde ymplementearre troch kompilatormagy, hast alle oaren wurde ymplementearre yn software en alle berekkeningen yn har binne suver.
D'r binne in protte effekten en elk hat syn eigen monade. Dit is in heul sterke en prachtige teory: alle monaden implementearje deselde ynterface. Wy sille prate oer de folgjende trije monaden:
- Of ea is in berekkening dy't in wearde fan type a jout of in útsûndering fan type e smyt. It gedrach fan dizze monade is tige ferlykber mei útsûnderingshanneling yn ymperatyf talen: flaters kinne wurde fongen of trochjûn. It wichtichste ferskil is dat de monade folslein logysk wurdt ymplementearre yn 'e standertbibleteek yn Haskell, wylst ymperatyf talen meastentiids bestjoeringssysteemmeganismen brûke.
- State sa is in berekkening dy't jout in wearde fan type a en hat tagong ta mutable steat fan type s.
- Miskien a. De Miskien-monade drukt in berekkening út dy't op elk momint kin wurde ûnderbrutsen troch Neat werom te jaan. Wy sille lykwols prate oer de ymplemintaasje fan 'e MonadPlus-klasse foar it Maybe-type, dy't it tsjinoerstelde effekt útdrukt: it is in berekkening dy't op elk momint kin wurde ûnderbrutsen troch in spesifike wearde werom te jaan.
Implementaasje fan it algoritme
Wy hawwe twa gegevenstypen, Graph a en Bigraph ab, wêrfan de earste grafiken fertsjintwurdiget mei hoekpunten markearre mei wearden fan type a, en de twadde fertsjintwurdiget bipartite grafiken mei hoekpunten oan 'e linkerkant markearre mei wearden fan type a en rjochts -side hoekpunten markearre mei wearden fan type b.
Dit binne gjin typen út de Alga-bibleteek. Alga hat gjin foarstelling foar ûnrjochte bipartitegrafiken. Ik makke de soarten lykas dit foar dúdlikens.
Wy sille ek helpfunksjes nedich hawwe mei de folgjende hantekeningen:
-- Список соседей данной вершины.
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)It is maklik om te sjen dat as wy yn 'e djipte-earste sykjen in tsjinstridige râne fûnen, de ûneven syklus boppe op' e rekursjestapel leit. Dus, om it te restaurearjen, moatte wy alles ôfsnije fan 'e rekursjestapel oant it earste optreden fan' e lêste hoekpunt.
Wy ymplementearje djipte-earste sykjen troch in assosjatyf array fan oandielnûmers te behâlden foar elke hoekpunt. De rekursjestapel sil automatysk bewarre wurde troch de ymplemintaasje fan 'e Functor-klasse fan' e monade dy't wy hawwe keazen: wy hoege allinich alle hoekpunten fan it paad yn it resultaat werom te setten fan 'e rekursive funksje.
Myn earste idee wie om de ien of oare monade te brûken, dy't krekt de effekten liket te ymplementearjen dy't wy nedich binne. De earste ymplemintaasje dy't ik skreau wie heul tichtby dizze opsje. Yn feite, ik hie fiif ferskillende ymplemintaasjes op ien punt en úteinlik fêstige op in oare.
Earst moatte wy in assosjatyf array fan oandielidentifikatoren behâlde - dit is wat oer steat. Twads moatte wy kinne stopje as in konflikt ûntdutsen wurdt. Dit kin of Monad foar ien wêze, of MonadPlus foar miskien. It wichtichste ferskil is dat Elk kin werom in wearde as de berekkening is net stoppe, en Miskien jout allinnich ynformaasje oer dit yn dit gefal. Sûnt wy net nedich in aparte wearde foar súkses (it is al opslein yn State), wy kieze miskien. En op it momint dat wy de effekten fan twa monaden kombinearje moatte, komme se út , dy't dizze effekten krekt kombinearje.
Wêrom haw ik sa'n komplekse type keazen? Twa redenen. As earste blykt de ymplemintaasje heul gelyk te wêzen oan ymperatyf. Twadder moatte wy de weromwearde manipulearje yn gefal fan konflikt by it weromkommen fan rekursje om de ûneven lus te herstellen, wat folle makliker te dwaan is yn 'e Miskien-monade.
Sa krije wy dizze ymplemintaasje.
{-# 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)
It wêr-blok is de kearn fan it algoritme. Ik sil besykje út te lizzen wat der binnen bart.
- inVertex is it diel fan 'e djipte-earste sykjen wêr't wy it toppunt foar it earst besykje. Hjir wy tawize in oandiel getal oan it toppunt en rinne onEdge op alle buorlju. Dit is ek wêr't wy werstelle de oprop stack: as msum werom in wearde, wy triuwe vertex v dêr.
- onEdge is it diel dêr't wy besykje de râne. It wurdt twa kear neamd foar elke râne. Hjir kontrolearje wy oft it toppunt oan 'e oare kant is besocht, en besykje it as net. As besocht, wy kontrolearje oft de râne is tsjinstridich. As it is, jouwe wy de wearde werom - de heule top fan 'e rekursjestapel, wêr't alle oare hoekpunten dan wurde pleatst by weromkomst.
- processVertex kontrolearret foar elke vertex oft it is besocht en rint inVertex derop as net.
- dfs rint processVertex op alle hoekpunten.
Da's alles.
Skiednis fan it wurd INLINE
It wurd INLINE wie net yn 'e earste ymplemintaasje fan it algoritme; it ferskynde letter. Doe't ik besocht te finen in bettere ymplemintaasje, Ik fûn dat de net-INLINE ferzje wie merkber stadiger op guon grafiken. Yn betinken nommen dat semantysk de funksjes itselde moatte wurkje, fernuvere dit my tige. Noch frjemder, op in oare masine mei in oare ferzje fan GHC wie gjin merkber ferskil.
Nei't ik in wike de GHC Core-útfier lêzen hie, koe ik it probleem oplosse mei ien line fan eksplisite INLINE. Op in stuit tusken GHC 8.4.4 en GHC 8.6.5 stoppe de optimizer dit op har eigen te dwaan.
Ik hie net ferwachte sokke smoargens tsjin te kommen yn Haskell-programmearring. Lykwols, sels hjoed, meitsje optimizers soms flaters, en it is ús taak om har hints te jaan. Bygelyks, hjir witte wy dat de funksje ynlined wurde moat, om't it yn 'e ymperatyf ferzje is ynlined, en dit is in reden om de kompilator in hint te jaan.
Wat barde dêrnei?
Doe haw ik it Hopcroft-Karp-algoritme ymplementearre mei oare monaden, en dat wie it ein fan it programma.
Mei tank oan Google Summer of Code haw ik praktyske ûnderfining opdien yn funksjoneel programmearring, wat my net allinich holp om in staazje te krijen by Jane Street de folgjende simmer (ik bin net wis hoe bekend dit plak sels is ûnder it betûfte publyk fan Habr, mar it is ien fan 'e pear wêr't jo simmer kinne om mei te dwaan oan funksjonele programmearring), mar ek yntrodusearre my oan' e prachtige wrâld fan it tapassen fan dit paradigma yn 'e praktyk, signifikant oars as myn ûnderfining yn tradisjonele talen.
Boarne: www.habr.com