Lastan someron mi partoprenis - programo por studentoj de Guglo. Ĉiujare, la organizantoj elektas plurajn Malfermfontajn projektojn, inkluzive de tiaj konataj organizoj kiel и . Guglo invitas studentojn el la tuta mondo labori pri ĉi tiuj projektoj.
Kiel partoprenanto en Google Summer of Code 2019, mi faris projekton ene de la biblioteko kun la organizo , kiu disvolvas la Haskell-lingvon - unu el la plej famaj funkciaj programlingvoj. Algo estas biblioteko kiu reprezentas reprezentado por grafeoj en Haskell. Ĝi estas uzata, ekzemple, en — Github-biblioteko kiu konstruas semantikajn arbojn, vokaj kaj dependecaj grafikaĵoj bazitaj sur kodo kaj povas kompari ilin. Mia projekto estis aldoni tip-sekuran reprezentadon por dupartiaj grafeoj kaj algoritmoj por tiu reprezentado.
En ĉi tiu afiŝo mi parolos pri mia efektivigo de algoritmo por kontroli grafeon por ambaŭpartieco en Haskell. Kvankam la algoritmo estas unu el la plej bazaj, efektivigi ĝin bele en funkcia stilo prenis al mi plurajn ripetojn kaj postulis sufiĉe multe da laboro. Kiel rezulto, mi decidis pri efektivigo kun monadtransformiloj.
Pri mi
Mi nomiĝas Vasilij Alferov, mi estas kvarjara studento ĉe Peterburga HSE. Antaŭe en la blogo mi skribis и . Ĝuste nun mi estas en staĝo ĉe en Norvegio, kie mi laboras pri aliroj al la problemo . Miaj interesoj inkluzivas parametrizajn algoritmojn kaj funkcian programadon.
Pri la efektivigo de la algoritmo
Antaŭparolo
Studentoj partoprenantaj en la programo estas forte instigitaj blogi. Ili provizis al mi platformon por la blogo . Ĉi tiu artikolo estas traduko , verkita de mi tie en julio en la angla, kun mallonga antaŭparolo.
Tiro Peto kun la koncerna kodo troveblas .
Vi povas legi pri la rezultoj de mia laboro (en la angla) .
Ĉi tiu afiŝo celas familiarigi la leganton kun la bazaj konceptoj en funkcia programado, kvankam mi provos rememori ĉiujn terminojn uzatajn kiam venos la tempo.
Kontrolante grafikaĵojn por ambaŭpartieco
Algoritmo por kontroli grafeon por ambaŭpartieco estas kutime donita en kurso pri algoritmoj kiel unu el la plej simplaj grafealgoritmoj. Lia ideo estas simpla: unue ni iel metas verticojn en la maldekstran aŭ dekstran parton, kaj kiam konfliktanta rando estas trovita, ni asertas ke la grafeo ne estas duflanka.
Iom pli da detalo: unue ni metas iom da vertico en la maldekstra parto. Evidente, ĉiuj najbaroj de ĉi tiu vertico devas kuŝi en la dekstra lobo. Plue, ĉiuj najbaroj de la najbaroj de ĉi tiu vertico devas kuŝi en la maldekstra lobo, ktp. Ni daŭre asignas akciojn al verticoj tiel longe kiel ekzistas ankoraŭ verticoj en la koneksa komponanto de la vertico, per kiu ni komencis, al kiu ni ne asignis najbarojn. Ni tiam ripetas ĉi tiun agon por ĉiuj konektitaj komponantoj.
Se ekzistas rando inter verticoj kiuj falas en la saman sekcion, estas ne malfacile trovi strangan ciklon en la grafeo, kiu estas vaste konata (kaj sufiĉe evidente) neebla en duparta grafeo. Alie, ni havas ĝustan subdiskon, kio signifas, ke la grafeo estas duflanka.
Tipe, ĉi tiu algoritmo estas efektivigita uzante aŭ . En nepraj lingvoj, profund-unua serĉo estas kutime uzata ĉar ĝi estas iomete pli simpla kaj ne postulas pliajn datumstrukturojn. Mi ankaŭ elektis profundan serĉon ĉar ĝi estas pli tradicia.
Tiel, ni venis al la sekva skemo. Ni trairas la verticojn de la grafeo uzante profundan serĉon kaj asignas akciojn al ili, ŝanĝante la nombron de la parto dum ni moviĝas laŭ la rando. Se ni provas asigni parton al vertico kiu jam havas parton asignita, ni povas sekure diri ke la grafeo ne estas duflanka. En la momento, kiam ĉiuj verticoj ricevas parton kaj ni rigardis ĉiujn randojn, ni havas bonan sekcion.
Pureco de kalkuloj
En Haskell ni supozas ke ĉiuj kalkuloj estas purigi. Tamen, se ĉi tio estus vere la kazo, ni ne havus manieron presi ion ajn al la ekrano. Entute, pura kalkuloj estas tiel maldiligentaj, ke ne ekzistas unu purigi kialoj por kalkuli ion. Ĉiuj kalkuloj okazantaj en la programo estas iel devigitaj "malpura" monado IO.
Monadoj estas maniero reprezenti kalkulojn per efikoj en Haskell. Klarigi kiel ili funkcias estas preter la amplekso de ĉi tiu afiŝo. Bona kaj klara priskribo legeblas en la angla .
Ĉi tie mi volas atentigi, ke dum kelkaj monadoj, kiel IO, estas efektivigitaj per kompilila magio, preskaŭ ĉiuj aliaj estas efektivigitaj en programaro kaj ĉiuj kalkuloj en ili estas puraj.
Estas multaj efikoj kaj ĉiu havas sian propran monadon. Ĉi tio estas tre forta kaj bela teorio: ĉiuj monadoj efektivigas la saman interfacon. Ni parolos pri la sekvaj tri monadoj:
- Aŭ e a estas kalkulo, kiu redonas valoron de tipo a aŭ ĵetas escepton de tipo e. La konduto de ĉi tiu monado estas tre simila al escepttraktado en imperativaj lingvoj: eraroj povas esti kaptitaj aŭ transdonitaj. La ĉefa diferenco estas, ke la monado estas tute logike efektivigita en la norma biblioteko en Haskell, dum nepraj lingvoj kutime uzas operaciumajn mekanismojn.
- Ŝtato s a estas kalkulo kiu liveras valoron de tipo a kaj havas aliron al ŝanĝebla stato de tipo s.
- Eble a. La Eble monado esprimas komputadon kiu povas esti interrompita iam ajn per resendado de Nenio. Tamen, ni parolos pri la efektivigo de la klaso MonadPlus por la Eble-tipo, kiu esprimas la kontraŭan efikon: ĝi estas kalkulo, kiu povas esti interrompita en ajna momento, redonante specifan valoron.
Efektivigo de la algoritmo
Ni havas du datumtipojn, Graph a kaj Bigraph a b, la unua el kiuj reprezentas grafeojn kun verticoj etikeditaj kun valoroj de tipo a, kaj la dua reprezentas dupartiajn grafeojn kun maldekstraflankaj verticoj etikeditaj per valoroj de tipo a kaj dekstra. -flankaj verticoj etikeditaj kun valoroj de tipo b.
Ĉi tiuj ne estas tipoj de la Alga biblioteko. Algo ne havas reprezenton por nedirektaj dupartiaj grafeoj. Mi faris tiajn tipojn por klareco.
Ni ankaŭ bezonos helpajn funkciojn kun la jenaj subskriboj:
-- Список соседей данной вершины.
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)Estas facile vidi, ke se dum la profundo-unua serĉo ni trovis konfliktan randon, la nepara ciklo kuŝas sur la supro de la rekursa stako. Tiel, por restarigi ĝin, ni devas fortranĉi ĉion de la rekursa stako ĝis la unua okazo de la lasta vertico.
Ni efektivigas profundan serĉon konservante asocian tabelon de akciaj nombroj por ĉiu vertico. La rekursia stako estos aŭtomate konservita per la efektivigo de la Functor-klaso de la monado, kiun ni elektis: ni nur bezonos meti ĉiujn verticojn de la vojo en la rezulton revenitan de la rekursiva funkcio.
Mia unua ideo estis uzi la Either-monadon, kiu ŝajnas efektivigi ĝuste la efikojn, kiujn ni bezonas. La unua efektivigo, kiun mi skribis, estis tre proksima al ĉi tiu opcio. Fakte, mi havis kvin malsamajn efektivigojn en unu momento kaj finfine decidiĝis pri alia.
Unue, ni devas konservi asociecan aron de akciaj identigiloj - ĉi tio estas io pri Ŝtato. Due, ni devas povi halti kiam konflikto estas detektita. Ĉi tio povas esti aŭ Monad por Either, aŭ MonadPlus por Eble. La ĉefa diferenco estas, ke Ambaŭ povas redoni valoron se la kalkulo ne estis ĉesigita, kaj Eble redonas nur informojn pri ĉi tiu kazo. Ĉar ni ne bezonas apartan valoron por sukceso (ĝi jam estas konservita en Ŝtato), ni elektas Eble. Kaj en la momento, kiam ni bezonas kombini la efikojn de du monadoj, ili aperas , kiuj ĝuste kombinas ĉi tiujn efikojn.
Kial mi elektis tian kompleksan tipon? Du kialoj. Unue, la efektivigo montriĝas tre simila al imperativo. Due, ni devas manipuli la revenan valoron en kazo de konflikto kiam revenas reen de rekurso por restarigi la neparan buklon, kio estas multe pli facila por fari en la Eble monado.
Tiel ni ricevas ĉi tiun efektivigon.
{-# 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)
La kie bloko estas la kerno de la algoritmo. Mi provos klarigi kio okazas en ĝi.
- inVertex estas la parto de profunda serĉo, kie ni vizitas la verticon unuafoje. Ĉi tie ni atribuas akcian numeron al la vertico kaj rulas onEdge sur ĉiuj najbaroj. Ĉi tie ankaŭ estas kie ni restarigas la voka stako: se msum redonis valoron, ni puŝas vertico v tien.
- onEdge estas la parto kie ni vizitas la randon. Ĝi estas nomita dufoje por ĉiu rando. Ĉi tie ni kontrolas ĉu la vertico ĉe la alia flanko estis vizitita, kaj vizitas ĝin se ne. Se vizitite, ni kontrolas ĉu la rando konfliktas. Se ĝi estas, ni resendas la valoron - la plej supro de la rekursa stako, kie ĉiuj aliaj verticoj tiam estos metitaj post reveno.
- processVertex kontrolas por ĉiu vertico ĉu ĝi estis vizitita kaj rulas enVertex sur ĝi se ne.
- dfs rulas processVertex sur ĉiuj verticoj.
Tio estas ĉio.
Historio de la vorto INLINE
La vorto INLINE ne estis en la unua efektivigo de la algoritmo; ĝi aperis poste. Kiam mi provis trovi pli bonan efektivigon, mi trovis, ke la ne-INLINE-versio estis rimarkeble pli malrapida en kelkaj grafikaĵoj. Konsiderante ke semantike la funkcioj devus funkcii same, tio ege surprizis min. Eĉ pli stranga, sur alia maŝino kun malsama versio de GHC ne estis rimarkebla diferenco.
Pasiginte semajnon legante la GHC Core-produktaĵon, mi povis ripari la problemon per unu linio de eksplicita INLINE. En iu momento inter GHC 8.4.4 kaj GHC 8.6.5 la optimumigilo ĉesis fari tion memstare.
Mi ne atendis renkonti tian malpuraĵon en Haskell-programado. Tamen, eĉ hodiaŭ, optimumigantoj foje faras erarojn, kaj estas nia tasko doni al ili sugestojn. Ekzemple, ĉi tie ni scias, ke la funkcio devus esti enliniita ĉar ĝi estas enliniita en la imperativa versio, kaj ĉi tio estas kialo por doni al la kompililo sugeston.
Kio okazis poste?
Tiam mi efektivigis la Hopcroft-Karp-algoritmon kun aliaj monadoj, kaj tio estis la fino de la programo.
Danke al Google Summer of Code, mi akiris praktikan sperton pri funkcia programado, kiu ne nur helpis min akiri staĝon ĉe Jane Street la sekvan someron (mi ne certas kiom konata ĉi tiu loko estas eĉ inter la sperta publiko de Habr, sed ĝi estas unu el la malmultaj kie oni povas someri okupiĝi pri funkcia programado), sed ankaŭ enkondukis min en la mirindan mondon de aplikado de ĉi tiu paradigmo en la praktiko, signife malsama ol mia sperto en tradiciaj lingvoj.
fonto: www.habr.com