În vara trecută, am participat la — un program pentru studenți de la Google. Anual, organizatorii selectează câteva proiecte Open Source, inclusiv de la organizații cunoscute precum și . Pentru a lucra la aceste proiecte, Google invită studenți din întreaga lume.
Ca participant la Google Summer of Code 2019, am realizat un proiect în cadrul bibliotecii împreună cu organizația , care se ocupă cu dezvoltarea limbajului Haskell — unul dintre cele mai cunoscute limbaje de programare funcțională. Alga — o bibliotecă care oferă pentru grafuri în Haskell. Este folosită, de exemplu, în — o bibliotecă a companiei Github, care construiește arbori semantici, grafuri de apeluri și dependențe și le poate compara. Proiectul meu a avut ca scop adăugarea unei reprezentări tip-secure pentru grafurile bipartite și algoritmi pentru această reprezentare.
În acest post, voi povesti despre implementarea algoritmului de verificare a bipartiției grafurilor în Haskell. Deși algoritmul este unul dintre cele mai de bază, implementarea sa frumoasă în stil funcțional a necesitat mai multe iterații și a necesitat o muncă considerabilă. Ca rezultat, m-am oprit la o implementare cu transformatoare monade.
Despre mine
Numele meu este Vasilie Alfiov, sunt student în anul patru la Universitatea Piter din St. Petersburg. Anterior, în blogul meu, am scris și . În prezent, mă află în stagiu la din Norvegia, unde mă ocup cu abordări pentru problema . Domeniile mele de interes includ algoritmi parametrizați și programare funcțională.
Despre implementarea algoritmului
Prefață
Studenților care participă la program li se recomandă insistent să întrețină un blog. Pentru blogul meu, mi s-a oferit o platformă . Acest articol este o traducere , pe care am scris-o acolo în iulie în limba engleză, cu o scurtă introducere.
Pull Request cu codul despre care se discută poate fi găsit .
Despre rezultatele muncii mele, se poate citi (în engleză) .
Postarea presupune că cititorul are cunoștințe de bază în programarea funcțională, deși voi încerca să reamintesc toate termenii utilizați atunci când va veni timpul.
Verificarea grafurilor pentru bipartiție
Algoritmul de verificare a bipartitității unui graf este de obicei prezentat în cursurile de algoritmi ca unul dintre cele mai simple algoritme grafice. Ideea sa este directă: mai întâi, distribuim în vreun fel nodurile în partea stângă sau dreaptă, iar când descoperim o margine conflictuală, afirmăm că graful nu este bipartit.
Un pic mai detaliat: mai întâi, plasăm un nod în partea stângă. Este evident că toți vecinii acestui nod trebuie să fie în partea dreaptă. Apoi, toți vecinii vecinilor acestui nod trebuie să se afle în partea stângă și așa mai departe. Continuăm să atribuim nodurilor o parte până când în componenta de conectivitate a nodului cu care am început, mai există noduri cărora nu le-am atribuit vecini. Apoi, repetăm această acțiune pentru toate componentele de conectivitate.
Dacă există o margine între nodurile ajunse în aceeași parte, nu este greu să găsim un ciclu impar în graf, ceea ce este, după cum se știe, imposibil într-un graf bipartit. În caz contrar, avem o împărțire corectă în părți, ceea ce înseamnă că graful este bipartit.
De regulă, acest algoritm este implementat folosind sau . În limbajele imperative, se utilizează de obicei căutarea în adâncime, deoarece este puțin mai simplă și nu necesită structuri de date suplimentare. De asemenea, am ales căutarea în adâncime ca fiind mai tradițională.
Astfel, am ajuns la următorul schema. Traversăm nodurile graf-ului folosind căutarea în adâncime și le atribuim părți, schimbând numărul părții atunci când ne deplasăm pe o margine. Dacă încercăm să atribuim o parte unui nod care are deja o parte atribuită, putem afirma cu încredere că graful nu este bipartit. În momentul în care tuturor nodurilor le-a fost atribuită o parte și am verificat toate marginile, avem o împărțire bună.
Purețea calculului
În Haskell presupunem că toate calculele sunt pure. Totuși, dacă chiar ar fi așa, nu am avea posibilitatea de a tipări nimic pe ecran. În general, calculările sunt atât de leneșe încât nu există nicio motivare pură pentru a efectua calcule. Toate calculele care au loc în program sunt, într-un fel sau altul, forțate în monada "nepură" IO.
Monadele sunt un mod de a reprezenta calcule cu efecte în Haskell. Explicația despre cum funcționează acestea depășește acest articol. O descriere bună și clară poate fi citită în engleză .
Aici vreau să menționez că, deși unele monade, precum IO, sunt implementate prin magia compilatorului, aproape toate celelalte sunt implementate programatic și toate calculele din acestea sunt pure.
Există foarte multe efecte și fiecare are propria monadă. Aceasta este o teorie foarte puternică și frumoasă: toate monadele implementează aceeași interfață. Vom discuta despre următoarele trei monade:
- Either e a — un calcul care returnează o valoare de tip a sau aruncă o excepție de tip e. Comportamentul acestei monade este foarte similar cu cel al excepțiilor în limbile imperative: erorile pot fi capturate sau transmise mai departe. Principala diferență este că monada este complet implementată logic în biblioteca standard în același Haskell, în timp ce în limbile imperative, de obicei, se folosesc mecanismele sistemului de operare.
- State s a — un calcul care returnează o valoare de tip a și are acces la un stat modificabil de tip s.
- Maybe a. Monada Maybe exprimă un calcul care poate fi oricând întrerupt prin returnarea lui Nothing. Cu toate acestea, vom discuta despre implementarea clasei MonadPlus pentru tipul Maybe, care exprimă efectul opus: acesta este un calcul care poate fi oricând întrerupt prin returnarea unei valori concrete.
Implementarea algoritmului
Avem două tipuri de date, Graph a și Bigraph a b, primul dintre acestea reprezentând grafuri cu vârfuri etichetate cu valori de tip a, iar al doilea reprezentând grafuri bipartite cu vârfuri pe partea stângă etichetate cu valori de tip a și vârfuri pe partea dreaptă etichetate cu valori de tip b.
Acestea nu sunt tipuri din biblioteca Alga. În Alga nu există o reprezentare pentru grafuri bipartite neorientate. Am făcut tipurile astfel pentru a fi mai clare.
De asemenea, vom avea nevoie de funcții auxiliare cu următoarele semnaturi:
-- Lista vecinilor acestui vârf.
neighbours :: Ord a => a -> Graph a -> [a]
-- Construiește un graf bipartit din graful și funcția pentru fiecare vârf
-- care returnează partea sa și marcajul din noua parte, ignorând muchiile conflictuale.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Lista vârfurilor din grafic
vertexList :: Ord a => Graph a -> [a]
Semnătura funcției pe care o vom scrie arată astfel:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Nu este greu de observat că, dacă în timpul căutării în adâncime am găsit o muchie conflictuală, ciclul impar se află în vârful stivei de recursie. Prin urmare, pentru a-l recupera, trebuie să tăiem din stiva de recursie totul până la prima apariție a ultimei vârf.
Vom implementa căutarea în adâncime, menținând un array asociativ cu numerele părților pentru fiecare vârf. Stiva de recursie va fi susținută automat prin implementarea clasei Functor a monadei alese de noi: va trebui doar să adăugăm toate vârfurile de pe drum în rezultatul returnat din funcția recursivă.
Prima mea idee a fost să folosesc monada Either, care pare să implementze exact acele efecte de care avem nevoie. Prima implementare pe care am scris-o era foarte aproape de această variantă. De fapt, am avut cinci implementări diferite într-un anumit moment, iar în final m-am oprit la altă variantă.
În primul rând, trebuie să menținem un array asociativ cu identificatorii părților — este ceva legat de State. În al doilea rând, trebuie să putem opri în cazul în care se descoperă un conflict. Acesta poate fi fie Monad pentru Either, fie MonadPlus pentru Maybe. Principala diferență este că Either poate returna o valoare în cazul în care calculul nu a fost oprit, iar Maybe returnează în acest caz doar informația despre aceasta. Deoarece nu avem nevoie de o valoare separată în cazul succesului (aceasta este deja stocată în State), alegem Maybe. Iar în momentul în care trebuie să combinăm efectele a două monade, apar , care exact acestea combină efectele.
De ce am ales un tip atât de complex? Două motive. În primul rând, implementarea devine foarte asemănătoare cu cea imperativă. În al doilea rând, trebuie să manipulăm valoarea returnată în caz de conflict, atunci când revenim din recursie pentru a restabili ciclul impar, iar acest lucru este mult mai simplu de realizat în monada Maybe.
Astfel, obținem o astfel de 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 a -> PartMonad a
onEdge p v = do m 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 [a]
oddCycle c = tail (dropWhile ((/=) last c) c)
Blocul where este nucleul algoritmului. Voi încerca să explic ce se întâmplă în interiorul lui.
- inVertex este partea căutării în adâncime, în care vizităm un vârf pentru prima dată. Aici atribuim vârfului un număr de partajare și lansăm onEdge pentru toți vecinii. De asemenea, acesta este locul unde restaurăm stiva de apeluri: dacă msum returnează o valoare, atârnăm acolo vârful v.
- onEdge este partea în care vizităm o margine. Se apelează 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 a fost. Dacă a fost vizitat, verificăm dacă marginea este conflictuală. Dacă este, returnăm valoarea — vârful cel mai de sus al stivei de recurs, unde apoi se vor atașa toate celelalte vârfuri la întoarcere.
- processVertex verifică dacă fiecare vârf a fost vizitat și pornește inVertex pe el dacă nu a fost.
- dfs pornește processVertex pe toate vârfurile.
Asta e tot.
Istoria cuvântului INLINE
Cuvântul INLINE nu a existat în prima implementare a algoritmului, a apărut mai târziu. Când am încercat să găsesc o implementare mai bună, am descoperit că pe unele grafuri versiunea fără INLINE funcționează semnificativ mai lent. Având în vedere că semantic vorbind funcțiile ar trebui să funcționeze la fel, m-a surprins foarte mult. Și mai ciudat, pe o altă mașină cu o altă versiune GHC nu a fost vizibilă nicio diferență.
După ce am petrecut o săptămână citind ieșirea GHC Core, am reușit să repar problema cu o singură linie de cod cu INLINE explicit. Într-un moment dat între GHC 8.4.4 și GHC 8.6.5, optimizatorul a încetat să facă asta de unul singur.
Nu m-am așteptat să întâlnesc atât de multă mizerie în programarea în Haskell. Totuși, optimizatorii chiar și în zilele noastre mai fac din când în când greșeli, iar a le oferi sugestii este sarcina noastră. De exemplu, aici știm că funcția ar trebui să fie inlined, deoarece este inlined în versiunea imperativă, și acesta este un motiv pentru a oferi compilatorului o sugestie.
Ce s-a întâmplat mai departe?
Mai departe, am implementat algoritmul Hopcroft-Karp deja cu alte monade, iar programul s-a încheiat aici.
Datorită Google Summer of Code, am dobândit experiență practică în programarea funcțională, care nu numai că m-a ajutat să trec la un stagiu la Jane Street vara următoare (nu sunt sigur cât de cunoscut este acest loc chiar și printre cei care cunosc Hub, dar este unul dintre puținele locuri unde poți să te ocupi de programarea funcțională vara), dar mi-a deschis și ușa către o lume uimitoare a aplicării acestei paradigme în practică, semnificativ diferită de experiența mea în limbajele tradiționale.
Sursa: habr.com
