Leschte Summer hunn ech deelgeholl - e Programm fir Studenten vu Google. All Joer wielen d'Organisateuren e puer Open Source Projeten aus, och vun esou bekannten Organisatiounen wéi и . Google invitéiert Studenten aus der ganzer Welt un dëse Projeten ze schaffen.
Als Participant am Google Summer of Code 2019 hunn ech e Projet an der Bibliothéik gemaach mat der Organisatioun , déi d'Haskell Sprooch entwéckelt - eng vun de bekanntste funktionnelle Programméierungssproochen. Alga ass eng Bibliothéik déi duerstellt Representatioun fir Grafiken an Haskell. Et gëtt benotzt, zum Beispill, an - eng Github Bibliothéik déi semantesch Beem baut, Uruff an Ofhängegkeet Grafike baséiert op Code a kann se vergläichen. Mäi Projet war eng Typ-sécher Representatioun fir Bipartite Grafiken an Algorithmen fir dës Representatioun ze addéieren.
An dësem Post wäert ech iwwer meng Ëmsetzung vun engem Algorithmus schwätzen fir eng Grafik fir Bipartiteness an Haskell ze kontrolléieren. Och wann den Algorithmus ee vun de meeschte Basis ass, huet et mech e puer Iteratiounen ëmzesetzen an e funktionnelle Stil ëmzesetzen an zimlech vill Aarbecht erfuerdert. Als Resultat hunn ech mech op eng Ëmsetzung mat Monad Transformatoren etabléiert.
Iwwer mech selwer
Mäin Numm ass Vasily Alferov, ech sinn e véierte Joer Student um St. Virdrun am Blog geschriwwen ech и . Momentan sinn ech op engem Stage bei an Norwegen, wou ech op Approche fir de Problem schaffen . Meng Interesse enthalen parametriséiert Algorithmen a funktionell Programméierung.
Iwwer d'Ëmsetzung vum Algorithmus
Viruerteel
Studenten, déi um Programm deelhuelen, si staark encouragéiert ze bloggen. Si hunn mir eng Plattform fir de Blog ginn . Dësen Artikel ass eng Iwwersetzung , vu mir do am Juli op Englesch geschriwwen, mat engem kuerze Virwuert.
Pull Ufro mam Code a Fro ka fonnt ginn .
Dir kënnt iwwer d'Resultater vu menger Aarbecht liesen (op Englesch) .
Dëse Post gëtt ugeholl datt de Lieser d'Basiskonzepter an der funktioneller Programméierung vertraut ass, obwuel ech probéieren all d'Begrëffer ze erënneren déi benotzt ginn wann d'Zäit kënnt.
Iwwerpréift Grafike fir bipartiteness
En Algorithmus fir eng Grafik fir Bipartite ze kontrolléieren gëtt normalerweis an engem Cours iwwer Algorithmen als ee vun den einfachsten Grafikalgorithmen ginn. Seng Iddi ass einfach: als éischt setzen mir iergendwéi Wirbelen an de lénksen oder rietsen Deel, a wann e konfliktende Rand fonnt gëtt, behaapte mir datt d'Grafik net bipartite ass.
E bësse méi Detail: als éischt setzen mir e Vertex an de lénksen Deel. Natierlech mussen all d'Noperen vun dësem Wirbel an der rietser Lobe leien. Weider mussen all d'Noperen vun den Noperen vun dësem Wirbel an der lénkser Lobe leien, a sou weider. Mir weider deelen zu Wirbelen zougewisen soulaang et nach Wirbelen an der verbonne Komponente vun der Wirbelsäit sinn mir ugefaang mat datt mir Noperen net zougewisen hunn. Mir widderhuelen dann dës Aktioun fir all verbonne Komponente.
Wann et e Rand tëscht Wirbelen ass, déi an déiselwecht Partition falen, ass et net schwéier en komeschen Zyklus an der Grafik ze fannen, wat wäit bekannt ass (a ganz offensichtlech) an enger bipartite Grafik onméiglech ass. Soss hu mir eng korrekt Partition, dat heescht datt d'Grafik bipartite ass.
Typesch gëtt dësen Algorithmus mat Hëllef ëmgesat oder . An imperativ Sproochen gëtt Déift-éischt Sich normalerweis benotzt well et liicht méi einfach ass an keng zousätzlech Datestrukturen erfuerdert. Ech hunn och Déift-éischt Sich gewielt well et méi traditionell ass.
Sou koume mir zum folgende Schema. Mir iwwerwannen d'Wierder vun der Grafik mat Hëllef vun Déift-éischt Sich an ginn Aktien un hinnen zou, änneren d'Zuel vum Undeel wéi mir laanscht de Rand bewegen. Wa mir probéieren eng Undeel un engem Wirbels ze zouzeschreiwen, datt schonn en Deel zougewisen huet, kënne mir sécher soen, datt d'Grafik net bipartite ass. De Moment ginn all Wirbelen en Deel zougewisen a mir hunn all d'Kante gekuckt, hu mir eng gutt Partition.
Rengheet vun Berechnungen
An Haskell mir dovun ausgoen, datt all Berechnungen sinn propper. Wéi och ëmmer, wann dëst wierklech de Fall wier, hätte mir kee Wee fir eppes op den Ecran ze drécken. Iwwerhaapt, propper sinn Berechnunge sinn esou faul datt et net een ass propper Grënn fir eppes ze berechnen. All Berechnungen, déi am Programm geschéien, ginn iergendwéi gezwongen "onrein" monad IO.
Monads sinn e Wee fir Berechnungen mat ze representéieren Effekter zu Haskell. Erkläre wéi se funktionnéieren ass iwwer den Ëmfang vun dësem Post. Eng gutt a kloer Beschreiwung kann op Englesch gelies ginn .
Hei wëll ech drop hiweisen datt während e puer Monaden, wéi IO, duerch Compiler Magie ëmgesat ginn, bal all déi aner a Software ëmgesat ginn an all Berechnungen an hinnen reng sinn.
Et gi vill Effekter an all huet seng eege Monad. Dëst ass eng ganz staark a schéin Theorie: all Monade implementéieren déiselwecht Interface. Mir schwätzen iwwer déi folgend dräi Monaden:
- Entweder e a ass eng Berechnung déi e Wäert vum Typ a zréckginn oder eng Ausnam vum Typ e werft. D'Behuele vun dëser Monad ass ganz ähnlech wéi d'Ausnahmshandhabung an imperativen Sproochen: Feeler kënne gefaangen oder weidergeleet ginn. Den Haaptunterschied ass datt d'Monad komplett logesch an der Standardbibliothéik zu Haskell implementéiert ass, während imperativ Sprooche normalerweis Betribssystem Mechanismen benotzen.
- Staat s a ass eng Berechnung déi e Wäert vum Typ a zréckkënnt an Zougang zum mutablen Zoustand vum Typ s huet.
- Vläicht a. D'Vläicht Monad dréckt eng Berechnung aus, déi zu all Moment ënnerbrach ka ginn andeems Dir Näischt zréckschéckt. Wéi och ëmmer, mir schwätzen iwwer d'Ëmsetzung vun der MonadPlus Klass fir den Typ Maybe, deen de Géigendeel Effekt ausdréckt: et ass eng Berechnung déi zu all Moment ënnerbrach ka ginn andeems Dir e spezifesche Wäert zréckkënnt.
Ëmsetzung vum Algorithmus
Mir hunn zwou Datentypen, Grafik a a Bigraph a b, déi éischt vun deenen Grafike mat Wirbelen duerstellt mat Wäerter vum Typ a markéiert, an déi zweet representéiert bipartite Grafike mat lénksen Wirbelen mat Wäerter vum Typ a a riets markéiert -Säit Wirbelen markéiert mat Wäerter vum Typ b.
Dëst sinn net Typen aus der Alga-Bibliothéik. Alga huet keng Representatioun fir ongeriicht bipartite Grafike. Ech hunn d'Typen esou gemaach fir Kloerheet.
Mir brauchen och Hëllefsfunktiounen mat de folgenden Ënnerschrëften:
-- Список соседей данной вершины.
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)Et ass einfach ze gesinn datt wa mir wärend der Déift-éischt Sich e konfliktende Rand fonnt hunn, de komeschen Zyklus läit uewen um Rekursiounsstapel. Also, fir et ze restauréieren, musse mir alles aus dem Rekursiounsstapel bis zum éischten Optriede vum leschte Wirbel ofschneiden.
Mir implementéieren Déift-éischt Sich andeems en assoziativen Array vun Undeelnummeren fir all Wirbel erhalen. De Rekursiounsstack gëtt automatesch duerch d'Ëmsetzung vun der Functor-Klass vun der Monad, déi mir gewielt hunn, erhale gelooss: mir brauchen nëmmen all Wirbelen aus dem Wee an d'Resultat zréckzeginn aus der rekursiver Funktioun.
Meng éischt Iddi war d'Entweder Monad ze benotzen, déi schéngt genau déi Effekter ëmzesetzen déi mir brauchen. Déi éischt Ëmsetzung, déi ech geschriwwen hunn, war ganz no bei dëser Optioun. Tatsächlech hat ech fënnef verschidden Implementatiounen op engem Punkt a schlussendlech op eng aner etabléiert.
Als éischt musse mir eng assoziativ Array vun Undeelidentifizéierer erhalen - dëst ass eppes iwwer Staat. Zweetens musse mir kënnen ophalen wann e Konflikt festgestallt gëtt. Dëst kann entweder Monad fir Entweder sinn, oder MonadPlus fir vläicht. Den Haaptunterschied ass datt Entweder e Wäert zréckginn kann wann d'Berechnung net gestoppt gouf, a vläicht gëtt an dësem Fall nëmmen Informatioun iwwer dëst zréck. Well mir brauchen net eng separat Wäert fir Succès (et ass schonn am Staat gespäichert), mir wielen vläicht. An am Moment wou mir d'Effekter vun zwou Monade musse kombinéieren, kommen se eraus , déi genee dës Effekter kombinéieren.
Firwat hunn ech sou e komplexen Typ gewielt? Zwee Grënn. Als éischt ass d'Ëmsetzung ganz ähnlech wéi Imperativ. Zweetens musse mir de Retourwäert am Fall vu Konflikt manipuléieren wann Dir zréck vu Rekursioun zréckkënnt fir déi komesch Loop ze restauréieren, wat vill méi einfach ass an der Vläicht Monad ze maachen.
Sou kréien mir dës Ëmsetzung.
{-# 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)
De wou Block ass de Kär vum Algorithmus. Ech probéieren ze erklären wat dobannen geschitt.
- inVertex ass den Deel vun der Déift-éischt Sich wou mir de Wirbel fir d'éischte Kéier besichen. Hei ginn mir eng Undeel Zuel un der Wirbelsail a lafen onEdge op all Noperen. Dëst ass och wou mir den Uruffstack restauréieren: wann msum e Wäert zréckginn, drécke mir Vertex v do.
- onEdge ass den Deel wou mir de Rand besichen. Et gëtt zweemol fir all Rand genannt. Hei kucke mer ob de Wirbel op der anerer Säit besicht gouf, a besicht se wann net. Wa mir besicht ginn, kontrolléiere mir ob de Rand konfliktend ass. Wann et ass, gi mir de Wäert zréck - déi ganz Spëtzt vum Rekursiounsstapel, wou all aner Wirbelen dann beim Retour gesat ginn.
- processVertex kontrolléiert fir all Vertex ob et besicht gouf a leeft inVertex drop wann net.
- dfs leeft processVertex op all Wirbelen.
Dat ass alles.
Geschicht vum Wuert INLINE
D'Wuert INLINE war net an der éischter Ëmsetzung vum Algorithmus; et erschéngt méi spéit. Wann ech probéiert eng besser Ëmsetzung ze fannen, Ech hu festgestallt, datt d'Net-INLINE Versioun op e puer Grafike merkbar méi lues war. Bedenkt datt semantesch d'Funktiounen d'selwecht solle funktionnéieren, huet dëst mech immens iwwerrascht. Och friem, op enger anerer Maschinn mat enger anerer Versioun vum GHC war keen merkbare Ënnerscheed.
Nodeems ech eng Woch de GHC Core Output gelies hunn, konnt ech de Problem mat enger Linn vun explizit INLINE fixéieren. Irgendwann tëscht GHC 8.4.4 an GHC 8.6.5 huet den Optimizer opgehalen dëst eleng ze maachen.
Ech hat net erwaart esou Dreck an der Haskell Programméierung ze begéinen. Wéi och ëmmer, och haut, Optimisateure maachen heiansdo Feeler, an et ass eis Aarbecht hinnen Hiweiser ze ginn. Zum Beispill, hei wësse mer datt d'Funktioun soll inlined sinn well se an der Imperativ Versioun inlined ass, an dëst ass e Grond fir de Compiler en Hiweis ze ginn.
Wat ass duerno geschitt?
Duerno hunn ech den Hopcroft-Karp Algorithmus mat anere Monaden ëmgesat, an dat war den Enn vum Programm.
Dank Google Summer of Code hunn ech praktesch Erfarung a funktionell Programméierung gewonnen, wat mir net nëmmen gehollef huet de nächste Summer e Stage op der Jane Street ze kréien (ech sinn net sécher wéi bekannt dës Plaz souguer ënner dem Habr sengem wëssenschaftleche Publikum ass, awer et ass eng vun de puer wou Dir kënnt Summer fir funktionell programméiere ze engagéieren), mä och agefouert mech an déi wonnerbar Welt vun Applikatioun vun dësem Paradigma an der Praxis, wesentlech anescht wéi meng Erfahrung an traditionell Sproochen.
Source: will.com