Tavaly nyáron vettem részt - egy program diákoknak a Google-tól. A szervezők minden évben több nyílt forráskódú projektet választanak ki, köztük olyan neves szervezetektől, mint pl и . A Google a világ minden tájáról hív diákokat, hogy dolgozzanak ezeken a projekteken.
A Google Summer of Code 2019 résztvevőjeként egy projektet végeztem a könyvtáron belül a szervezettel , amely a Haskell nyelvet – az egyik leghíresebb funkcionális programozási nyelvet – fejleszti. Az Alga egy olyan könyvtár, amely képviseli gráfok ábrázolása Haskellben. Használják pl — egy Github-könyvtár, amely szemantikai fákat, hívási és függőségi gráfokat épít fel kód alapján, és össze tudja őket hasonlítani. A projektem az volt, hogy típusbiztos reprezentációt adjak hozzá kétoldalú gráfokhoz és algoritmusokhoz ehhez a reprezentációhoz.
Ebben a bejegyzésben egy algoritmus implementációjáról fogok beszélni a Haskell-beli gráf kétoldalúságának ellenőrzésére. Annak ellenére, hogy az algoritmus az egyik legalapvetőbb, ennek gyönyörű, funkcionális stílusban való megvalósítása több iterációt is igénybe vett, és elég sok munkát igényelt. Ennek eredményeként a monád transzformátorokkal való megvalósítás mellett döntöttem.
Magamról
A nevem Vaszilij Alferov, a Szentpétervári HSE negyedik éves hallgatója vagyok. Korábban a blogban írtam и . Jelenleg gyakorlaton vagyok itt Norvégiában, ahol a probléma megközelítésén dolgozom . Érdeklődésem a paraméterezett algoritmusok és a funkcionális programozás.
Az algoritmus megvalósításáról
Előszó
A programban részt vevő diákokat erősen bátorítjuk a blogírásra. Ők biztosítottak nekem egy platformot a bloghoz . Ez a cikk fordítás , én írtam ott júliusban angolul, rövid előszóval.
Pull Request a kérdéses kóddal megtalálható .
Munkám eredményeiről olvashattok (angol nyelven) .
Ennek a bejegyzésnek az a célja, hogy megismertesse az olvasót a funkcionális programozás alapfogalmaival, bár megpróbálom felidézni az összes használt kifejezést, ha eljön az ideje.
A grafikonok kétoldalúságának ellenőrzése
A gráf kétrészességének ellenőrzésére szolgáló algoritmust általában az algoritmusokról szóló kurzusban adnak meg, mint az egyik legegyszerűbb gráfalgoritmust. Ötlete egyértelmű: először valahogyan a bal vagy a jobb megosztásba helyezzük a csúcsokat, és ha találunk egy ütköző élt, azt állítjuk, hogy a gráf nem kétoldalú.
Egy kicsit részletesebben: először a bal oldali megosztásba helyezünk néhány csúcsot. Nyilvánvaló, hogy ennek a csúcsnak az összes szomszédjának a jobb lebenyben kell lennie. Továbbá ennek a csúcsnak a szomszédjainak minden szomszédjának a bal lebenyben kell lennie, és így tovább. Folytatjuk a megosztások hozzárendelését a csúcsokhoz mindaddig, amíg a kezdeti csúcs összekapcsolt komponensében vannak még olyan csúcsok, amelyekhez nem rendeltünk szomszédokat. Ezután megismételjük ezt a műveletet az összes csatlakoztatott összetevőre.
Ha van él az azonos partícióba eső csúcsok között, nem nehéz páratlan ciklust találni a gráfban, ami széles körben ismert (és nyilvánvalóan lehetetlen egy kétrészes gráfban). Ellenkező esetben helyes partíciónk van, ami azt jelenti, hogy a gráf kétrészes.
Ezt az algoritmust általában a segítségével valósítják meg vagy . A kötelező nyelveken általában a mélységi keresést használják, mivel ez valamivel egyszerűbb, és nem igényel további adatstruktúrákat. Én is a mélységi keresést választottam, mivel az hagyományosabb.
Így a következő sémához jutottunk. A gráf csúcsait mélységi kereséssel bejárjuk, és megosztásokat rendelünk hozzájuk, a megosztás számát változtatva, ahogy haladunk az él mentén. Ha egy olyan csúcshoz próbálunk megosztást rendelni, amelyhez már van megosztás hozzárendelve, akkor nyugodtan kijelenthetjük, hogy a gráf nem bipartit. Abban a pillanatban, amikor minden csúcshoz hozzá van rendelve egy megosztás, és megnéztük az összes élt, van egy jó partíciónk.
A számítások tisztasága
Haskellben feltételezzük, hogy minden számítás igaz tiszta. Ha azonban ez valóban így lenne, nem tudnánk semmit a képernyőre nyomtatni. Egyáltalán, tiszta olyan lusták a számítások, hogy nincs is tiszta okok számítani valamit. A programban előforduló összes számítás valamilyen módon bele van kényszerítve "tisztátalan" monád IO.
A monádok a számítások ábrázolásának módja hatások Haskellben. A működésük elmagyarázása túlmutat ennek a bejegyzésnek a keretein. Jó és érthető leírás olvasható angolul .
Itt szeretném rámutatni, hogy míg néhány monád, mint például az IO, fordítói varázslaton keresztül valósul meg, addig szinte az összes többi szoftverben van implementálva, és minden számítás tiszta.
Nagyon sok effekt létezik, és mindegyiknek megvan a maga monádja. Ez egy nagyon erős és szép elmélet: minden monád ugyanazt a felületet valósítja meg. A következő három monádról fogunk beszélni:
- Az ea egy olyan számítás, amely a típusú értéket ad vissza, vagy egy e típusú kivételt dob. Ennek a monádnak a viselkedése nagyon hasonlít az imperatív nyelvek kivételkezeléséhez: a hibákat el lehet kapni vagy továbbadni. A fő különbség az, hogy a monád teljesen logikusan van megvalósítva a Haskell szabványos könyvtárában, míg a kötelező nyelvek általában operációs rendszer mechanizmusokat használnak.
- Az sa állapot egy olyan számítás, amely a típusú értéket ad vissza, és hozzáfér az s típusú változó állapothoz.
- Talán egy. A Talán monád olyan számítást fejez ki, amely bármikor megszakítható a Semmi visszaadásával. Szó lesz azonban a Maybe típushoz tartozó MonadPlus osztály megvalósításáról, ami az ellenkező hatást fejezi ki: ez egy olyan számítás, amely egy adott érték visszaadásával bármikor megszakítható.
Az algoritmus megvalósítása
Két adattípusunk van, a Graph a és a Bigraph ab, amelyek közül az első olyan gráfokat reprezentál, amelyek csúcsai az a típusú értékekkel vannak jelölve, a második pedig kétrészes gráfokat képvisel baloldali csúcsokkal, amelyek a és jobb típusú értékekkel vannak címkézve. -b típusú értékekkel jelölt oldalcsúcsok.
Ezek nem az Alga könyvtár típusai. Az Alga nem rendelkezik irányítatlan bipartit gráfok reprezentációjával. Az érthetőség kedvéért így készítettem a típusokat.
Szükségünk lesz segédfunkciókra is a következő aláírásokkal:
-- Список соседей данной вершины.
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)Könnyen belátható, hogy ha a mélységi keresés során ütköző élt találtunk, akkor a páratlan ciklus a rekurziós verem tetején található. Így a visszaállításához mindent le kell vágnunk a rekurziós veremtől az utolsó csúcs első előfordulásáig.
A mélységi keresést úgy valósítjuk meg, hogy minden csúcshoz fenntartjuk a megosztási számok asszociatív tömbjét. A rekurziós verem automatikusan karbantartásra kerül az általunk választott monád Functor osztályának megvalósítása révén: csak az útvonal összes csúcsát kell behelyeznünk a rekurzív függvényből visszaadott eredménybe.
Az első ötletem az volt, hogy az Akár-monádot használom, amely úgy tűnik, pontosan azokat a hatásokat valósítja meg, amelyekre szükségünk van. Az első megvalósítás, amit írtam, nagyon közel állt ehhez a lehetőséghez. Valójában öt különböző megvalósításom volt egy ponton, és végül egy másik mellett döntöttem.
Először is fenn kell tartanunk a megosztási azonosítók asszociatív tömbjét – ez az állapotról szól. Másodszor, meg kell tudnunk állni, ha konfliktust észlelünk. Ez lehet a Monad az egyikhez vagy a MonadPlus a Maybe számára. A fő különbség az, hogy az Any akkor tud visszaadni egy értéket, ha a számítást nem állították le, és a Maybe ebben az esetben csak erről ad vissza információt. Mivel a sikerhez nem kell külön érték (ez már State-ben van tárolva), ezért a Maybe-t választjuk. És abban a pillanatban, amikor két monád hatását kell kombinálnunk, előjönnek , amelyek pontosan egyesítik ezeket a hatásokat.
Miért választottam egy ilyen összetett típust? Két ok. Először is, a megvalósítás nagyon hasonlít az imperatívához. Másodszor, konfliktus esetén módosítanunk kell a visszatérési értéket, amikor visszatérünk a rekurzióból, hogy visszaállítsuk a páratlan ciklust, ami sokkal könnyebb a Maybe monádban.
Így kapjuk ezt 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 <- 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)
A where blokk az algoritmus magja. Megpróbálom elmagyarázni, mi történik benne.
- Az inVertex a mélységi keresésnek az a része, ahol először látogatjuk meg a csúcsot. Itt egy megosztási számot rendelünk a csúcshoz, és az onEdge-et futtatjuk az összes szomszédon. Itt is visszaállítjuk a hívásveremet: ha az msum értéket adott vissza, akkor oda toljuk a v csúcsot.
- Az onEdge az a rész, ahol meglátogatjuk az élt. Minden élhez kétszer hívják. Itt ellenőrizzük, hogy a másik oldalon lévő csúcsot meglátogatták-e, és meglátogatjuk, ha nem. Ha meglátogatjuk, ellenőrizzük, hogy az él ütköző-e. Ha igen, akkor az értéket adjuk vissza – a rekurziós verem legtetején, ahol az összes többi csúcs visszakerül.
- A processVertex minden csúcsnál ellenőrzi, hogy meglátogatták-e, és ha nem, futtatja az inVertex-et.
- A dfs minden csúcson futtatja a processVertex-et.
Ennyi az egész.
Az INLINE szó története
Az INLINE szó nem az algoritmus első implementációjában szerepelt, később jelent meg. Amikor megpróbáltam jobb megvalósítást találni, azt tapasztaltam, hogy a nem INLINE verzió néhány grafikonon észrevehetően lassabb volt. Figyelembe véve, hogy szemantikailag a függvényeknek ugyanúgy kell működniük, ez nagyon meglepett. Még furcsább, hogy egy másik gépen a GHC más verziójával nem volt észrevehető különbség.
Miután egy hetet eltöltöttem a GHC Core kimenet olvasásával, meg tudtam oldani a problémát egy sor explicit INLINE segítségével. A GHC 8.4.4 és a GHC 8.6.5 között valamikor az optimalizáló ezt magától abbahagyta.
Nem számítottam rá, hogy ekkora szennyeződéssel találkozom a Haskell programozás során. Az optimalizálók azonban még ma is hibáznak, és a mi feladatunk, hogy tippeket adjunk nekik. Például itt tudjuk, hogy a függvényt be kell illeszteni, mert az imperatív verzióban be van írva, és ez ok arra, hogy a fordítónak tippet adjunk.
Aztán mi történt?
Aztán implementáltam a Hopcroft-Karp algoritmust más monádokkal, és ezzel véget is ért a program.
A Google Summer of Code-nak köszönhetően gyakorlati tapasztalatot szereztem a funkcionális programozás terén, ami nemcsak abban segített, hogy a következő nyáron szakmai gyakorlatot szerezzek a Jane Streeten (nem tudom, mennyire ismert ez a hely még Habr hozzáértő közönsége körében is, de ez egy azon kevesek közül, ahol nyáron funkcionális programozással foglalkozhat), hanem bevezetett e paradigma gyakorlati alkalmazásának csodálatos világába, amely jelentősen eltér a hagyományos nyelveken szerzett tapasztalataimtól.
Forrás: will.com