Prošlog ljeta sam učestvovao - program za studente iz Google-a. Svake godine organizatori biraju nekoliko projekata otvorenog koda, uključujući i takve poznate organizacije kao što su и . Google poziva studente iz cijelog svijeta da rade na ovim projektima.
Kao učesnik Google Summer of Code 2019, uradio sam projekat u okviru biblioteke sa organizacijom , koji razvija jezik Haskell - jedan od najpoznatijih funkcionalnih programskih jezika. Alga je biblioteka koja predstavlja reprezentacija za grafove u Haskell-u. Koristi se, na primjer, u — Github biblioteka koja gradi semantička stabla, grafove poziva i zavisnosti na osnovu koda i može ih porediti. Moj projekat je bio da dodam tip-sigurnu reprezentaciju za bipartitne grafove i algoritme za tu reprezentaciju.
U ovom postu ću govoriti o svojoj implementaciji algoritma za provjeru bipartitnosti grafa u Haskellu. Iako je algoritam jedan od najosnovnijih, njegova lijepa implementacija u funkcionalnom stilu mi je oduzela nekoliko iteracija i zahtijevala je dosta posla. Kao rezultat toga, odlučio sam se na implementaciji s monadnim transformatorima.
O meni
Moje ime je Vasilij Alferov, student sam četvrte godine HSE-a u Sankt Peterburgu. Ranije u blogu sam pisao и . Trenutno sam na praksi u u Norveškoj, gdje radim na pristupima problemu . Moja interesovanja uključuju parametrizirane algoritme i funkcionalno programiranje.
O implementaciji algoritma
Predgovor
Studenti koji učestvuju u programu se snažno ohrabruju da vode blog. Dali su mi platformu za blog . Ovaj članak je prijevod , koju sam tamo napisao u julu na engleskom, sa kratkim predgovorom.
Zahtjev za povlačenje sa dotičnim kodom može se pronaći .
O rezultatima mog rada možete pročitati (na engleskom) .
Ovaj post ima za cilj da upozna čitaoca sa osnovnim konceptima u funkcionalnom programiranju, iako ću pokušati da se prisetim svih termina koji se koriste kada dođe vreme.
Provjera grafova na bipartitnost
Algoritam za provjeru grafa na bipartitnost se obično daje u kursu o algoritmima kao jedan od najjednostavnijih algoritama grafa. Njegova ideja je jednostavna: prvo nekako stavimo vrhove u lijevu ili desnu dionicu, a kada se pronađe konfliktna ivica, tvrdimo da graf nije bipartitan.
Malo detaljnije: prvo stavljamo neki vrh u lijevi dio. Očigledno, svi susjedi ovog vrha moraju ležati u desnom režnju. Nadalje, svi susjedi susjeda ovog vrha moraju ležati u lijevom režnju, i tako dalje. Nastavljamo sa dodjeljivanjem udjela vrhovima sve dok još uvijek postoje vrhovi u povezanoj komponenti vrha s kojim smo započeli, a kojima nismo dodijelili susjede. Zatim ponavljamo ovu radnju za sve povezane komponente.
Ako postoji ivica između vrhova koji spadaju u istu particiju, nije teško pronaći neparan ciklus u grafu, što je široko poznato (i sasvim očigledno) nemoguće u bipartitnom grafu. Inače, imamo ispravnu particiju, što znači da je graf bipartitan.
Obično se ovaj algoritam implementira pomoću ili . U imperativnim jezicima obično se koristi pretraga u dubinu jer je nešto jednostavnija i ne zahtijeva dodatne strukture podataka. Također sam odabrao pretragu u dubinu jer je tradicionalnije.
Tako smo došli do sljedeće šeme. Prelazimo vrhove grafa koristeći pretragu u dubinu i dodjeljujemo im dionice, mijenjajući broj udjela dok se krećemo duž ivice. Ako pokušamo da dodijelimo udio vrhu kojem je već dodijeljen udio, možemo sa sigurnošću reći da graf nije bipartitan. U trenutku kada je svim vrhovima dodijeljen udio i kada smo pogledali sve ivice, imamo dobru particiju.
Čistoća proračuna
U Haskell-u pretpostavljamo da su svi proračuni jesu cisto. Međutim, da je to zaista tako, ne bismo imali načina da bilo šta ispišemo na ekranu. Uopšte, čist proračuni su toliko lijeni da ih nema cisto razlozi da se nešto izračuna. Svi proračuni koji se dešavaju u programu su na neki način prisiljeni "nečisti" monada IO.
Monade su način predstavljanja proračuna efekti Haskell. Objašnjavanje načina na koji rade je izvan okvira ovog posta. Dobar i jasan opis može se pročitati na engleskom .
Ovdje želim da istaknem da dok se neke monade, kao što je IO, implementiraju putem magije kompajlera, skoro sve ostale su implementirane u softveru i svi proračuni u njima su čisti.
Ima mnogo efekata i svaki ima svoju monadu. Ovo je vrlo jaka i lijepa teorija: sve monade implementiraju isto sučelje. Govorit ćemo o sljedeće tri monade:
- Ili ea je izračun koji vraća vrijednost tipa a ili izbacuje izuzetak tipa e. Ponašanje ove monade je vrlo slično rukovanju izuzetcima u imperativnim jezicima: greške se mogu uhvatiti ili prenijeti dalje. Glavna razlika je u tome što je monada potpuno logično implementirana u standardnu biblioteku u Haskell-u, dok imperativni jezici obično koriste mehanizme operativnog sistema.
- Stanje sa je proračun koji vraća vrijednost tipa a i ima pristup promjenjivom stanju tipa s.
- Možda a. Monada Maybe izražava izračunavanje koje se može prekinuti u bilo kojem trenutku vraćanjem Ništa. Međutim, govorićemo o implementaciji MonadPlus klase za tip Maybe, koji izražava suprotan efekat: to je proračun koji se može prekinuti u bilo kom trenutku vraćanjem određene vrednosti.
Implementacija algoritma
Imamo dva tipa podataka, Graf a i Bigraf ab, od kojih prvi predstavlja grafove sa vrhovima označenim vrijednostima tipa a, a drugi predstavlja bipartitne grafove sa vrhovima s lijeve strane označenim vrijednostima tipa a i desno -bočni vrhovi označeni vrijednostima tipa b.
Ovo nisu tipovi iz biblioteke Alga. Alga nema reprezentaciju za neusmjerene bipartitne grafove. Napravio sam ovakve tipove radi jasnoće.
Također će nam trebati pomoćne funkcije sa sljedećim potpisima:
-- Список соседей данной вершины.
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)Lako je vidjeti da ako smo tokom pretrage u dubinu pronašli konfliktnu ivicu, neparni ciklus leži na vrhu rekurzivnog steka. Stoga, da bismo ga vratili, moramo odrezati sve od rekurzivnog steka do prvog pojavljivanja posljednjeg vrha.
Implementiramo pretragu u dubinu tako što održavamo asocijativni niz brojeva dionica za svaki vrh. Rekurzivni stog će se automatski održavati kroz implementaciju Functor klase monade koju smo odabrali: trebat ćemo samo staviti sve vrhove sa putanje u rezultat vraćen iz rekurzivne funkcije.
Moja prva ideja je bila da koristim monadu Either, koja izgleda implementira upravo one efekte koji su nam potrebni. Prva implementacija koju sam napisao bila je vrlo bliska ovoj opciji. U stvari, imao sam pet različitih implementacija u jednom trenutku i na kraju sam se odlučio na drugu.
Prvo, moramo održavati asocijativni niz identifikatora dionica - ovo je nešto o državi. Drugo, moramo biti u stanju zaustaviti se kada se otkrije konflikt. Ovo može biti ili Monad za Ili, ili MonadPlus za Možda. Glavna razlika je u tome što Either može vratiti vrijednost ako izračunavanje nije zaustavljeno, a Maybe vraća samo informacije o tome u ovom slučaju. Pošto nam nije potrebna posebna vrijednost za uspjeh (već je pohranjena u State), biramo Možda. I u trenutku kada trebamo spojiti efekte dvije monade, oni izlaze , koji precizno kombinuju ove efekte.
Zašto sam izabrao tako složen tip? Dva razloga. Prvo, pokazalo se da je implementacija vrlo slična imperativu. Drugo, moramo da manipulišemo povratnom vrednošću u slučaju konflikta kada se vraćamo iz rekurzije da bismo vratili neparnu petlju, što je mnogo lakše uraditi u monadi Maybe.
Tako dobijamo ovu implementaciju.
{-# 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)
Gdje je blok jezgro algoritma. Pokušaću da objasnim šta se dešava u njemu.
- inVertex je dio pretrage u dubinu gdje prvi put posjećujemo vrh. Ovdje dodjeljujemo broj dionice vrhu i pokrećemo onEdge na svim susjedima. Ovo je također mjesto gdje vraćamo stek poziva: ako je msum vratio vrijednost, guramo vrh v tamo.
- onEdge je dio gdje posjećujemo rub. Poziva se dvaput za svaku ivicu. Ovdje provjeravamo da li je vrh na drugoj strani posjećen, a ako nije posjećen. Ako se posjeti, provjeravamo da li je rub u sukobu. Ako jeste, vraćamo vrijednost - sam vrh rekurzivnog steka, gdje će svi ostali vrhovi biti smješteni nakon povratka.
- processVertex provjerava za svaki vrh da li je posjećen i pokreće inVertex na njemu ako nije.
- dfs pokreće processVertex na svim vrhovima.
To je sve.
Istorija riječi INLINE
Riječ INLINE nije bila u prvoj implementaciji algoritma; pojavila se kasnije. Kada sam pokušao pronaći bolju implementaciju, otkrio sam da je verzija koja nije INLINE bila primjetno sporija na nekim grafovima. S obzirom da bi semantički funkcije trebale raditi isto, ovo me je jako iznenadilo. Što je još čudnije, na drugoj mašini sa drugom verzijom GHC-a nije bilo primjetne razlike.
Nakon što sam nedelju dana proveo čitajući GHC Core izlaz, uspeo sam da rešim problem sa jednom linijom eksplicitnog INLINE. U nekom trenutku između GHC 8.4.4 i GHC 8.6.5 optimizator je prestao da to radi sam.
Nisam očekivao da ću naići na takvu prljavštinu u Haskell programiranju. Međutim, čak i danas optimizatori ponekad griješe, a naš je posao da im damo savjete. Na primjer, ovdje znamo da funkcija treba biti umetnuta jer je umetnuta u imperativnoj verziji, a to je razlog da kompajleru damo nagovještaj.
Šta se desilo sledeće?
Zatim sam implementirao Hopcroft-Karp algoritam sa drugim monadama i to je bio kraj programa.
Zahvaljujući Google Summer of Code, stekao sam praktično iskustvo u funkcionalnom programiranju, što mi je pomoglo ne samo da dobijem praksu u Jane Street sljedećeg ljeta (nisam siguran koliko je ovo mjesto poznato čak i među upućenoj publici Habra, ali je jedno od rijetkih gdje se možete ljeti baviti funkcionalnim programiranjem), ali me i uveo u čudesan svijet primjene ove paradigme u praksi, bitno drugačiji od mog iskustva u tradicionalnim jezicima.
izvor: www.habr.com