Minulého léta jsem se účastnil programu pro studenty od společnosti Google. Každoročně organizátoři vybírají několik Open Source projektů, včetně tak známých organizací, jako jsou a . Pro práci na těchto projektech Google oslovuje studenty z celého světa.
Jako účastník Google Summer of Code 2019 jsem realizoval projekt v rámci knihovny s organizací , která se zabývá rozvojem jazyka Haskell – jednoho z nejznámějších funkcionálních programovacích jazyků. Alga – knihovna představující zobrazení grafů v Haskellu. Používá se například v , knihovně od společnosti Github, která na základě kódu vytváří sémantické stromy, volací grafy a grafy závislostí a umí je porovnávat. Můj projekt spočíval v přidání typově bezpečného zobrazení pro bipartitní grafy a algoritmů pro toto zobrazení.
V tomto příspěvku se podělím o svou implementaci algoritmu pro ověřování bipartitnosti grafu v Haskellu. I když je algoritmus jedním z nejzákladnějších, jeho krásná implementace v funkcionálním stylu mi zabrala několik iterací a vyžadovala docela hodně práce. Výsledkem je, že jsem se rozhodl pro implementaci s monádovými transformátory.
O mně
Jmenuji se Vasily Alfjоров, jsem student čtvrtého ročníku na Vysoké škole ekonomické v Petrohradě. Dříve jsem na blogu psal a . Právě teď jsem na stáži na v Norsku, kde se zabývám přístupy k úloze . Mezi mé zájmy patří parametrizované algoritmy a funkcionální programování.
O implementaci algoritmu
Úvod
Účastníkům programu se důrazně doporučuje vést blog. Pro svůj blog jsem dostal platformu . Tento článek je překlad , který jsem tam napsal v červenci v angličtině, s malým úvodem.
Pull Request s kódem, o kterém se hovoří, lze nalézt .
O výsledcích mé práce si můžete přečíst (v angličtině) .
Příspěvek předpokládá, že čtenář má základní znalosti o funkcionálním programování, i když se pokusím připomenout všechny používané termíny, když přijde jejich čas.
Ověření bipartitnosti grafů
Algoritmus ověřování bipartitnosti grafu je obvykle považován za jeden z nejjednodušších grafových algoritmů. Jeho myšlenka je přímočará: nejprve nějakým způsobem umístíme vrcholy do levé nebo pravé množiny, a při zjištění konfliktní hrany tvrdíme, že graf není bipartitní.
Trochu podrobněji: nejprve umístíme nějaký vrchol do levé množiny. Je jasné, že všichni sousedé tohoto vrcholu by měli být v pravé množině. Dále všichni sousedé sousedů tohoto vrcholu by měli být v levé množině a tak dále. Pokračujeme v přiřazování vrcholům množin, dokud v komponentě spojení vrcholu, se kterým jsme začali, ještě existují vrcholy, kterým jsme nepřiřadili sousedy. Poté tento proces opakujeme pro všechny komponenty spojení.
Pokud existuje hrana mezi vrcholy, které se dostaly do stejné množiny, není obtížné najít v grafu lichý cyklus, což je, jak je široce známo (a dost zřejmé), nemožné v bipartitním grafu. Jinak máme správné rozdělení na množiny, a tedy graf je bipartitní.
Obvykle je tento algoritmus implementován pomocí nebo . V imperativních jazycích se obvykle používá prohledávání do hloubky, které je trochu jednodušší a nevyžaduje dodatečné datové struktury. Také jsem zvolil prohledávání do hloubky jako tradičnější.
Tak jsme dospěli k následující schémě. Procházení vrcholů grafu provádíme pomocí prohledávání do hloubky a přiřazujeme jim množiny, přičemž měníme číslo množiny při přechodu po hraně. Pokud se pokusíme přiřadit množinu vrcholu, který již má přiřazenou množinu, můžeme s jistotou říct, že graf není bipartitní. V okamžiku, kdy jsou všem vrcholům přiřazeny množiny a prohlédli jsme všechny hrany, máme dobré rozdělení.
Čistota výpočtů
V Haskellu předpokládáme, že všechny výpočty jsou čisté. Pokud by tomu tak skutečně bylo, nemohli bychom nic vytisknout na obrazovku. V podstatě, čisté výpočty jsou tak lenivé, že neexistuje žádný čistý důvod něco počítat. Všechny výpočty, které se v programu provádějí, jsou nějakým způsobem vyvolávány v ''nečisté'' monádě IO.
Monády jsou způsobem, jak reprezentovat výpočty s efekty ve Haskellu. Vysvětlení, jak fungují, přesahuje rámec tohoto příspěvku. Dobré a srozumitelné vysvětlení lze nalézt v angličtině. .
Zde bych chtěl poznamenat, že zatímco některé monády, jako je IO, jsou realizovány pomocí magie kompilátoru, téměř všechny ostatní jsou implementovány programově a všechny výpočty v nich jsou čisté.
Existuje mnoho efektů a pro každý z nich existuje vlastní monáda. To je velmi silná a krásná teorie: všechny monády implementují stejn interface. Budeme hovořit o následujících třech monádách:
- Either e a — výpočet, který vrací hodnotu typu a nebo vyhazuje výjimku typu e. Chování této monády je velmi podobné práci s výjimkami v imperativních jazycích: chyby mohou být zachyceny nebo předány dále. Hlavní rozdíl je v tom, že monáda je zcela logicky implementována ve standardní knihovně na tom samém Haskellu, zatímco v imperativních jazycích se obvykle používají mechanismy operačního systému.
- State s a — výpočet, který vrací hodnotu typu a a má přístup k mutable stavu typu s.
- Maybe a. Monáda Maybe vyjadřuje výpočet, který může být kdykoli přerušen vrácením Nothing. Nicméně budeme hovořit o implementaci třídy MonadPlus pro typ Maybe, vyjadřující opačný efekt: to je výpočet, který může být kdykoli přerušen vrácením konkrétní hodnoty.
Implementace algoritmu
Máme dva typy dat, Graph a a Bigraph a b, přičemž první z nich představuje grafy s vrcholy označenými hodnotami typu a a druhý představuje bipartitní grafy s vrcholy levé části označenými hodnotami typu a a vrcholy pravé části označenými hodnotami typu b.
To nejsou typy z knihovny Alga. V Alga neexistuje reprezentace pro neorientované bipartitní grafy. Typy jsem vytvořil takto pro přehlednost.
Také budeme potřebovat pomocné funkce s následujícími signaturami:
-- Seznam sousedů tohoto vrcholu.
neighbours :: Ord a => a -> Graph a -> [a]
-- Vytvořit bipartitní graf na základě grafu a funkce, která pro každý vrchol
-- vrací jeho část a označení v nové části, přičemž ignoruje konfliktní hrany.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Seznam vrcholů v grafu
vertexList :: Ord a => Graph a -> [a]
Podpis funkce, kterou budeme psát, vypadá takto:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Není těžké si všimnout, že pokud během prohledávání do hloubky najdeme konfliktní hranu, neparitní cyklus leží na vrcholu zásobníku rekurze. Proto, abychom jej obnovili, musíme odstranit ze zásobníku rekurze vše až k prvnímu výskytu posledního vrcholu.
Implementujeme prohledávání do hloubky, přičemž udržujeme asociativní pole čísel částí pro každý vrchol. Zásobník rekurze bude automaticky udržován prostřednictvím implementace třídy Functor zvolené monády: stačí ukládat všechny vrcholy na cestě do výsledku, který je vrácen z rekurzivní funkce.
Mou první myšlenkou bylo použít monádu Either, která jakoby implementuje přesně ty efekty, které potřebujeme. První implementace, kterou jsem napsal, byla velmi blízko této variantě. Ve skutečnosti jsem měl v určitém okamžiku pět různých implementací a nakonec jsem se zastavil u jiné.
Za prvé, musíme udržovat asociativní pole identifikátorů částí — to je něco o stavu. Za druhé, musíme umět zastavit v případě, že dojde ke konfliktu. To může být buď Monad pro Either, nebo MonadPlus pro Maybe. Hlavní rozdíl je v tom, že Either může vracet hodnotu, pokud výpočet nebyl zastaven, zatímco Maybe v takovém případě vrací jen informaci o tom. Protože nepotřebujeme samostatnou hodnotu v případě úspěchu (ta je již uložena ve Stavu), vybíráme Maybe. A v momentě, kdy musíme kombinovat efekty dvou monád, objeví se , které právě tyto efekty kombinují.
Proč jsem zvolil tak složitý typ? D два důvody. Za prvé, realizace je velmi podobná imperativní. Za druhé, musíme manipulovat s hodnotou, která se vrací v případě konfliktu, při návratu z rekurze k obnově nechtěného cyklu, což je mnohem jednodušší provádět v monádě Maybe.
Tímto způsobem dostáváme tuto realizaci.
{-# 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)
Blok where je jádrem algoritmu. Pokusím se vysvětlit, co se uvnitř něj děje.
- inVertex je část hledání do hloubky, kde navštěvujeme vrchol poprvé. Zde přiřazujeme vrcholu číslo dílu a spouštíme onEdge pro všechny sousedy. Také je to místo, kde obnovujeme zásobník volání: pokud msum vrátil hodnotu, přidáváme tam vrchol v.
- onEdge — to je část, ve které navštěvujeme hranu. Volá se dvakrát pro každou hranu. Zde kontrolujeme, zda byla vrchol na druhé straně navštíven, a navštívíme ho, pokud ne. Pokud byla navštívena, zkontrolujeme, zda je hrana konfliktní. Pokud ano, vrátíme hodnotu — samotný vrchol zásobníku rekurze, na který se při návratu navěsí všechny ostatní vrcholy.
- processVertex kontroluje pro každý vrchol, zda byl navštíven, a spouští na něm inVertex, pokud ne.
- dfs spouští processVertex na všech vrcholech.
To je vše.
Historie slova INLINE
Slovo INLINE nebylo v první implementaci algoritmu, objevilo se později. Když jsem se snažil najít lepší implementaci, zjistil jsem, že na některých grafech verze bez INLINE pracuje znatelně pomaleji. S ohledem na to, že semanticky by funkce měly fungovat stejně, mě to velmi překvapilo. Ještě podivnější bylo, že na jiném stroji s jinou verzí GHC nebyl žádný rozdíl patrný.
Po týdnu stráveném čtením výstupu GHC Core se mi podařilo vyřešit problém jedním řádkem s explicitním INLINE. V určitém okamžiku mezi GHC 8.4.4 a GHC 8.6.5 přestal optimalizátor toto dělat automaticky.
Nebyl jsem připraven na takovou špínu v programování v Haskellu. Přesto optimalizátory i v naší době občas dělají chyby a je naší úlohou dávat jim nápovědy. Například zde víme, že funkce by měla být inlinována, protože je inlinována v imperativní verzi, a to je důvod, proč dát kompilátoru nápovědu.
Co se stalo dál?
Dále jsem implementoval algoritmus Hopcroft-Karpa již s jinými monádami, a tím program skončil.
Díky Google Summer of Code jsem získal praktické zkušenosti v funkcionálním programování, které mi nejen pomohly dostat se na stáž v Jane Street následující léto (nejsem si jistý, jak moc je toto místo známo i mezi znalci Hubra, ale je to jedno z mála, kde se v létě můžete věnovat funkcionálnímu programování), ale také mě seznámily s úžasným světem aplikace této paradigmy v praxi, který se výrazně liší od mých zkušeností s tradičními jazyky.
Zdroj: habr.com
