Praėjusią vasarą dalyvavau - programa studentams iš Google. Kiekvienais metais organizatoriai atrenka po kelis atvirojo kodo projektus, tarp jų ir iš tokių žinomų organizacijų kaip и . „Google“ kviečia studentus iš viso pasaulio dirbti su šiais projektais.
Kaip „Google Summer of Code 2019“ dalyvis, įgyvendinau projektą bibliotekoje su organizacija , kuri kuria Haskell kalbą – vieną žinomiausių funkcinio programavimo kalbų. Alga yra biblioteka, kuri atstovauja grafų vaizdavimas Haskell. Jis naudojamas, pavyzdžiui, — Github biblioteka, kuri pagal kodą kuria semantinius medžius, skambučių ir priklausomybės grafikus ir gali juos palyginti. Mano projektas buvo pridėti tipams saugų dvišalių grafikų atvaizdavimą ir to atvaizdavimo algoritmus.
Šiame įraše kalbėsiu apie savo algoritmo, skirto Haskell grafiko dvišališkumo tikrinimo, įgyvendinimą. Nors algoritmas yra vienas elementariausių, gražiai jį įgyvendinti funkciniu stiliumi man prireikė kelių iteracijų ir pareikalavo nemažai darbo. Dėl to aš apsisprendžiau įgyvendinti su monadiniais transformatoriais.
Apie mane
Mano vardas Vasilijus Alferovas, esu Sankt Peterburgo HSE ketvirto kurso studentas. Anksčiau dienoraštyje rašiau и . Šiuo metu esu stažuotėje Norvegijoje, kur dirbu prie problemos sprendimo būdų . Mano pomėgiai yra parametrizuoti algoritmai ir funkcinis programavimas.
Apie algoritmo įgyvendinimą
pratarmė
Programoje dalyvaujantys studentai labai raginami rašyti tinklaraštį. Jie suteikė man tinklaraščio platformą . Šis straipsnis yra vertimas , aš parašiau ten liepos mėnesį anglų kalba, su trumpa pratarme.
Galima rasti ištraukimo užklausą su atitinkamu kodu .
Apie mano darbo rezultatus galite paskaityti (anglų kalba) .
Šis įrašas skirtas supažindinti skaitytoją su pagrindinėmis funkcinio programavimo sąvokomis, nors atėjus laikui pasistengsiu prisiminti visus vartojamus terminus.
Diagramų dvišališkumo tikrinimas
Grafo dvišališkumo tikrinimo algoritmas paprastai pateikiamas algoritmų kurse kaip vienas paprasčiausių grafų algoritmų. Jo idėja yra paprasta: pirmiausia mes kažkaip dedame viršūnes į kairę arba dešinę dalį, o kai randame prieštaringą briauną, tvirtiname, kad grafas nėra dvišalis.
Šiek tiek detaliau: pirmiausia įdedame viršūnę į kairę dalį. Akivaizdu, kad visi šios viršūnės kaimynai turi būti dešinėje skiltyje. Be to, visi šios viršūnės kaimynų kaimynai turi gulėti kairėje skiltyje ir pan. Mes ir toliau priskiriame dalis viršūnėms tol, kol prijungtame viršūnės komponente, nuo kurio pradėjome, vis dar yra viršūnių, kurioms nepriskyrėme kaimynų. Tada pakartojame šį veiksmą visiems prijungtiems komponentams.
Jei tarp viršūnių, patenkančių į tą pačią skaidinį, yra briauna, grafe nesunku rasti nelyginį ciklą, o tai yra plačiai žinoma (ir gana akivaizdu) dvišaliame grafe. Kitu atveju turime teisingą skaidinį, o tai reiškia, kad grafikas yra dvišalis.
Paprastai šis algoritmas įgyvendinamas naudojant arba . Privalomose kalbose dažniausiai naudojama giluminė paieška, nes ji yra šiek tiek paprastesnė ir nereikalauja papildomų duomenų struktūrų. Taip pat pasirinkau giluminę paiešką, nes ji yra labiau tradicinė.
Taigi priėjome prie tokios schemos. Per grafiko viršūnes perkeliame naudodami paiešką pagal gylį ir priskiriame joms dalis, keičiant dalies skaičių judant išilgai krašto. Jei bandysime priskirti dalį viršūnei, kuriai jau yra priskirta dalis, galime drąsiai teigti, kad grafikas nėra dvišalis. Kai visoms viršūnėms priskiriama dalis ir mes peržiūrėjome visas briaunas, turime gerą skaidinį.
Skaičiavimų grynumas
Haskell mes manome, kad visi skaičiavimai yra švarus. Tačiau jei taip būtų, neturėtume galimybės nieko atspausdinti ekrane. Iš viso, švarus skaičiavimai tokie tingūs, kad jų nėra švarus priežasčių ką nors skaičiuoti. Visi programoje atliekami skaičiavimai yra kažkaip priversti "nešvarus" monada IO.
Monados yra būdas pateikti skaičiavimus efektai Haskellyje. Paaiškinimas, kaip jie veikia, nepatenka į šio įrašo taikymo sritį. Gerą ir aiškų aprašymą galima perskaityti anglų kalba .
Čia noriu atkreipti dėmesį, kad nors kai kurios monados, tokios kaip IO, yra įdiegtos naudojant kompiliatoriaus magiją, beveik visos kitos yra įdiegtos programinėje įrangoje ir visi skaičiavimai jose yra gryni.
Yra daug efektų ir kiekvienas turi savo monadą. Tai labai stipri ir graži teorija: visos monados įgyvendina tą pačią sąsają. Mes kalbėsime apie šias tris monadas:
- Arba ea yra skaičiavimas, kuris grąžina a tipo reikšmę arba pateikia e tipo išimtį. Šios monados elgesys labai panašus į išimčių apdorojimą imperatyviosiomis kalbomis: klaidas galima pagauti arba perduoti. Pagrindinis skirtumas yra tas, kad monada yra visiškai logiškai įdiegta standartinėje Haskell bibliotekoje, o būtinos kalbos paprastai naudoja operacinės sistemos mechanizmus.
- Būsena sa yra skaičiavimas, kuris grąžina a tipo reikšmę ir turi prieigą prie kintamos s tipo būsenos.
- Galbūt a. Galbūt monada išreiškia skaičiavimą, kurį galima bet kada nutraukti grąžinant Nieko. Tačiau kalbėsime apie MonadPlus klasės įdiegimą Maybe tipui, kuris išreiškia priešingą efektą: tai skaičiavimas, kurį galima bet kada nutraukti grąžinus konkrečią reikšmę.
Algoritmo įgyvendinimas
Turime du duomenų tipus: Graph a ir Bigraph ab, iš kurių pirmasis vaizduoja grafikus su viršūnėmis, pažymėtomis a tipo reikšmėmis, o antrasis - dvipusius grafikus su kairiosiomis viršūnėmis, pažymėtomis a tipo ir dešiniosios reikšmėmis. -šoninės viršūnės, pažymėtos b tipo reikšmėmis.
Tai nėra Algos bibliotekos tipai. Alga neturi neorientuotų dvišalių grafikų vaizdavimo. Aiškumo dėlei padariau tokius tipus.
Mums taip pat reikės pagalbinių funkcijų su šiais parašais:
-- Список соседей данной вершины.
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)Nesunku pastebėti, kad jei atliekant giluminę paiešką radome prieštaringą kraštą, nelyginis ciklas yra rekursijos krūvos viršuje. Taigi, norėdami jį atkurti, turime nupjauti viską nuo rekursijos krūvos iki pirmojo paskutinės viršūnės pasireiškimo.
Įgyvendiname giluminę paiešką, palaikydami asociatyvų kiekvienos viršūnės dalies skaičių masyvą. Rekursijos krūva bus automatiškai palaikoma įdiegus mūsų pasirinktos monados Functor klasę: mums reikės tik įdėti visas kelio viršūnes į rezultatą, grąžintą iš rekursinės funkcijos.
Mano pirmoji idėja buvo naudoti „Ether“ monadą, kuri, atrodo, įgyvendina būtent tokius efektus, kurių mums reikia. Pirmasis įgyvendinimas, kurį parašiau, buvo labai artimas šiam variantui. Tiesą sakant, vienu metu turėjau penkis skirtingus įgyvendinimus ir galiausiai apsisprendžiau prie kito.
Pirma, turime išlaikyti asociatyvų akcijų identifikatorių masyvą – tai kažkas apie būseną. Antra, aptikus konfliktą turime sugebėti sustoti. Tai gali būti arba Monad for Bet, arba MonadPlus for Maybe. Pagrindinis skirtumas yra tas, kad „Ether“ gali grąžinti reikšmę, jei skaičiavimas nebuvo sustabdytas, o „Maybe“ šiuo atveju pateikia tik informaciją apie tai. Kadangi sėkmei mums nereikia atskiros reikšmės (ji jau saugoma State), renkamės Galbūt. Ir tuo momentu, kai reikia sujungti dviejų monadų efektus, jie išryškėja , kurios tiksliai sujungia šiuos efektus.
Kodėl pasirinkau tokį sudėtingą tipą? Dvi priežastys. Pirma, įgyvendinimas yra labai panašus į imperatyvą. Antra, turime manipuliuoti grąžinimo reikšme konflikto atveju, kai grįžtame iš rekursijos, kad atkurtume nelyginę kilpą, o tai yra daug lengviau padaryti „Maybe“ monadoje.
Taigi mes gauname šį įgyvendinimą.
{-# 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)
Kur blokas yra algoritmo šerdis. Pabandysiu paaiškinti, kas vyksta jos viduje.
- inVertex yra pirmosios gilumos paieškos dalis, kurioje pirmą kartą aplankome viršūnę. Čia viršūnei priskiriame bendrinimo numerį ir paleidžiame onEdge visuose kaimynuose. Čia taip pat atkuriame iškvietimo krūvą: jei msum grąžino reikšmę, ten nustumiame viršūnę v.
- onEdge yra dalis, kurioje lankome kraštą. Kiekvienam kraštui jis vadinamas du kartus. Čia patikriname, ar kitoje pusėje esanti viršūnė buvo aplankyta, ir aplankome, jei ne. Jei lankotės, patikriname, ar kraštas neprieštarauja. Jei taip, mes grąžiname reikšmę – pačią rekursijos krūvos viršūnę, kur grįžus bus patalpintos visos kitos viršūnės.
- ProcessVertex patikrina kiekvieną viršūnę, ar ji buvo aplankyta, ir paleidžia inVertex, jei ne.
- dfs paleidžia processVertex visose viršūnėse.
Štai ir viskas.
Žodžio INLINE istorija
Žodis INLINE nebuvo pirmą kartą įdiegtas algoritmas, jis pasirodė vėliau. Kai bandžiau rasti geresnį įgyvendinimą, pastebėjau, kad kai kuriuose grafikuose ne INLINE versija buvo pastebimai lėtesnė. Atsižvelgiant į tai, kad semantiškai funkcijos turėtų veikti taip pat, tai mane labai nustebino. Dar keista, kad kitoje mašinoje su kita GHC versija nebuvo pastebimo skirtumo.
Praleidęs savaitę skaitydamas GHC Core išvestį, galėjau išspręsti problemą viena aiškios INLINE eilutės eilute. Tam tikru momentu tarp GHC 8.4.4 ir GHC 8.6.5 optimizavimo priemonė nustojo tai daryti pati.
Nesitikėjau susidurti su tokiu purvu Haskell programavimo metu. Tačiau ir šiandien optimizuotojai kartais klysta, o mūsų darbas yra duoti jiems užuominas. Pavyzdžiui, čia mes žinome, kad funkcija turėtų būti įterpta, nes ji yra įterptoje imperatyviojoje versijoje, ir tai yra priežastis pateikti kompiliatoriui užuominą.
Kas nutiko toliau?
Tada įdiegiau Hopcroft-Karp algoritmą su kitomis monadomis, ir tuo programa baigėsi.
„Google Summer of Code“ dėka įgavau praktinės funkcinio programavimo patirties, kuri ne tik padėjo kitą vasarą atlikti praktiką Jane gatvėje (nesu tikras, ar ši vieta žinoma net tarp Habro išmanančios auditorijos, bet iš nedaugelio, kur galite vasarą užsiimti funkciniu programavimu), bet taip pat supažindino mane su nuostabiu šios paradigmos taikymo praktikoje pasauliu, kuris labai skiriasi nuo mano patirties naudojant tradicines kalbas.
Šaltinis: www.habr.com