Vara trecută am participat la - un program pentru studenți de la Google. În fiecare an, organizatorii selectează mai multe proiecte Open Source, inclusiv din organizații cunoscute precum и . Google invită studenți din întreaga lume să lucreze la aceste proiecte.
Ca participant la Google Summer of Code 2019, am realizat un proiect în cadrul bibliotecii cu organizatia , care dezvoltă limbajul Haskell - unul dintre cele mai cunoscute limbaje de programare funcțională. Alga este o bibliotecă care reprezintă reprezentare pentru grafice în Haskell. Este folosit, de exemplu, în — o bibliotecă Github care construiește arbori semantici, grafice de apeluri și dependențe bazate pe cod și le poate compara. Proiectul meu a fost să adaug o reprezentare sigură de tip pentru graficele bipartite și algoritmi pentru acea reprezentare.
În această postare voi vorbi despre implementarea mea a unui algoritm pentru verificarea unui grafic pentru bipartitate în Haskell. Chiar dacă algoritmul este unul dintre cele mai de bază, implementarea lui frumos într-un stil funcțional mi-a luat mai multe iterații și a necesitat destul de multă muncă. Drept urmare, m-am hotărât pe o implementare cu transformatoare monade.
Despre mine
Numele meu este Vasily Alferov, sunt student în anul IV la HSE din Sankt Petersburg. Mai devreme pe blog am scris и . În acest moment sunt într-un stagiu la în Norvegia, unde lucrez la abordări ale problemei . Interesele mele includ algoritmi parametrizați și programarea funcțională.
Despre implementarea algoritmului
Prefață
Studenții care participă la program sunt încurajați să scrie pe blog. Mi-au oferit o platformă pentru blog . Acest articol este o traducere , scris de mine acolo în iulie în engleză, cu o scurtă prefață.
Pull Request cu codul în cauză poate fi găsit .
Puteți citi despre rezultatele muncii mele (în engleză) .
Acest post are scopul de a familiariza cititorul cu conceptele de bază în programarea funcțională, deși voi încerca să amintesc toți termenii folosiți când va veni momentul.
Verificarea graficelor pentru bipartitate
Un algoritm pentru verificarea caracterului bipartit al unui grafic este de obicei prezentat într-un curs despre algoritmi ca unul dintre cei mai simpli algoritmi de grafic. Ideea lui este simplă: mai întâi punem cumva vârfuri în partea stângă sau dreaptă, iar când se găsește o muchie conflictuală, afirmăm că graficul nu este bipartit.
Mai multe detalii: mai întâi punem niște vârfuri în cota din stânga. Evident, toți vecinii acestui vârf trebuie să se afle în lobul drept. În plus, toți vecinii vecinilor acestui vârf trebuie să se afle în lobul stâng și așa mai departe. Continuăm să atribuim acțiuni la vârfuri atâta timp cât mai există vârfuri în componenta conectată a vârfului cu care am început, cărora nu le-am atribuit vecini. Repetăm apoi această acțiune pentru toate componentele conectate.
Dacă există o muchie între vârfuri care se încadrează în aceeași partiție, nu este dificil să găsești un ciclu impar în grafic, ceea ce este larg cunoscut (și destul de evident) imposibil într-un graf bipartit. În caz contrar, avem o partiție corectă, ceea ce înseamnă că graficul este bipartit.
De obicei, acest algoritm este implementat folosind sau . În limbile imperative, căutarea în profunzime este de obicei folosită, deoarece este puțin mai simplă și nu necesită structuri de date suplimentare. De asemenea, am ales căutarea în profunzime, deoarece este mai tradițională.
Astfel, am ajuns la următoarea schemă. Parcurgem nodurile graficului folosind căutarea depth-first și le atribuim acțiuni, schimbând numărul cotei pe măsură ce ne deplasăm de-a lungul marginii. Dacă încercăm să atribuim o cotă unui vârf care are deja o cotă alocată, putem spune cu siguranță că graficul nu este bipartit. În momentul în care tuturor nodurilor li se atribuie o cotă și ne-am uitat la toate marginile, avem o partiție bună.
Puritatea calculelor
În Haskell presupunem că toate calculele sunt curat. Cu toate acestea, dacă acesta ar fi cu adevărat cazul, nu am avea nicio modalitate de a imprima nimic pe ecran. Deloc, curat calculele sunt atât de leneșe încât nu există curat motive pentru a calcula ceva. Toate calculele care apar în program sunt cumva forțate "necurat" monada IO.
Monadele sunt o modalitate de a reprezenta calcule cu efecte în Haskell. Explicarea modului în care funcționează depășește scopul acestei postări. O descriere bună și clară poate fi citită în limba engleză .
Aici vreau să subliniez că, în timp ce unele monade, cum ar fi IO, sunt implementate prin magia compilatorului, aproape toate celelalte sunt implementate în software și toate calculele din ele sunt pure.
Sunt o mulțime de efecte și fiecare are propria sa monada. Aceasta este o teorie foarte puternică și frumoasă: toate monadele implementează aceeași interfață. Vom vorbi despre următoarele trei monade:
- Fie ea este un calcul care returnează o valoare de tip a, fie aruncă o excepție de tip e. Comportamentul acestei monade este foarte asemănător cu gestionarea excepțiilor în limbaje imperative: erorile pot fi prinse sau transmise. Principala diferență este că monada este implementată complet logic în biblioteca standard din Haskell, în timp ce limbile imperative folosesc de obicei mecanisme ale sistemului de operare.
- Starea sa este un calcul care returnează o valoare de tip a și are acces la starea mutabilă de tip s.
- Poate un. Monada Maybe exprimă un calcul care poate fi întrerupt în orice moment, returnând Nimic. Totuși, vom vorbi despre implementarea clasei MonadPlus pentru tipul Maybe, care exprimă efectul opus: este un calcul care poate fi întrerupt oricând prin returnarea unei anumite valori.
Implementarea algoritmului
Avem două tipuri de date, Graph a și Bigraph ab, primul dintre care reprezintă grafice cu vârfuri etichetate cu valori de tip a, iar al doilea reprezintă grafice bipartite cu vârfuri din stânga etichetate cu valori de tip a și dreapta -vârfurile laterale etichetate cu valori de tip b.
Acestea nu sunt tipuri din biblioteca Alga. Alga nu are o reprezentare pentru graficele bipartite nedirecționate. Am făcut astfel de tipuri pentru claritate.
De asemenea, vom avea nevoie de funcții de ajutor cu următoarele semnături:
-- Список соседей данной вершины.
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)Este ușor de observat că, dacă în timpul căutării în profunzime, am găsit o margine conflictuală, ciclul impar se află deasupra stivei de recursivitate. Astfel, pentru a-l restabili, trebuie să tăiem totul, de la stiva de recursivitate până la prima apariție a ultimului vârf.
Implementăm căutarea în profunzime, menținând o matrice asociativă de numere de acțiuni pentru fiecare vârf. Stiva de recursivitate va fi menținută automat prin implementarea clasei Functor a monadei pe care am ales-o: va trebui doar să punem toate nodurile din cale în rezultatul returnat de la funcția recursivă.
Prima mea idee a fost să folosesc monada Fie, care pare să implementeze exact efectele de care avem nevoie. Prima implementare pe care am scris-o a fost foarte aproape de această opțiune. De fapt, am avut cinci implementări diferite la un moment dat și în cele din urmă m-am hotărât pe alta.
În primul rând, trebuie să menținem o matrice asociativă de identificatori de acțiuni - acesta este ceva despre stat. În al doilea rând, trebuie să ne putem opri atunci când este detectat un conflict. Acesta poate fi fie Monad pentru Fie, fie MonadPlus pentru Poate. Principala diferență este că Fie poate returna o valoare dacă calculul nu a fost oprit și poate returnează doar informații despre aceasta în acest caz. Deoarece nu avem nevoie de o valoare separată pentru succes (este deja stocată în State), alegem Poate. Și în momentul în care trebuie să combinăm efectele a două monade, ele ies , care combina tocmai aceste efecte.
De ce am ales un tip atât de complex? Două motive. În primul rând, implementarea se dovedește a fi foarte asemănătoare cu imperativ. În al doilea rând, trebuie să manipulăm valoarea returnată în caz de conflict atunci când ne întoarcem din recursie pentru a restabili bucla impară, ceea ce este mult mai ușor de făcut în monada Maybe.
Astfel obținem această implementare.
{-# 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)
Blocul unde este nucleul algoritmului. Voi încerca să explic ce se întâmplă în interiorul ei.
- inVertex este partea căutării depth-first în care vizităm vârful pentru prima dată. Aici atribuim un număr de partajare vârfului și rulăm onEdge pe toți vecinii. Tot aici restaurăm stiva de apeluri: dacă msum a returnat o valoare, împingem vârful v acolo.
- onEdge este partea în care vizităm marginea. Se numește de două ori pentru fiecare margine. Aici verificăm dacă vârful de pe cealaltă parte a fost vizitat și îl vizităm dacă nu. Dacă este vizitat, verificăm dacă marginea este în conflict. Dacă este, returnăm valoarea - partea de sus a stivei recursive, unde toate celelalte vârfuri vor fi apoi plasate la întoarcere.
- processVertex verifică pentru fiecare vârf dacă a fost vizitat și rulează inVertex pe el dacă nu.
- dfs rulează processVertex pe toate nodurile.
Asta e tot.
Istoria cuvântului INLINE
Cuvântul INLINE nu a fost în prima implementare a algoritmului; a apărut mai târziu. Când am încercat să găsesc o implementare mai bună, am constatat că versiunea non-INLINE a fost vizibil mai lentă pe unele grafice. Având în vedere că din punct de vedere semantic funcțiile ar trebui să funcționeze la fel, acest lucru m-a surprins foarte mult. Și mai ciudat, pe o altă mașină cu o versiune diferită de GHC nu a existat nicio diferență notabilă.
După ce am petrecut o săptămână citind ieșirea GHC Core, am reușit să rezolv problema cu o linie de INLINE explicită. La un moment dat, între GHC 8.4.4 și GHC 8.6.5, optimizatorul a încetat să facă acest lucru singur.
Nu mă așteptam să întâlnesc o astfel de murdărie în programarea Haskell. Cu toate acestea, chiar și astăzi, optimizatorii fac uneori greșeli și este datoria noastră să le oferim indicii. De exemplu, aici știm că funcția ar trebui să fie aliniată pentru că este inlineată în versiunea imperativă și acesta este un motiv pentru a oferi compilatorului un indiciu.
Ce s-a întâmplat în continuare?
Apoi am implementat algoritmul Hopcroft-Karp cu alte monade și acesta a fost sfârșitul programului.
Datorită Google Summer of Code, am câștigat experiență practică în programarea funcțională, ceea ce nu numai că m-a ajutat să obțin un stagiu la Jane Street în vara următoare (nu sunt sigur cât de cunoscut este acest loc chiar în rândul publicului informat al lui Habr, dar este unul dintre puținele în care poți vara să te angajezi în programare funcțională), dar m-a și introdus în lumea minunată a aplicării acestei paradigme în practică, semnificativ diferită de experiența mea în limbile tradiționale.
Sursa: www.habr.com