Tavaly nyáron részt vettem — a Google diákoknak szóló programjában. Évente a szervezők több Open Source projektet választanak ki, beleértve olyan ismert szervezeteket, mint és . Ezekben a projektekben a Google a világ minden tájáról hív meg diákokat.
A Google Summer of Code 2019 résztvevőjeként egy projektet készítettem az szervezet közreműködésével , amely a Haskell programozási nyelv fejlesztésével foglalkozik — az egyik legismertebb funkcionális programozási nyelv. Az Alga egy ábrázolása grafoknak Haskellben. Például használják a — a Github által készített könyvtár, amely a kódból szemantikus fákat, hívási és függőségi grafokat épít, és képes azokat összehasonlítani. Az én projektem abban állt, hogy hozzáadom a típusbiztos ábrázolást a kétoldalú grafokhoz, valamint algoritmusokat ehhez az ábrázoláshoz.
A bejegyzésben arról fogok írni, hogyan valósítottam meg a graf kétoldalúságának ellenőrzésére szolgáló algoritmust Haskellben. Bár az algoritmus az egyik legalapvetőbb, gyönyörű megvalósítása funkcionális stílusban több iterációt igényelt, és meglehetősen sok munkát igényelt. Végül a monádtansformátorokkal való megvalósításon állapodtam meg.
Rólam
A nevem Vaszilij Aljoforov, a negyedéves hallgató vagyok a Szentpétervári Egyetemen. Korábban a blogomban írtam és . Jelenleg egy gyakornoki program keretében vagyok Norvégiában, ahol a feladat megoldásaira összpontosítok . Az érdeklődési területeim közé tartozik a parametrizált algoritmusok és a funkcionális programozás.
Az algoritmus megvalósítása
Bevezető
A programban részt vevő hallgatóknak javasolt blogot vezetni. Számomra a bloghoz a platformot biztosították. Ez a cikk a júliusban angol nyelven oda írt fordítása, egy rövid bevezetővel.
A szóban forgó kód Pull Request-jét itt található .
A munkám eredményeiről angolul olvashatnak .
A bejegyzés feltételezi, hogy az olvasó ismeri a funkcionális programozás alapfogalmait, bár megpróbálom emlékeztetni az összes használt kifejezésre, amikor elérkezik az ideje.
A gráfok bipoláris jellegének ellenőrzése
A gráf bipoláris jellegének ellenőrzésére szolgáló algoritmus általában az algoritmusok kurzusában az egyik legegyszerűbb gráf algoritmusként szerepel. Az ötlet egyszerű: először valamilyen módon elhelyezzük a csúcsokat a bal vagy a jobb részbe, és amikor feszültséges élt találunk, azt állítjuk, hogy a gráf nem bipoláris.
Kicsit részletesebben: először elhelyezünk egy csúcsot a bal részbe. Nyilvánvaló, hogy ennek a csúcsnak az összes szomszédjának a jobb részben kell lennie. Továbbá, a csúcs szomszédjainak szomszédainak a bal részben kell lenniük, és így tovább. Folytatjuk a csúcsok részének kijelölését, amíg a kezdeti konzisztenciakomponensben még vannak olyan csúcsok, akiknek nem jelöltük ki a szomszédait. Ezután megismételjük ezt a lépést minden konzisztenciakomponensnél.
Ha van él a csúcsok között, amelyek ugyanabba a részbe estek, nem nehéz a gráfban páratlan kört találni, ami közismert (és elég nyilvánvaló) módon lehetetlen egy bipoláris gráfban. Ellenkező esetben helyes felosztásunk van, tehát a gráf bipoláris.
Általánosságban ezt az algoritmust a vagy segítségével valósítják meg. Az imperatív nyelvekben általában mélységi keresést használnak, amely kissé egyszerűbb és nem igényel további adatstruktúrákat. Én is a mélységi keresést választottam, mint a hagyományosabb megoldást.
Így eljutottunk a következő sémához. A gráf csúcsait mélységi kereséssel járjuk be, és részükhöz rendeljük őket, megváltoztatva a rész számát az élek mentén való áthaladáskor. Ha megpróbálunk részét kijelölni egy csúcsnak, amely már rendelkezik résszel, biztonsággal állíthatjuk, hogy a gráf nem bipoláris. Abban a pillanatban, amikor minden csúcsnak részét jelöltük ki, és megnéztük az összes élt, jó felosztással rendelkezünk.
A számítások tisztasága
Haskellben azt feltételezzük, hogy minden számítás tiszták. Ha ez valóban így lenne, nem lenne lehetőségünk semmit se kinyomtatni a képernyőre. Valójában a tiszták számítások olyan lusta, hogy nincs egyetlen tiszta oka annak, hogy bármit számítsunk. A program során végbemenő összes számítást valamilyen módon kényszerítik a »piszkos« IO monádba.
A monádák a számítások hatásokkal való reprezentálásának módját jelentik. hatásokkal Haskellban. Az, hogy hogyan működnek, túlmutat ennek a bejegyzésnek a keretein. Jó és érthető leírást olvashatunk angolul. .
Itt szeretném megjegyezni, hogy míg néhány Monad, mint az IO, a fordító varázslatával van megvalósítva, szinte minden más programozás révén, és minden számítás bennük tiszta.
Nagyon sokféle effektus létezik, és minden egyeshez saját monád tartozik. Ez egy nagyon erős és szép elmélet: az összes monád ugyanazt az interfészt valósítja meg. A következő három monádról fogunk beszélni:
- Either e a – egy olyan számítás, amely visszaadja az a típusú értéket, vagy dob egy e típusú kivételt. Ennek a monádnak a működése nagyon hasonlít a kivételekkel való munkára imperatív nyelvekben: a hibák megfoghatók vagy továbbadhatók. A fő különbség az, hogy a monád teljesen logikailag van megvalósítva a standard könyvtárban ugyanabban a Haskellben, míg imperatív nyelvekben általában az operációs rendszer mechanizmusait használják.
- State s a – egy olyan számítás, amely visszaadja az a típusú értéket és hozzáférést biztosít a s típusú módosítható állapothoz.
- Maybe a. A Maybe monád egy olyan számítást fejez ki, amely bármikor megszakítható Nothing visszaadásával. Azonban a Maybe típus MonadPlus osztályának megvalósításáról fogunk beszélni, amely ellentétes hatást fejez ki: ez egy olyan számítás, amely bármikor megszakítható egy konkrét érték visszaadásával.
Az algoritmus megvalósítása
Két adatunk van: Graph a és Bigraph a b, az első képviseli a gráfokat a csúcsokkal, amelyeket az a típusú értékek jelölnek, a második pedig a bipoláris gráfokat, ahol a bal oldali csúcsok az a típust jelölik, a jobb oldali csúcsok pedig a b típust.
Ezek nem az Alga könyvtár típusai. Az Alga nem tartalmaz reprezentációt az irányítatlan bipoláris gráfok számára. Azért készítettem el ezeket a típusokat, hogy tisztább legyen.
Továbbá szükségünk lesz segédfüggvényekre a következő aláírásokkal:
-- A csúcs szomszédainak listája.
neighbours :: Ord a => a -> Graph a -> [a]
-- Kétoldalú gráfot épít egy gráf és egy függvény alapján, amely
-- minden csúcsához megadja a részét és a megjegyzést az új részben,
-- figyelmen kívül hagyva a konfliktusos éleket.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- A gráf csúcsainak listája
vertexList :: Ord a => Graph a -> [a]
A funkció aláírása, amit írni fogunk, így néz ki:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Könnyű észrevenni, hogy ha a mélységi keresés során konfliktusos élt találunk, az páratlan ciklus a rekurziós verem tetején van. Ezért, hogy helyreállítsuk, le kell vágnunk a rekurziós veremből mindent az utolsó csúcs első előfordulásáig.
Megvalósítjuk a mélységi keresést, fenntartva egy asszociatív tömböt, amely a részek azonosítóit tartalmazza minden csúcs számára. A rekurziós verem automatikusan karbantartásra kerül a választott Monad Functor osztályának megvalósítása révén: csak annyit kell tennünk, hogy az összes csúcsot az útról a rekurzív függvényből visszaadott eredménybe helyezzük.
Első ötletem az volt, hogy az Either monádát használom, amely úgy tűnik, pontosan azokat a hatásokat valósítja meg, amelyekre szükségünk van. Az általam írt első változat nagyon közel állt ehhez a megoldáshoz. Valójában öt különböző megvalósításom volt egy időben, és végül egy másikon állapodtam meg.
Először is, szükségünk van egy asszociatív tömbre a részek azonosítóival – ez egyfajta State. Másodszor, meg kell tudnunk állni konfliktus észlelésekor. Ez lehet Either Monad, vagy MonadPlus a Maybe esetében. A fő különbség az, hogy az Either értéket tud visszaadni, ha a számítás nem állt le, míg a Maybe csak információt ad erről. Mivel siker esetén nem szükséges külön érték (az már a State-ben tárolva van), a Maybe-t választjuk. És abban a pillanatban, amikor hatások két monáda kombinálására van szükség, felbukkannak , amelyek éppen ezeket a hatásokat kombinálják.
Miért választottam ilyen bonyolult típust? Két ok van. Először is, a megvalósítás nagyon hasonlít az imperatív stílusra. Másodszor, manipulálnunk kell a konfliktus esetén visszaadott értéket, amikor visszatérünk a rekurzióból az páratlan ciklus helyreállítása érdekében, amit sokkal egyszerűbb így megtenni a Maybe monádban.
Így alakítjuk ki a megvalósítást.
{-# 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)
A where blokk az algoritmus magja. Megpróbálom elmagyarázni, hogy mi történik benne.
- Az inVertex a mélységi keresés része, ahol először látogatjuk meg a csúcsot. Itt a csúcsnak számot adunk és elindítjuk az onEdge-t minden szomszédnak. Ez az a hely, ahol helyreállítjuk a hívási veremet: ha az msum visszaadott értéket, akkor hozzáadjuk a v csúcsot.
- onEdge — ez a rész, ahol az élt látogatjuk meg. Minden élre kétszer van szükség. Itt ellenőrizzük, hogy a csúcs a másik oldalon van-e már, és ha nincs, meglátogatjuk. Ha már meglátogatva van, ellenőrizzük, hogy az él ütköző-e. Ha igen, akkor visszatérünk az értékünkkel — a rekurzió legfelső szintjére, ahová aztán visszatérve az összes többi csúcs kerül.
- A processVertex ellenőrzi, hogy minden csúcs meg van-e látogatva, és meghívja az inVertex-et, ha még nem.
- A dfs a processVertex-et hívja meg az összes csúcson.
Ennyit erről.
A INLINE szó története
A INLINE szó az algoritmus első megvalósításában nem volt jelen, később került be. Amikor a legjobb megvalósítást kerestem, észrevettem, hogy egyes gráfokon az INLINE nélküli verzió észrevehetően lassabb. Figyelembevételével, hogy a szeminálisan a funkcióknak azonosan kell működniük, ez meglepett. Még furcsább volt, hogy egy másik gépen, más GHC verzióval semmilyen különbséget nem észleltem.
Miután egy hétig olvastam a GHC Core kimenetét, egy sor explicit INLINE-nel tudtam megoldani a problémát. Valahol a GHC 8.4.4 és a GHC 8.6.5 között az optimalizáló már nem végezte el automatikusan ezt.
Nem vártam, hogy ilyen rendetlenséggel találkozom a Haskell programozásban. Az optimalizálók azonban még manapság is hibáznak, és a feladatunk, hogy javaslatokat adjunk nekik. Például itt tudjuk, hogy a funkciónak inlined-nek kell lennie, mivel az imperatív verzióban inline az, és ez okot ad a fordítónak a figyelmeztetésre.
Mi történt aztán?
Aztán megvalósítottam a Hopcroft-Karp algoritmust más monádokkal, és ezzel véget ért a program.
A Google Summer of Code segítségével gyakorlati tapasztalatot szereztem a funkcionális programozásban, amely nemcsak abban segített, hogy a következő nyáron gyakornokként bekerüljek a Jane Streethez (nem vagyok biztos benne, mennyire ismert ez a hely még a Habr tudós közönsége előtt, de az egyik kevés hely, ahol nyáron funkcionális programozással foglalkozhatunk), hanem megismertette egy sor érdekes világot, amely e paradigma gyakorlati alkalmazásáról szól, ami jelentősen eltér a hagyományos nyelvekben szerzett tapasztalatomtól.
Forrás: habr.com
