Lo scorso estate ho partecipato a — un programma per studenti organizzato da Google. Ogni anno, gli organizzatori selezionano alcuni progetti Open Source, tra cui quelli di importanti organizzazioni come e . Per lavorare su questi progetti, Google invita studenti da tutto il mondo.
Come partecipante al Google Summer of Code 2019, ho lavorato a un progetto all'interno della libreria in collaborazione con , un'organizzazione dedicata allo sviluppo del linguaggio Haskell, uno dei linguaggi di programmazione funzionali più noti. Alga è una libreria che offre per grafi in Haskell. È utilizzata, ad esempio, in — una libreria di GitHub che costruisce alberi semantici, grafi di chiamata e dipendenze dal codice, e che può confrontarli. Il mio progetto consisteva nell'aggiungere una rappresentazione tipo-sicura per grafi bipartiti e algoritmi per questa rappresentazione.
In questo post parlerò della mia implementazione dell'algoritmo per verificare se un grafo è bipartito utilizzando Haskell. Sebbene l'algoritmo sia uno dei più basilari, la sua bella implementazione in stile funzionale ha richiesto diverse iterazioni e molto lavoro. Alla fine, ho optato per un'implementazione con trasformatori monadici.
Su di me
Mi chiamo Vasily Alferov, sono uno studente del quarto anno della Higher School of Economics di San Pietroburgo. In precedenza, ho scritto nel blog e . Attualmente sono in stage presso in Norvegia, dove mi occupo di approcci al problema di . I miei interessi includono algoritmi parametrizzati e programmazione funzionale.
Sull'implementazione dell'algoritmo
Prefazione
Agli studenti partecipanti al programma si consiglia vivamente di tenere un blog. Mi è stata fornita una piattaforma per il blog . Questo articolo è una traduzione , scritta da me lì in luglio in inglese, con un breve preambolo.
La Pull Request con il codice di cui si parla può essere trovata .
Puoi leggere dei risultati del mio lavoro (in inglese) .
Questo articolo introduce il lettore ai concetti fondamentali della programmazione funzionale, sebbene cercherò di ricordare tutti i termini utilizzati quando sarà il momento.
Verifica dei grafi per bicolore
L'algoritmo per la verifica di un grafo bicolore è generalmente presentato nel corso di algoritmi come uno dei più semplici algoritmi sui grafi. La sua idea è diretta: iniziamo a collocare i vertici in una parte sinistra o destra, e quando rileviamo un bordo conflittuale, affermiamo che il grafo non è bicolore.
Un po' più nel dettaglio: iniziamo collocando un vertice in una parte sinistra. Ovviamente, tutti i vicini di questo vertice devono trovarsi nella parte destra. In seguito, tutti i vicini dei vicini di questo vertice devono trovarsi nella parte sinistra, e così via. Continuiamo ad assegnare parti ai vertici finché nel componente di connettività del vertice da cui abbiamo iniziato ci sono ancora vertici ai quali non abbiamo assegnato vicini. Poi ripetiamo questa operazione per tutti i componenti di connettività.
Se esiste un arco tra i vertici che rientrano nella stessa partizione, non è difficile trovare un ciclo dispari nel grafo, come è ampiamente noto (e abbastanza ovvio) impossibile in un grafo bipartito. Altrimenti, abbiamo una partizione valida, il che significa che il grafo è bipartito.
Di norma, questo algoritmo viene implementato tramite o . Nei linguaggi imperativi si utilizza generalmente la ricerca in profondità, essendo leggermente più semplice e non richiedendo strutture dati aggiuntive. Ho scelto anche la ricerca in profondità come opzione più tradizionale.
Pertanto, siamo arrivati alla seguente procedura. Esploriamo i vertici del grafo utilizzando la ricerca in profondità e assegniamo loro partizioni, cambiando il numero della partizione quando ci spostiamo lungo un arco. Se tentiamo di assegnare una partizione a un vertice già assegnato, possiamo affermare con certezza che il grafo non è bipartito. Nel momento in cui tutte le partizioni sono state assegnate e abbiamo esaminato tutti gli archi, abbiamo una buona partizione.
Purezza dei calcoli
In Haskell assumiamo che tutti i calcoli siano purificati. Tuttavia, se fosse davvero così, non avremmo la possibilità di stampare nulla sullo schermo. In generale, puliti i calcoli sono così pigri che non esiste alcun pulito motivo per calcolare qualcosa. Tutti i calcoli che avvengono nel programma vengono forzati in un modo o nell'altro in una "non pulita" monade IO.
Le monadi sono un modo per rappresentare calcoli con effetti in Haskell. Spiegare come funzionano va oltre il tema di questo post. Una buona e chiara descrizione può essere letta in inglese. .
Qui voglio notare che, mentre alcune monadi, come IO, sono implementate tramite la magia del compilatore, quasi tutte le altre sono implementate programmaticamente e tutti i calcoli in esse sono puri.
Esistono molti tipi di effetti e per ciascuno è stata creata una propria monade. Questa è una teoria molto potente e bella: tutte le monadi implementano lo stesso interfaccia. Parleremo delle seguenti tre monadi:
- Either e a — un calcolo che restituisce un valore di tipo a o solleva un'eccezione di tipo e. Il comportamento di questo monade è molto simile alla gestione delle eccezioni nei linguaggi imperativi: gli errori possono essere catturati o propagati. L'unica differenza principale è che la monade è completamente implementata logicamente nella libreria standard dello stesso Haskell, mentre nei linguaggi imperativi si usano tipicamente i meccanismi del sistema operativo.
- State s a — un calcolo che restituisce un valore di tipo a e ha accesso a uno stato mutabile di tipo s.
- Maybe a. La monade Maybe esprime un calcolo che può essere interrotto ritornando Nothing in qualsiasi momento. Tuttavia, parleremo dell'implementazione della classe MonadPlus per il tipo Maybe, che esprime l'effetto opposto: questo calcolo può essere interrotto in qualsiasi momento restituendo un valore specifico.
Implementazione dell'algoritmo
Abbiamo due tipi di dati, Graph a e Bigraph a b; il primo rappresenta grafi con vertici etichettati con valori di tipo a, mentre il secondo rappresenta grafi bipartiti con vertici del lato sinistro etichettati con valori di tipo a e vertici del lato destro etichettati con valori di tipo b.
Questi non sono tipi della libreria Alga. In Alga non esiste una rappresentazione per grafi bipartiti non orientati. Ho creato questi tipi per chiarezza.
Avremo anche bisogno di funzioni ausiliarie con le seguenti firme:
-- Lista dei vicini di un dato vertice.
neighbours :: Ord a => a -> Graph a -> [a]
-- Costruire un grafo bipartito a partire da un grafo e da una funzione,
-- per ciascun vertice che restituisce la sua parte e l'etichetta nella nuova parte,
-- ignorando i bordi in conflitto.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Lista dei vertici nel grafo
vertexList :: Ord a => Graph a -> [a]
La firma della funzione che scriveremo è la seguente:
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à troviamo un arco conflittuale, il ciclo dispari si trova sopra lo 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 degli indici per ogni vertice. Lo stack di ricorsione sarà mantenuto automaticamente tramite l'implementazione della classe Functor della monade scelta: sarà necessario solo inserire tutti i vertici nel percorso nel risultato restituito dalla funzione ricorsiva.
La mia prima idea è stata di utilizzare la monade Either, che sembra implementare esattamente quegli effetti di cui abbiamo bisogno. La prima implementazione che ho scritto era molto simile a questa variante. In realtà, avevo cinque diverse implementazioni a un certo punto, e alla fine mi sono fermato su un'altra.
In primo luogo, dobbiamo gestire un array associativo di identificatori delle quote — riguarda qualcosa dello Stato. In secondo luogo, dobbiamo essere in grado di fermarci in caso di rilevamento di un conflitto. Questo può essere o un Monad per Either, o MonadPlus per Maybe. La principale differenza è che Either può restituire un valore nel caso in cui il calcolo non si sia fermato, mentre Maybe restituisce solo un'informazione al riguardo. Poiché non abbiamo bisogno di un valore separato in caso di successo (è già memorizzato nello Stato), scegliamo Maybe. E nel momento in cui dobbiamo combinare gli effetti di due monadi, emergono , che combinano proprio questi effetti.
Perché ho scelto un tipo così complesso? Due motivi. In primo luogo, l'implementazione risulta essere molto simile a quella imperativa. In secondo luogo, dobbiamo maneggiare 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 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 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 accade al suo interno.
- inVertex è la parte della ricerca in profondità in cui visitiamo un vertice per la prima volta. Qui assegniamo al vertice un numero di parte e chiamiamo onEdge per tutti i vicini. È anche il posto dove ripristiniamo lo stack delle chiamate: se msum ha restituito un valore, appendiamo lì il vertice v.
- onEdge è la parte in cui visitiamo un arco. Viene chiamata due volte per ogni arco. Qui controlliamo se il vertice dall'altro lato è stato visitato e lo visitiamo se non lo è. Se è già stato visitato, controlliamo se l'arco è conflittuale. Se lo è, restituiamo il valore – l'elemento superiore dello stack della ricorsione, su cui poi verranno appesi tutti gli altri vertici al ritorno.
- processVertex controlla se ogni vertice è stato visitato e attiva inVertex se non lo è.
- dfs esegue processVertex su tutti i vertici.
Questo è tutto.
Storia della parola INLINE
La parola INLINE non era presente nella prima implementazione dell'algoritmo, è comparsa successivamente. Quando ho cercato una migliore implementazione, ho scoperto che su alcuni grafi la versione senza INLINE funziona 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 una versione diversa di GHC non c'era alcuna differenza evidente.
Dopo aver passato una settimana a leggere l'output di GHC Core, sono riuscito a risolvere il problema con una riga di codice che utilizza 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 incontrare così tanta confusione nella programmazione in Haskell. Tuttavia, anche gli ottimizzatori commettono a volte errori e dare loro suggerimenti è il nostro compito. Ad esempio, qui sappiamo che la funzione deve essere inlinata, poiché è inlinata nella versione imperativa, e questo è un motivo per fornire un suggerimento al compilatore.
E poi?
Successivamente, ho implementato l'algoritmo di Hopcroft-Karp con altre monadi, e con questo la programmazione è terminata.
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 la prossima estate (non sono sicuro di quanto sia conosciuto questo posto anche tra il pubblico esperto di Habr, ma è uno dei pochi dove si può fare programmazione funzionale in estate), ma mi ha anche aperto le porte a un mondo straordinario di applicazione di questa prospettiva nella pratica, molto diversa dalla mia esperienza con i linguaggi tradizionali.
Fonte: habr.com
