L'estate scorsa ho partecipato - un programma per studenti di Google. Ogni anno gli organizzatori selezionano diversi progetti Open Source, anche di organizzazioni rinomate come и . Google invita studenti da tutto il mondo a lavorare su questi progetti.
Come partecipante al Google Summer of Code 2019, ho realizzato un progetto all'interno della biblioteca con l'organizzazione , che sta sviluppando il linguaggio Haskell, uno dei linguaggi di programmazione funzionale più famosi. Alga è una libreria che rappresenta rappresentazione dei grafici in Haskell. Viene utilizzato, ad esempio, in — una libreria Github che crea alberi semantici, grafici delle chiamate e delle dipendenze basati sul codice e può confrontarli. Il mio progetto consisteva nell'aggiungere una rappresentazione indipendente dai tipi per i grafici bipartiti e gli algoritmi per tale rappresentazione.
In questo post parlerò della mia implementazione di un algoritmo per il controllo della bipartitezza di un grafico in Haskell. Anche se l'algoritmo è uno dei più basilari, implementarlo magnificamente in uno stile funzionale mi ha richiesto diverse iterazioni e molto lavoro. Di conseguenza, ho optato per un'implementazione con trasformatori monade.
Informazioni su di me
Mi chiamo Vasily Alferov, sono uno studente del quarto anno all'HSE di San Pietroburgo. In precedenza nel blog ho scritto и . In questo momento sto facendo uno stage presso in Norvegia, dove sto lavorando sugli approcci al problema . I miei interessi includono algoritmi parametrizzati e programmazione funzionale.
Informazioni sull'implementazione dell'algoritmo
prefazione
Gli studenti che partecipano al programma sono fortemente incoraggiati a bloggare. Mi hanno fornito una piattaforma per il blog . Questo articolo è una traduzione , scritto da me lì a luglio in inglese, con una breve prefazione.
È possibile trovare la pull request con il codice in questione .
Puoi leggere i risultati del mio lavoro (in inglese) .
Questo post presuppone che il lettore abbia familiarità con i concetti di base della programmazione funzionale, anche se cercherò di richiamare tutti i termini utilizzati quando sarà il momento.
Controllo della bipartitezza dei grafici
Un algoritmo per verificare la bipartitezza di un grafico viene solitamente fornito in un corso sugli algoritmi come uno degli algoritmi grafici più semplici. La sua idea è semplice: prima inseriamo in qualche modo i vertici nella parte sinistra o destra e, quando viene trovato un bordo in conflitto, affermiamo che il grafico non è bipartito.
Un po' più in dettaglio: per prima cosa inseriamo qualche vertice nella parte sinistra. Ovviamente tutti i vicini di questo vertice devono trovarsi nel lobo destro. Inoltre, tutti i vicini dei vicini di questo vertice devono trovarsi nel lobo sinistro e così via. Continuiamo ad assegnare quote ai vertici finché ci sono ancora vertici nella componente connessa del vertice con cui abbiamo iniziato a cui non abbiamo assegnato i vicini. Ripetiamo quindi questa azione per tutti i componenti collegati.
Se c'è un bordo tra i vertici che ricadono nella stessa partizione, non è difficile trovare un ciclo dispari nel grafo, cosa ampiamente nota (e abbastanza ovviamente) impossibile in un grafo bipartito. Altrimenti abbiamo una partizione corretta, il che significa che il grafico è bipartito.
In genere, questo algoritmo viene implementato utilizzando o . Nei linguaggi imperativi viene solitamente utilizzata la ricerca approfondita poiché è leggermente più semplice e non richiede strutture dati aggiuntive. Ho scelto anche la ricerca approfondita poiché è più tradizionale.
Siamo quindi giunti al seguente schema. Attraversiamo i vertici del grafico utilizzando la ricerca in profondità e assegniamo loro delle quote, modificando il numero della quota mentre ci muoviamo lungo il bordo. Se proviamo ad assegnare una quota ad un vertice a cui è già assegnata una quota, possiamo tranquillamente affermare che il grafo non è bipartito. Nel momento in cui a tutti i vertici viene assegnata una condivisione e abbiamo esaminato tutti i bordi, abbiamo una buona partizione.
Purezza dei calcoli
In Haskell assumiamo che tutti i calcoli lo siano pulito. Tuttavia, se così fosse, non avremmo modo di stampare nulla sullo schermo. Affatto, pulito i calcoli sono così pigri che non ce n'è uno puro motivi per calcolare qualcosa. Tutti i calcoli che si verificano nel programma vengono in qualche modo forzati "impuro" monade IO.
Le monadi sono un modo per rappresentare i calcoli con effetti ad Haskell. Spiegare come funzionano va oltre lo scopo di questo post. Una descrizione buona e chiara può essere letta in inglese .
Qui voglio sottolineare che mentre alcune monadi, come IO, sono implementate tramite la magia del compilatore, quasi tutte le altre sono implementate nel software e tutti i calcoli in essi contenuti sono puri.
Ci sono molti effetti e ognuno ha la propria monade. Questa è una teoria molto forte e bella: tutte le monadi implementano la stessa interfaccia. Parleremo delle seguenti tre monadi:
- O ea è un calcolo che restituisce un valore di tipo a o genera un'eccezione di tipo e. Il comportamento di questa monade è molto simile alla gestione delle eccezioni nei linguaggi imperativi: gli errori possono essere rilevati o trasmessi. La differenza principale è che la monade è implementata in modo completamente logico nella libreria standard di Haskell, mentre i linguaggi imperativi utilizzano solitamente i meccanismi del sistema operativo.
- Lo stato sa è un calcolo che restituisce un valore di tipo a e ha accesso allo stato modificabile di tipo s.
- Forse un. La monade Forse esprime un calcolo che può essere interrotto in qualsiasi momento restituendo Niente. Parleremo però dell'implementazione della classe MonadPlus per la tipologia Forse, che esprime l'effetto opposto: si tratta di un calcolo che può essere interrotto in qualsiasi momento restituendo un valore specifico.
Implementazione dell'algoritmo
Abbiamo due tipi di dati, Graph a e Bigraph ab, il primo dei quali rappresenta grafici con vertici etichettati con valori di tipo a, e il secondo rappresenta grafici bipartiti con vertici di sinistra etichettati con valori di tipo a e di destra -lati vertici etichettati con valori di tipo b.
Questi non sono tipi della libreria Alga. Alga non ha una rappresentazione per i grafi bipartiti non orientati. Ho creato i tipi come questo per chiarezza.
Avremo bisogno anche di funzioni di supporto con le 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)È facile vedere che se durante la ricerca in profondità troviamo un arco in conflitto, il ciclo dispari si trova in cima allo stack di ricorsione. Quindi, per ripristinarlo, dobbiamo tagliare tutto, dallo stack di ricorsione fino alla prima occorrenza dell'ultimo vertice.
Implementiamo la ricerca approfondita mantenendo un array associativo di numeri di condivisione per ciascun vertice. Lo stack di ricorsione verrà mantenuto automaticamente attraverso l'implementazione della classe Functor della monade che abbiamo scelto: dovremo solo inserire tutti i vertici del percorso nel risultato restituito dalla funzione ricorsiva.
La mia prima idea è stata quella di utilizzare la monade Both, che sembra implementare esattamente gli effetti di cui abbiamo bisogno. La prima implementazione che ho scritto era molto vicina a questa opzione. In effetti, ad un certo punto ho avuto cinque diverse implementazioni e alla fine ne ho optato per un'altra.
Innanzitutto, dobbiamo mantenere un array associativo di identificatori di condivisione: questo riguarda lo Stato. In secondo luogo, dobbiamo essere in grado di fermarci quando viene rilevato un conflitto. Può essere Monad per Entrambi o MonadPlus per Forse. La differenza principale è che O può restituire un valore se il calcolo non è stato interrotto e Forse in questo caso restituisce solo informazioni al riguardo. Poiché non abbiamo bisogno di un valore separato per il successo (è già memorizzato in State), scegliamo Forse. E nel momento in cui dobbiamo combinare gli effetti di due monadi, queste escono , che combinano proprio questi effetti.
Perché ho scelto una tipologia così complessa? Due ragioni. Innanzitutto, l'implementazione risulta essere molto simile all'imperativo. In secondo luogo, dobbiamo manipolare il valore restituito in caso di conflitto quando torniamo dalla ricorsione per ripristinare il ciclo dispari, cosa molto più semplice da fare nella monade Forse.
Quindi otteniamo questa 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)
Il blocco dove è il cuore dell'algoritmo. Cercherò di spiegare cosa sta succedendo al suo interno.
- inVertex è la parte della ricerca approfondita in cui visitiamo il vertice per la prima volta. Qui assegniamo un numero di condivisione al vertice ed eseguiamo onEdge su tutti i vicini. Questo è anche il punto in cui ripristiniamo lo stack di chiamate: se msum restituisce un valore, inseriamo lì il vertice v.
- onEdge è la parte in cui visitiamo il bordo. Viene chiamato due volte per ciascun bordo. Qui controlliamo se il vertice dall'altra parte è stato visitato e lo visitiamo in caso contrario. Se visitato, controlliamo se il bordo è in conflitto. Se lo è, restituiamo il valore: la parte superiore dello stack di ricorsione, dove tutti gli altri vertici verranno posizionati al ritorno.
- processVertex controlla per ciascun vertice se è stato visitato ed esegue inVertex su di esso in caso contrario.
- dfs esegue processVertex su tutti i vertici.
È tutto.
Storia della parola INLINE
La parola INLINE non era nella prima implementazione dell'algoritmo; è apparsa più tardi. Quando ho provato a trovare un'implementazione migliore, ho scoperto che la versione non INLINE era notevolmente più lenta su alcuni grafici. Considerando che semanticamente le funzioni dovrebbero funzionare allo stesso modo, la cosa mi ha molto sorpreso. Ancora più strano, su un'altra macchina con una versione diversa di GHC non c'erano differenze evidenti.
Dopo aver trascorso una settimana a leggere l'output di GHC Core, sono riuscito a risolvere il problema con una riga di INLINE esplicito. Ad un certo punto tra GHC 8.4.4 e GHC 8.6.5 l'ottimizzatore ha smesso di farlo da solo.
Non mi aspettavo di incontrare tanta sporcizia nella programmazione Haskell. Tuttavia, anche oggi, gli ottimizzatori a volte commettono errori ed è nostro compito fornire loro suggerimenti. Ad esempio, qui sappiamo che la funzione dovrebbe essere inline perché lo è nella versione imperativa, e questo è un motivo per dare un suggerimento al compilatore.
Cosa è successo dopo?
Poi ho implementato l'algoritmo di Hopcroft-Karp con altre monadi, e quella è stata la fine del programma.
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 in cui è possibile dedicarsi all'estate alla programmazione funzionale), ma mi ha anche introdotto nel meraviglioso mondo dell'applicazione pratica di questo paradigma, significativamente diverso dalla mia esperienza con i linguaggi tradizionali.
Fonte: habr.com