L'estate scorsa aghju participatu - un prugramma per i studienti da Google. Ogni annu, l'urganizatori selezziunate parechji prughjetti Open Source, cumpresu da l'urganisazioni cusì cunnisciute cum'è и . Google invita studienti di tuttu u mondu à travaglià nantu à sti prughjetti.
Cum'è participante in Google Summer of Code 2019, aghju fattu un prughjettu in a biblioteca cù l'urganizazione , chì sviluppa a lingua Haskell - una di e più famose lingue di prugrammazione funziunale. Alga hè una biblioteca chì rapprisenta Rappresentazione per i grafici in Haskell. Hè usatu, per esempiu, in - una libreria Github chì custruisce arburi semantici, grafii di chjama è di dependenza basatu nantu à u codice è ponu paragunà. U mo prughjettu era di aghjunghje una rapprisintazioni sicura di tipu per i grafici bipartiti è algoritmi per quella rapprisintazioni.
In questu post parraraghju di a mo implementazione di un algoritmu per verificà un graficu per a bipartitezza in Haskell. Ancu s'è l'algoritmu hè unu di i più basi, l'implementazione bella in un stile funziunale m'hà pigliatu parechje iterazioni è hà dumandatu assai travagliu. In u risultatu, aghju stabilitu nantu à una implementazione cù transformatori di monadi.
À mè stessu
Mi chjamu Vasily Alferov, sò un studiente di quartu annu in St. Petersburg HSE. Prima in u blog aghju scrittu и . Avà sò in un stage in in Norvegia, induve aghju travagliatu nantu à approcci à u prublema . I mo interessi includenu algoritmi parametrizzati è prugrammazione funziunale.
Circa l'implementazione di l'algoritmu
Prélude
I studienti chì participanu à u prugramma sò fermamente incuraghjiti à bloggu. Mi furnianu una piattaforma per u blog . Questu articulu hè una traduzzione , scrittu da mè quì in lugliu in inglese, cù una breve prefazione.
Pull Request cù u codice in quistione pò esse trovu .
Pudete leghje nantu à i risultati di u mo travagliu (in inglese) .
Questu post hè destinatu à familiarizà u lettore cù i cuncetti basi in a prugrammazione funziunale, ancu s'ellu pruvaraghju di ricurdà tutti i termini utilizati quandu u tempu vene.
Verificate i grafici per a bipartite
Un algoritmu per verificà un gràficu per a bipartitezza hè generalmente datu in un cursu nantu à l'algoritmi cum'è unu di l'algoritmi di gràficu più simplici. A so idea hè simplice: prima mettemu in qualchì modu vertici in a parte sinistra o diritta, è quandu si trova un bordu cunflittu, affirmemu chì u graficu ùn hè micca bipartitu.
Un pocu di più dettagliu: prima mettemu qualchì vertice in a parte di manca. Ovviamente, tutti i vicini di questu vertice deve esse in u lòbulu ghjustu. In più, tutti i vicini di i vicini di questu vertice deve esse in u lòbulu manca, è cusì. Continuemu à assignà azzioni à i vertici, sempre chì ci sò sempre vertici in u cumpunente cunnessu di u vertice chì avemu principiatu chì ùn avemu micca assignatu vicini. Dopu ripetemu sta azzione per tutti i cumpunenti cunnessi.
S'ellu ci hè un bordu trà i vertici chì cascanu in a listessa partizione, ùn hè micca difficiule di truvà un ciculu stranu in u graficu, chì hè assai cunnisciutu (è abbastanza ovviamente) impussibile in un gràficu bipartitu. Altrimenti, avemu una partizione curretta, chì significa chì u graficu hè bipartitu.
Di genere, stu algoritmu hè implementatu cù l'usu o . In lingue imperative, a ricerca di prufundità prima hè generalmente usata perchè hè un pocu più simplice è ùn necessita micca strutture di dati supplementari. Aghju sceltu ancu a ricerca di a prufundità prima perchè hè più tradiziunale.
Cusì, avemu ghjuntu à u schema seguente. Traversemu i vertici di u gràficu utilizendu a ricerca di prufundità prima è assignemu azzioni à elli, cambiendu u numeru di a parte cum'è ci movemu longu u bordu. Se pruvemu d'assignà una parte à un vertice chì hà digià una parte assignata, pudemu dì sicuru chì u graficu ùn hè micca bipartitu. U mumentu chì tutti i vertici sò assignati una parte è avemu vistu tutti i bordi, avemu una bona partizione.
Purità di calculi
In Haskell assumemu chì tutti i calculi sò pulita. Tuttavia, s'ellu era veramente u casu, ùn averemu micca manera di stampà qualcosa à u screnu. Per nunda, pulita i calculi sò cusì pigri chì ùn ci hè micca unu pulitu ragioni per calculà qualcosa. Tutti i calculi accaduti in u prugramma sò in qualchì manera furzati "impuru" monade IO.
Monadi sò una manera di rapprisintà calculi cù effetti in Haskell. Spiegà cumu travaglianu hè fora di u scopu di stu post. Una descrizzione bona è chjara pò esse leghje in inglese .
Quì vogliu nutà chì, mentri certi monadi, cum'è IO, sò implementati da a magia di compilatore, quasi tutti l'altri sò implementati in u software è tutti i calculi in elli sò puri.
Ci sò assai effetti è ognunu hà a so propria monade. Questa hè una teoria assai forte è bella: tutte e monadi implementanu a stessa interfaccia. Parleremu di e trè monadi seguenti:
- O ea hè un calculu chì torna un valore di u tipu a o ghjetta una eccezzioni di u tipu e. U cumpurtamentu di sta monade hè assai simili à a gestione di l'eccezzioni in lingue imperativi: l'errori ponu esse catturati o trasmessi. A diferenza principale hè chì a monade hè cumpletamente implementata logicamente in a biblioteca standard in Haskell, mentre chì i linguaggi imperativi generalmente utilizanu miccanismi di u sistema operatore.
- State sa hè un calculu chì torna un valore di tipu a è hà accessu à u statu mutabile di tipu s.
- Forse a. A monade Forse sprime un calculu chì pò esse interrottu in ogni mumentu restituendu Nulla. In ogni casu, parlemu di l'implementazione di a classa MonadPlus per u tipu Maybe, chì sprime l'effettu oppostu: hè un calculu chì pò esse interrottu in ogni mumentu restituendu un valore specificu.
Implementazione di l'algoritmu
Avemu dui tipi di dati, Graph a è Bigraph ab, u primu di quale rapprisenta grafici cù vertici marcati cù valori di tipu a, è u sicondu rapprisenta grafici bipartiti cù vertici di sinistra marcati cù valori di tipu a è right. -Vertici laterali marcati cù valori di tipu b.
Quessi ùn sò micca tipi da a biblioteca Alga. Alga ùn hà micca una rapprisintazioni per i gràfici bipartiti senza direzzione. Aghju fattu i tipi cusì per a clarità.
Averemu ancu bisognu di funzioni d'aiutu cù e seguenti firme:
-- Список соседей данной вершины.
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)Hè facilitu per vede chì se durante a ricerca di a prufundità prima truvamu un bordu cunflittu, u ciculu stranu si trova nantu à a pila di ricursione. Cusì, per restaurà, avemu bisognu di cutà tuttu da a pila di ricursione finu à a prima occurrence di l'ultimu vertice.
Implementemu a ricerca di prufundità prima mantenendu una matrice associativa di numeri di sparte per ogni vertice. A pila di ricursione serà mantinutu automaticamente per mezu di l'implementazione di a classa Functor di a monada chì avemu sceltu: avemu solu bisognu di mette tutti i vertici da a strada in u risultatu tornatu da a funzione recursiva.
A mo prima idea era d'utilizà a monade Either, chì pari di implementà esattamente l'effetti chì avemu bisognu. A prima implementazione chì aghju scrittu era assai vicinu à questa opzione. In fattu, aghju avutu cinque implementazioni diverse in un puntu è eventualmente si stabiliscenu in un altru.
Prima, avemu bisognu di mantene un array assuciativu di identificatori di sparte - questu hè qualcosa di Statu. Siconda, avemu bisognu di pudè piantà quandu un cunflittu hè rilevatu. Questu pò esse sia Monad per Either, sia MonadPlus per Forse. A principal diferenza hè chì O pò vultà un valore se u calculu ùn hè micca firmatu, è Forse torna solu infurmazione nantu à questu in questu casu. Siccomu ùn avemu micca bisognu di un valore separatu per u successu (hè digià guardatu in u Statu), scegliemu Forse. È à u mumentu quandu avemu bisognu di cumminà l'effetti di dui monadi, escenu , chì combina precisamente questi effetti.
Perchè aghju sceltu un tipu cusì cumplessu? Dui motivi. Prima, l'implementazione hè assai simile à l'imperativu. Siconda, avemu bisognu di manipulà u valore di ritornu in casu di cunflittu quandu torna da a ricursione per restaurà l'odd loop, chì hè assai più faciule da fà in a Monada Forse.
Cusì avemu sta implementazione.
{-# 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)
U bloccu induve hè u core di l'algoritmu. Pruvaraghju di spiegà ciò chì succede in ellu.
- inVertex hè a parte di a ricerca di a prufundità prima induve visitemu u vertice per a prima volta. Quì assignemu un numeru di sparte à u vertice è eseguimu onEdge nantu à tutti i vicini. Questu hè ancu induve restaurà a pila di chjama: se msum hà restituutu un valore, spingemu u vertice v quì.
- onEdge hè a parte induve visitemu u bordu. Hè chjamatu duie volte per ogni bordu. Quì avemu cuntrollà s'ellu u vertice nant'à l 'autru latu hè statu visitatu, è visita lu s'ellu ùn. Se visitate, cuntrollemu se u bordu hè cunflittu. S'ellu hè, vultemu u valore - a cima di a pila di recursione, induve tutti l'altri vertici seranu postu dopu à u ritornu.
- processVertex verifica per ogni vertice s'ellu hè statu visitatu è eseguisce inVertex nantu à ellu se no.
- dfs esegue processVertex su tutti i vertici.
Eccu tuttu.
Storia di a parolla INLINE
A parolla INLINE ùn era micca in a prima implementazione di l'algoritmu; apparsu dopu. Quandu aghju pruvatu à truvà una implementazione megliu, aghju trovu chì a versione non-INLINE era notevolmente più lenta in certi grafici. Cunsiderendu chì semanticamente e funzioni duveranu travaglià u listessu, questu m'hà surprisatu assai. Ancu più straneru, in una altra macchina cù una versione sfarente di GHC ùn ci era nisuna differenza notevuli.
Dopu avè passatu una settimana à leghje l'output GHC Core, aghju pussutu risolve u prublema cù una linea di INLINE esplicita. À un certu puntu trà GHC 8.4.4 è GHC 8.6.5, l'ottimisatore hà cessatu di fà questu per sè stessu.
Ùn m'aspittava micca di scuntrà cusì brutta in a prugrammazione Haskell. In ogni casu, ancu oghje, l'ottimisatori facenu qualchì volta sbagli, è hè u nostru travagliu di dà li suggerimenti. Per esempiu, quì sapemu chì a funzione deve esse inlineed perchè hè inlineed in a versione imperativa, è questu hè un mutivu per dà u compilatore un suggerimentu.
Chì successe dopu ?
Allora aghju implementatu l'algoritmu Hopcroft-Karp cù altre monadi, è questu era a fine di u prugramma.
Grazie à Google Summer of Code, aghju acquistatu una sperienza pratica in a prugrammazione funziunale, chì ùn solu m'hà aiutatu à ottene un stage in Jane Street l'estate dopu (ùn sò micca sicuru chì questu locu sia cunnisciutu ancu trà l'audienza esperta di Habr, ma hè unu di i pochi induve pudete l'estate per impegnà in a prugrammazione funziunale), ma ancu m'hà introduttu à u mondu maravigliu di l'applicazione di stu paradigma in pratica, significativamente sfarente da a mo spirienza in lingue tradiziunali.
Source: www.habr.com