L'estate scorsa ho partecipato a — un programma per studenti di Google. Ogni anno, gli organizzatori selezionano diversi progetti Open Source, inclusi quelli di organizzazioni rinomate come e . Per lavorare su questi progetti, Google invita studenti da tutto il mondo.
Come partecipante al Google Summer of Code 2019, ho sviluppato un progetto nell'ambito della libreria con l'organizzazione , che si occupa dello sviluppo del linguaggio Haskell — uno dei linguaggi di programmazione funzionale più noti. Alga — una libreria che fornisce per grafi in Haskell. Viene utilizzata, ad esempio, in — una libreria di Github che costruisce alberi semantici, grafi di chiamate e dipendenze e sa confrontarli. Il mio progetto consisteva nell'aggiungere una rappresentazione type-safe per grafi bipartiti e algoritmi per questa rappresentazione.
In questo post parlerò della mia implementazione dell'algoritmo di verifica della bipartizione dei grafi in Haskell. Sebbene l'algoritmo sia uno dei più basilari, la sua elegante implementazione in stile funzionale ha richiesto diverse iterazioni ed è stata piuttosto laboriosa. Alla fine, ho optato per un'implementazione con monad transformers.
Chi sono
Mi chiamo Vasily Alferov, sono uno studente del quarto anno della Higher School of Economics di San Pietroburgo. In precedenza, nel blog ho scritto e . Al momento sono in stage presso in Norvegia, dove mi occupo di approcci al problema . Gli ambiti di mio interesse includono algoritmi parametrizzati e programmazione funzionale.
Sull'implementazione dell'algoritmo
Introduzione
Si consiglia vivamente agli studenti partecipanti al programma di tenere un blog. Per il mio blog, mi è stata fornita la piattaforma . Questo articolo è una traduzione , scritta da me in inglese a luglio, con una breve introduzione.
La Pull Request con il codice di cui si parla può essere trovata .
Puoi leggere sui risultati del mio lavoro (in inglese) .
Il post presuppone che il lettore conosca i concetti di base della programmazione funzionale, anche se cercherò di rinfrescare i termini utilizzati quando sarà il momento.
Verifica della bipartizione dei grafi
L'algoritmo per verificare se un grafo è bipartito è generalmente presentato nei corsi di algoritmi come uno dei più semplici algoritmi grafici. La sua idea è semplice: iniziamo ponendo in qualche modo i vertici nel sottoinsieme sinistro o destro, e nel momento in cui scopriamo un arco conflittuale, affermiamo che il grafo non è bipartito.
Un po' più in dettaglio: iniziamo ponendo un vertice nel sottoinsieme sinistro. Ovviamente, tutti i vicini di questo vertice devono trovarsi nel sottoinsieme destro. Successivamente, tutti i vicini dei vicini di questo vertice devono trovarsi nel sottoinsieme sinistro, e così via. Continuiamo ad assegnare i vertici ai sottoinsiemi fino a quando nella componente connessa del vertice con cui siamo partiti ci sono ancora vertici ai quali non abbiamo assegnato i vicini. Poi ripetiamo quest'operazione per tutte le componenti connesse.
Se esiste un arco tra i vertici che sono stati posti nello stesso sottoinsieme, è facile trovare in un grafo un ciclo dispari, come è ampiamente noto (e abbastanza ovvio) impossibile in un grafo bipartito. Altrimenti, abbiamo una corretta suddivisione in sottoinsiemi, e quindi il grafo è bipartito.
In generale, questo algoritmo viene implementato utilizzando o . Nei linguaggi imperativi di solito viene utilizzata la ricerca in profondità, che è leggermente più semplice e non richiede strutture dati aggiuntive. Ho anche scelto la ricerca in profondità come quella più tradizionale.
Così, siamo arrivati alla seguente schematizzazione. Attraversiamo i vertici del grafo utilizzando la ricerca in profondità e assegniamo loro i sottoinsiemi, cambiando il numero del sottoinsieme mentre ci spostiamo lungo un arco. Se cerchiamo di assegnare un sottoinsieme a un vertice già assegnato, possiamo affermare con certezza che il grafo non è bipartito. Nel momento in cui tutti i vertici hanno ricevuto un sottoinsieme e abbiamo esaminato tutti gli archi, abbiamo una buona suddivisione.
Purezza dei calcoli
In Haskell presumiamo che tutti i calcoli siano puri. Tuttavia, se ciò fosse realmente così, non avremmo la possibilità di stampare nulla sullo schermo. In generale, i calcoli sono così pigri che non esiste alcun motivo puro per calcolare qualcosa. Tutti i calcoli che avvengono nel programma, in un modo o nell'altro, vengono forzati nella monade 'impura'. Le monadi sono un modo per rappresentare i calcoli con effetti.
Le monadi sono un modo per rappresentare calcoli con effetti in Haskell. A detailed explanation of how they work goes beyond this post. A good and clear description can be found in English. .
Here I want to note that while some monads, such as IO, are implemented through compiler magic, almost all others are implemented programmatically and all computations within them are pure.
There are many effects and each has its own monad. This is a very strong and beautiful theory: all monads implement the same interface. We will discuss the following three monads:
- Either e a — a computation that returns a value of type a or throws an exception of type e. The behavior of this monad is very similar to working with exceptions in imperative languages: errors can be caught or propagated. The main difference is that the monad is fully logically implemented in the standard library in the same Haskell, while in imperative languages, operating system mechanisms are usually used.
- State s a — a computation that returns a value of type a and has access to mutable state of type s.
- Maybe a. The Maybe monad expresses a computation that can be interrupted at any moment by returning Nothing. However, we will discuss the implementation of the MonadPlus class for the Maybe type, which expresses the opposite effect: this is a computation that can be interrupted at any moment by returning a specific value.
Implementation of the algorithm
We have two data types, Graph a and Bigraph a b, the first represents graphs with vertices labeled with values of type a, and the second represents bipartite graphs with left part vertices labeled with values of type a and right part vertices labeled with values of type b.
These are not types from the Alga library. Alga does not have a representation for undirected bipartite graphs. I made the types this way for clarity.
We will also need auxiliary functions with the following signatures:
-- Elenco dei nodi adiacenti a questo vertice.
neighbours :: Ord a => a -> Graph a -> [a]
-- Costruire un grafo bipartito a partire dal grafo e dalla funzione, per ogni vertice
-- che restituisce la sua parte e l'etichetta nella nuova parte, ignorando gli archi conflittuali.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Elenco dei vertici nel grafo
vertexList :: Ord a => Graph a -> [a]
La firma della funzione che scriveremo appare così:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Non è difficile notare che se durante la ricerca in profondità abbiamo trovato un arco conflittuale, il ciclo dispari si trova in cima allo stack di ricorsione. Pertanto, per ripristinarlo, dobbiamo tagliare dallo stack di ricorsione tutto fino alla prima occorrenza dell'ultimo vertice.
Implementeremo la ricerca in profondità, mantenendo un array associativo dei numeri di parte per ogni vertice. Lo stack di ricorsione sarà mantenuto automaticamente attraverso l'implementazione della classe Functor della monade scelta: sarà sufficiente mettere tutti i vertici del percorso nel risultato restituito dalla funzione ricorsiva.
La mia prima idea è stata di utilizzare la monade Either, che sembra implementare esattamente gli effetti di cui abbiamo bisogno. La prima implementazione che ho scritto era molto simile a questa variante. Infatti, avevo cinque diverse implementazioni in un certo momento e alla fine mi sono fermato su un'altra.
Prima di tutto, dobbiamo mantenere un array associativo degli identificatori delle parti — è una questione di State. In secondo luogo, dobbiamo essere in grado di fermarci in caso di conflitto. Questo può essere o Monad per Either, o MonadPlus per Maybe. La principale differenza è che Either può restituire un valore nel caso in cui il calcolo non sia stato interrotto, mentre Maybe restituisce solo informazioni al riguardo. Poiché non abbiamo bisogno di un valore separato in caso di successo (è già memorizzato in State), scegliamo Maybe. E nel momento in cui dobbiamo combinare gli effetti di due monadi, emergono , che combinano esattamente questi effetti.
Perché ho scelto un tipo così complesso? Due motivi. In primo luogo, l'implementazione risulta molto simile a quella imperativa. In secondo luogo, dobbiamo manipolare il valore restituito in caso di conflitto, durante il ritorno dalla ricorsione per ripristinare un ciclo dispari, e questo è molto più semplice da fare nella monade Maybe.
In questo modo otteniamo tale 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 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)
Il blocco where è il nucleo dell'algoritmo. Cercherò di spiegare cosa succede al suo interno.
- inVertex è la parte della ricerca in profondità in cui visitamo un vertice per la prima volta. Qui assegniamo al vertice un numero di parte e avviamo onEdge per tutti i vicini. È anche il luogo in cui ripristiniamo lo stack delle chiamate: se msum restituisce un valore, inseriamo il vertice v.
- onEdge è la parte in cui visitiamo il bordo. Viene chiamata due volte per ogni bordo. Qui controlliamo se il vertice dall'altra parte è stato visitato e lo visitiamo se non lo è. Se è stato visitato, verifichiamo se il bordo è in conflitto. Se lo è, restituiamo il valore — la parte superiore dello stack di ricorsione, sulla quale poi verranno sovrapposti tutti gli altri vertici al termine del ritorno.
- processVertex controlla se ogni vertice è stato visitato e avvia inVertex su di esso se non lo è.
- dfs avvia processVertex su tutti i vertici.
Questo è tutto.
Storia della parola INLINE
La parola INLINE non era presente nella prima implementazione dell'algoritmo, è apparsa successivamente. Quando cercavo una migliore implementazione, ho scoperto che su alcuni grafi la versione senza INLINE funzionava notevolmente più lentamente. Considerando che semanticamente le funzioni dovrebbero funzionare allo stesso modo, questo mi ha sorpreso molto. Ancora più strano è che su un'altra macchina con un'altra versione di GHC non c'era alcuna differenza evidente.
Dopo aver speso una settimana a leggere l'output di GHC Core, sono riuscito a risolvere il problema con una sola riga usando INLINE esplicito. A un certo punto tra GHC 8.4.4 e GHC 8.6.5, l'ottimizzatore ha smesso di farlo autonomamente.
Non mi aspettavo di trovare una situazione così complicata nella programmazione in Haskell. Tuttavia, anche al giorno d'oggi, gli ottimizzatori a volte commettono errori e il nostro compito è dare loro suggerimenti. Ad esempio, qui sappiamo che la funzione deve essere inlinata, poiché è inlinata nella versione imperativa, e questo è un motivo per dare un suggerimento al compilatore.
Cosa è successo dopo?
Successivamente, ho implementato l'algoritmo di Hopcroft-Karp già con altre monadi, e a questo punto il programma è terminato.
Grazie a Google Summer of Code, ho acquisito esperienza pratica nella programmazione funzionale, che non solo mi ha aiutato a ottenere uno stage presso Jane Street l'estate successiva (non sono sicuro di quanto sia noto questo posto anche tra il pubblico esperto di Habr, ma è uno dei pochi dove si può fare programmazione funzionale durante l'estate), ma mi ha anche introdotto a un mondo straordinario di applicazione di questa paradigm in pratica, molto diverso dalla mia esperienza nei linguaggi tradizionali.
Fonte: habr.com
