Loni v létě jsem se zúčastnil - program pro studenty od společnosti Google. Organizátoři každoročně vybírají několik Open Source projektů, a to i od takových známých organizací, jako je např и . Google zve studenty z celého světa, aby na těchto projektech pracovali.
Jako účastník Google Summer of Code 2019 jsem dělal projekt v rámci knihovny s organizací , která vyvíjí jazyk Haskell – jeden z nejznámějších funkcionálních programovacích jazyků. Alga je knihovna, která reprezentuje reprezentace pro grafy v Haskell. Používá se např. v — knihovna Github, která vytváří sémantické stromy, grafy volání a závislostí na základě kódu a dokáže je porovnávat. Mým projektem bylo přidat typově bezpečnou reprezentaci pro bipartitní grafy a algoritmy pro tuto reprezentaci.
V tomto příspěvku budu hovořit o mé implementaci algoritmu pro kontrolu bipartitnosti grafu v Haskell. Přestože je algoritmus jedním z nejzákladnějších, jeho implementace ve funkčním stylu mi zabrala několik iterací a vyžadovala poměrně hodně práce. V důsledku toho jsem se rozhodl pro implementaci s monádovými transformátory.
O mně
Jmenuji se Vasilij Alferov, jsem studentem čtvrtého ročníku na HSE v Petrohradě. Dříve v blogu, který jsem psal и . Momentálně jsem na stáži u v Norsku, kde pracuji na přístupech k problému . Mezi mé zájmy patří parametrizované algoritmy a funkcionální programování.
O implementaci algoritmu
předmluva
Studentům účastnícím se programu důrazně doporučujeme, aby blogovali. Poskytli mi platformu pro blog . Tento článek je překladem , kterou jsem tam napsal v červenci v angličtině, s krátkou předmluvou.
Lze nalézt žádost o vytažení s příslušným kódem .
O výsledcích mé práce si můžete přečíst (v angličtině) .
Účelem tohoto příspěvku je seznámit čtenáře se základními pojmy ve funkcionálním programování, i když se pokusím všechny použité termíny připomenout, až přijde čas.
Kontrola bipartitnosti grafů
Algoritmus pro kontrolu bipartitnosti grafu je obvykle uveden v kurzu o algoritmech jako jeden z nejjednodušších grafových algoritmů. Jeho myšlenka je přímočará: nejprve nějakým způsobem vložíme vrcholy do levého nebo pravého podílu, a když je nalezena konfliktní hrana, tvrdíme, že graf není bipartitní.
Trochu podrobněji: nejprve vložíme nějaký vrchol do levého podílu. Je zřejmé, že všichni sousedé tohoto vrcholu musí ležet v pravém laloku. Dále, všichni sousedé sousedů tohoto vrcholu musí ležet v levém laloku a tak dále. Pokračujeme v přiřazování podílů k vrcholům tak dlouho, dokud jsou v připojené komponentě vrcholu, se kterým jsme začali, ještě vrcholy, kterým jsme nepřiřadili sousedy. Tuto akci pak opakujeme pro všechny připojené komponenty.
Pokud existuje hrana mezi vrcholy, které spadají do stejného oddílu, není těžké najít v grafu lichý cyklus, což je všeobecně známé (a zcela zjevně) nemožné v bipartitním grafu. Jinak máme správné rozdělení, což znamená, že graf je bipartitní.
Obvykle je tento algoritmus implementován pomocí nebo . V imperativních jazycích se obvykle používá vyhledávání do hloubky, protože je o něco jednodušší a nevyžaduje další datové struktury. Také jsem zvolil hloubkové vyhledávání, protože je tradičnější.
Tím jsme se dostali k následujícímu schématu. Procházíme vrcholy grafu pomocí hledání do hloubky a přiřazujeme jim podíly, přičemž při pohybu podél okraje měníme číslo podílu. Pokud se pokusíme přiřadit podíl k vrcholu, který již má podíl přiřazený, můžeme s klidem říci, že graf není bipartitní. Ve chvíli, kdy je všem vrcholům přiřazen podíl a my jsme se podívali na všechny hrany, máme dobrý oddíl.
Čistota výpočtů
V Haskellu předpokládáme, že všechny výpočty jsou čistý. Pokud by to však skutečně tak bylo, neměli bychom žádnou možnost vytisknout na obrazovku nic. Vůbec, čistý výpočty jsou tak líné, že neexistuje ani jeden čistý důvody, proč něco vypočítat. Všechny výpočty vyskytující se v programu jsou nějak vynuceny "nečistý" monad IO.
Monády představují způsob, jak reprezentovat výpočty efekty v Haskellu. Vysvětlení, jak fungují, je nad rámec tohoto příspěvku. Dobrý a jasný popis lze číst v angličtině .
Zde chci upozornit na to, že zatímco některé monády, jako je IO, jsou implementovány pomocí kompilátorové magie, téměř všechny ostatní jsou implementovány softwarově a všechny výpočty v nich jsou čisté.
Efektů je spousta a každý má svou vlastní monádu. Toto je velmi silná a krásná teorie: všechny monády implementují stejné rozhraní. Budeme mluvit o následujících třech monádách:
- Buď je ea výpočet, který vrací hodnotu typu a, nebo vyvolá výjimku typu e. Chování této monády je velmi podobné zpracování výjimek v imperativních jazycích: chyby lze zachytit nebo předat dál. Hlavním rozdílem je, že monáda je zcela logicky implementována ve standardní knihovně v Haskellu, zatímco imperativní jazyky obvykle používají mechanismy operačního systému.
- Stav sa je výpočet, který vrací hodnotu typu a a má přístup k proměnlivému stavu typu s.
- Možná a. Možná monáda vyjadřuje výpočet, který lze kdykoli přerušit vrácením Nothing. Budeme však mluvit o implementaci třídy MonadPlus pro typ Maybe, která vyjadřuje opačný efekt: jde o výpočet, který lze kdykoli přerušit vrácením konkrétní hodnoty.
Implementace algoritmu
Máme dva datové typy, Graph a a Bigraph ab, z nichž první představuje grafy s vrcholy označenými hodnotami typu a a druhý představuje bipartitní grafy s levostrannými vrcholy označenými hodnotami typu a a vpravo. -postranní vrcholy označené hodnotami typu b.
Nejedná se o typy z knihovny Alga. Alga nemá zastoupení pro neorientované bipartitní grafy. Pro přehlednost jsem udělal takové typy.
Budeme také potřebovat pomocné funkce s následujícími podpisy:
-- Список соседей данной вершины.
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)Je snadné vidět, že pokud během hloubkového hledání najdeme konfliktní hranu, lichý cyklus leží na vrcholu rekurzního zásobníku. Abychom jej obnovili, musíme odříznout vše od zásobníku rekurze až po první výskyt posledního vrcholu.
Implementujeme hloubkové vyhledávání udržováním asociativního pole čísel sdílení pro každý vrchol. Zásobník rekurze bude automaticky udržován prostřednictvím implementace třídy Functor monády, kterou jsme si vybrali: budeme muset pouze vložit všechny vrcholy z cesty do výsledku vráceného rekurzivní funkcí.
Můj první nápad byl použít buď monádu, která, jak se zdá, implementuje přesně ty efekty, které potřebujeme. První implementace, kterou jsem napsal, byla této možnosti velmi blízko. Ve skutečnosti jsem měl v jednu chvíli pět různých implementací a nakonec jsem se rozhodl pro jinou.
Za prvé, musíme udržovat asociativní pole sdílených identifikátorů – to je něco o státu. Za druhé, musíme být schopni zastavit, když je zjištěn konflikt. Může to být buď Monad pro Either, nebo MonadPlus pro Možná. Hlavní rozdíl je v tom, že Buď může vrátit hodnotu, pokud výpočet nebyl zastaven, a Maybe v tomto případě vrátí pouze informace o tomto. Protože pro úspěch nepotřebujeme samostatnou hodnotu (je již uložena ve State), zvolíme Možná. A ve chvíli, kdy potřebujeme spojit účinky dvou monád, vyjdou , které přesně spojují tyto efekty.
Proč jsem si vybral tak složitý typ? Dva důvody. Za prvé, implementace se ukazuje jako velmi podobná imperativu. Za druhé, potřebujeme manipulovat s návratovou hodnotou v případě konfliktu při návratu z rekurze, abychom obnovili lichou smyčku, což je mnohem snazší udělat v Monadě Možná.
Tak dostáváme tuto implementaci.
{-# 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)
Blok kde je jádrem algoritmu. Pokusím se vysvětlit, co se v něm děje.
- inVertex je část hloubkového vyhledávání, kde poprvé navštívíme vrchol. Zde přiřadíme vertexu číslo sdílení a spustíme onEdge na všech sousedech. Zde také obnovíme zásobník volání: pokud msum vrátil hodnotu, vložíme tam vertex v.
- onEdge je část, kde navštívíme hranu. Pro každou hranu se volá dvakrát. Zde zkontrolujeme, zda byl vrchol na druhé straně navštíven, a pokud ne, navštívíme jej. Při návštěvě zkontrolujeme, zda není hrana konfliktní. Pokud je, vrátíme hodnotu – samý vrchol zásobníku rekurze, kam se pak po návratu umístí všechny ostatní vrcholy.
- processVertex pro každý vrchol zkontroluje, zda byl navštíven, a pokud ne, spustí na něm inVertex.
- dfs spustí 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 neINLINE verze byla na některých grafech znatelně pomalejší. Vzhledem k tomu, že významově by funkce měly fungovat stejně, mě to velmi překvapilo. Ještě podivnější je, že na jiném stroji s jinou verzí GHC nebyl žádný znatelný rozdíl.
Po týdnu stráveném čtením výstupu GHC Core se mi podařilo problém vyřešit pomocí jednoho řádku explicitního INLINE. V určitém okamžiku mezi GHC 8.4.4 a GHC 8.6.5 to optimalizátor přestal dělat sám od sebe.
Nečekal jsem, že se v programování Haskell setkám s takovou špínou. I dnes však optimalizátory někdy dělají chyby a je naším úkolem jim poradit. Zde například víme, že funkce by měla být vložena, protože je vložena v imperativní verzi, a to je důvod, proč dát kompilátor nápovědu.
Co se stalo pak?
Pak jsem implementoval Hopcroft-Karpův algoritmus s dalšími monádami, a to byl konec programu.
Díky Google Summer of Code jsem získal praktické zkušenosti s funkčním programováním, které mi nejen pomohly získat stáž v Jane Street následující léto (nejsem si jistý, jak známé je toto místo i mezi Habrovým znalým publikem, ale je to jedno z mála, kde se můžete v létě věnovat funkcionálnímu programování), ale také mě uvedl do úžasného světa aplikace tohoto paradigmatu v praxi, výrazně odlišného od mých zkušeností s tradičními jazyky.
Zdroj: www.habr.com