Letztes Jahr habe ich an — einem Programm für Studenten von Google. Jedes Jahr wählen die Organisatoren mehrere Open Source-Projekte aus, darunter von so bekannten Organisationen wie und . Google lädt Studenten aus der ganzen Welt ein, an diesen Projekten zu arbeiten.
Als Teilnehmer von Google Summer of Code 2019 habe ich ein Projekt im Rahmen der Bibliothek mit der Organisation , die sich mit der Entwicklung der Programmiersprache Haskell beschäftigt — einer der bekanntesten funktionalen Programmiersprachen. Alga — eine Bibliothek, die Darstellungen für Graphen in Haskell bietet. Sie wird unter anderem in , der Bibliothek von Github, verwendet, die aus dem Code semantische Bäume, Aufruf- und Abhängigkeitsgraphen erstellt und diese vergleichen kann. Mein Projekt bestand darin, eine typensichere Darstellung für bipartite Graphen und Algorithmen für diese Darstellung hinzuzufügen.
In diesem Beitrag werde ich über meine Implementierung des Algorithmus zur Überprüfung der Bipartitheit von Graphen in Haskell berichten. Obwohl der Algorithmus einer der grundlegendsten ist, benötigte seine schöne Umsetzung im funktionalen Stil mehrere Iterationen und erforderte ziemlich viel Arbeit. Schließlich entschied ich mich für eine Implementierung mit Monaden-Transformatoren.
Über mich
Ich heiße Wassili Alfjow, ich bin Student im vierten Jahr an der Peter-Pauls-Universität. Früher habe ich in meinem Blog und . Im Moment mache ich ein Praktikum an der in Norwegen, wo ich mich mit Ansätzen zur Problematik . Mein Interessensgebiet umfasst parametrische Algorithmen und funktionale Programmierung.
Über die Implementierung des Algorithmus
Vorwort
Es wird den Studenten, die am Programm teilnehmen, dringend empfohlen, einen Blog zu führen. Mir wurde eine Plattform für den Blog zur Verfügung gestellt . Dieser Artikel ist eine Übersetzung , die ich dort im Juli auf Englisch geschrieben habe, mit einem kurzen Vorwort.
Der Pull Request mit dem Code, um den es geht, ist zu finden .
Über die Ergebnisse meiner Arbeit kann man (in Englisch) lesen .
Der Beitrag setzt voraus, dass der Leser mit den grundlegenden Konzepten der funktionalen Programmierung vertraut ist, obwohl ich versuchen werde, alle verwendeten Begriffe zu wiederholen, wenn die Zeit dafür gekommen ist.
Überprüfung von Graphen auf Bipartitheit
Der Algorithmus zur Überprüfung, ob ein Graph bipartit ist, wird in Algorithmuskursen häufig als einer der einfachsten Graphalgorithmen vorgestellt. Seine Idee ist einfach: Zuerst ordnen wir die Knoten irgendwie der linken oder rechten Teilmenge zu, und wenn eine Konfliktkante entdeckt wird, behaupten wir, dass der Graph nicht bipartit ist.
Um etwas genauer zu werden: Zuerst legen wir einen Knoten in die linke Teilmenge. Offensichtlich müssen alle Nachbarn dieses Knotens in der rechten Teilmenge liegen. Anschließend müssen alle Nachbarn der Nachbarn dieses Knotens in der linken Teilmenge liegen und so weiter. Wir setzen die Zuordnung der Knoten fort, bis in der Zusammenhangskomponente des Knotens, mit dem wir begonnen haben, noch Knoten vorhanden sind, für die wir keine Nachbarn zugewiesen haben. Dann wiederholen wir dieses Vorgehen für alle Zusammenhangskomponenten.
Wenn eine Kante zwischen Knoten existiert, die in derselben Teilmenge sind, ist es nicht schwer, einen ungeraden Zyklus im Graphen zu finden, was, wie allgemein bekannt (und offensichtlich) ist, in einem bipartiten Graphen unmöglich ist. Andernfalls haben wir eine korrekte Aufteilung in Teilmengen, und der Graph ist somit bipartit.
In der Regel wird dieser Algorithmus mittels oder . In imperativen Programmiersprachen verwendet man normalerweise die Tiefensuche, da sie etwas einfacher ist und keine zusätzlichen Datenstrukturen benötigt. Ich habe ebenfalls die Tiefensuche gewählt, da sie traditioneller ist.
Damit sind wir zu folgendem Schema gekommen. Wir durchlaufen die Knoten des Graphen mithilfe der Tiefensuche und ordnen ihnen die Teilmengen zu, indem wir die Nummer der Teilmenge beim Überqueren einer Kante ändern. Wenn wir versuchen, einem Knoten, dem bereits eine Teilmenge zugewiesen wurde, erneut eine Teilmenge zuzuweisen, können wir mit Sicherheit behaupten, dass der Graph nicht bipartit ist. In dem Moment, in dem allen Knoten eine Teilmenge zugewiesen ist und wir alle Kanten betrachtet haben, haben wir eine gute Aufteilung.
Die Reinheit der Berechnungen
In Haskell gehen wir davon aus, dass alle Berechnungen rein sind. Wären sie tatsächlich so, hätten wir keine Möglichkeit, irgendetwas auf dem Bildschirm auszugeben. Allgemein gesagt, reine Berechnungen sind so faul, dass es keinen einzigen reinen Grund gibt, etwas zu berechnen. Alle Berechnungen, die im Programm stattfinden, werden auf die eine oder andere Weise in die „unreine“ IO-Monade gezwungen.
Monaden sind eine Art, Berechnungen mit Effekten darzustellen. in Haskell. Eine Erklärung, wie sie funktionieren, sprengt den Rahmen dieses Beitrags. Eine gute und verständliche Beschreibung kann auf Englisch gelesen werden. .
Hier möchte ich anmerken, dass einige Monaden, wie IO, durch Compiler-Magie umgesetzt werden, während fast alle anderen programmatisch realisiert sind und alle Berechnungen darin rein sind.
Es gibt eine Vielzahl von Effekten, und für jeden gibt es eine eigene Monade. Dies ist eine sehr starke und schöne Theorie: Alle Monaden implementieren dasselbe Interface. Wir werden über die folgenden drei Monaden sprechen:
- Either e a — eine Berechnung, die einen Wert vom Typ a zurückgibt oder eine Ausnahme vom Typ e wirft. Das Verhalten dieser Monade ähnelt sehr der Arbeit mit Ausnahmen in imperativen Sprachen: Fehler können gefangen oder weitergegeben werden. Der Hauptunterschied besteht darin, dass die Monade vollständig logisch in der Standardbibliothek in demselben Haskell implementiert ist, während in imperativen Sprachen normalerweise Mechanismen des Betriebssystems verwendet werden.
- State s a — eine Berechnung, die einen Wert vom Typ a zurückgibt und Zugriff auf einen veränderbaren Zustand vom Typ s hat.
- Maybe a. Die Maybe-Monade drückt eine Berechnung aus, die jederzeit durch die Rückgabe von Nothing unterbrochen werden kann. Wir werden jedoch über die Implementierung der Klasse MonadPlus für den Typ Maybe sprechen, die den gegenteiligen Effekt ausdrückt: Dies ist eine Berechnung, die jederzeit durch die Rückgabe eines bestimmten Wertes unterbrochen werden kann.
Implementierung des Algorithmus
Wir haben zwei Datentypen, Graph a und Bigraph a b, wobei der erste Graphen mit Knoten darstellt, die mit Werten des Typs a gekennzeichnet sind, während der zweite bipartite Graphen mit Knoten auf der linken Seite darstellt, die mit Werten des Typs a gekennzeichnet sind, und Knoten auf der rechten Seite, die mit Werten des Typs b gekennzeichnet sind.
Dies sind keine Typen aus der Alga-Bibliothek. In Alga gibt es keine Darstellung für ungerichtete bipartite Graphen. Ich habe die Typen so gestaltet, um die Verständlichkeit zu verbessern.
Wir benötigen auch Hilfsfunktionen mit den folgenden Signaturen:
-- Liste der Nachbarn dieses Knotens.
neighbours :: Ord a => a -> Graph a -> [a]
-- Erstelle einen bipartiten Graphen aus dem Graphen und der Funktion, die für jeden Knoten
-- seine Partition und Markierung in der neuen Partition ausgibt, während konfliktreiche Kanten ignoriert werden.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Liste der Knoten im Graphen
vertexList :: Ord a => Graph a -> [a]
Die Signatur der Funktion, die wir schreiben werden, sieht so aus:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Es ist leicht zu erkennen, dass, wenn wir während der Tiefensuche eine konfliktreiche Kante gefunden haben, der ungerade Zyklus an der Spitze des Rekursionsstapels liegt. Daher müssen wir, um ihn wiederherzustellen, alles bis zum ersten Auftreten des letzten Knotens vom Rekursionsstapel abschneiden.
Wir implementieren die Tiefensuche und halten ein assoziatives Array von Partitionen für jeden Knoten. Der Rekursionsstapel wird automatisch durch die Implementierung der von uns gewählten Monad: Functor unterstützt; wir müssen lediglich alle Knoten auf dem Weg in das Resultat legen, das aus der rekursiven Funktion zurückgegeben wird.
Meine erste Idee war die Verwendung der Either-Monade, die anscheinend genau die Effekte realisiert, die wir benötigen. Die erste von mir geschriebene Implementierung war sehr nah an dieser Variante. Tatsächlich hatte ich irgendwann fünf verschiedene Implementierungen, und ich habe letztendlich auf eine andere umgeschwenkt.
Zunächst müssen wir ein assoziatives Array von Partitions-IDs unterstützen — das hat etwas mit State zu tun. Zweitens müssen wir die Fähigkeit haben anzuhalten, wenn ein Konflikt erkannt wird. Das kann entweder eine Monad für Either oder MonadPlus für Maybe sein. Der Hauptunterschied besteht darin, dass Either einen Wert zurückgeben kann, wenn die Berechnung nicht gestoppt wurde, während Maybe in diesem Fall nur Informationen darüber zurückgibt. Da wir im Falle eines Erfolgs (dies wird bereits im State gespeichert) keinen separaten Wert benötigen, wählen wir Maybe. Und in dem Moment, in dem wir die Effekte zweier Monaden kombinieren müssen, treten , die genau diese Effekte kombinieren.
Warum habe ich so einen komplexen Typ gewählt? Zwei Gründe. Erstens ist die Implementierung sehr ähnlich der imperativen. Zweitens müssen wir den Wert manipulieren, der im Falle eines Konflikts zurückgegeben wird, wenn wir aus der Rekursion zurückkehren, um einen ungeraden Zyklus wiederherzustellen, und das lässt sich viel einfacher in der Maybe-Monade durchführen.
So erhalten wir eine solche Implementierung.
{-# 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)
Der Block where ist das Herzstück des Algorithmus. Ich werde versuchen zu erklären, was darin passiert.
- inVertex ist Teil der Tiefensuche, in der wir den Knoten zum ersten Mal besuchen. Hier ordnen wir dem Knoten eine Partitionsnummer zu und starten onEdge für alle Nachbarn. Dies ist auch der Punkt, an dem wir den Aufrufstapel wiederherstellen: Wenn msum einen Wert zurückgegeben hat, hängen wir dort den Knoten v an.
- onEdge — das ist der Teil, in dem wir die Kante besuchen. Es wird für jede Kante zweimal aufgerufen. Hier überprüfen wir, ob der Knoten auf der anderen Seite besucht wurde, und besuchen ihn, wenn dies nicht der Fall ist. Wenn er besucht wurde, überprüfen wir, ob die Kante konfliktär ist. Wenn ja, geben wir den Wert zurück — die oberste Spitze des Rekursionsstapels, zu dem dann alle anderen Knoten bei der Rückkehr hinzugefügt werden.
- processVertex überprüft für jeden Knoten, ob er besucht wurde, und startet inVertex, wenn dies nicht der Fall ist.
- dfs startet processVertex auf allen Knoten.
Das wäre alles.
Die Geschichte des Begriffs INLINE
Der Begriff INLINE war in der ersten Implementierung des Algorithmus nicht vorhanden und tauchte erst später auf. Als ich versuchte, eine bessere Implementierung zu finden, stellte ich fest, dass die Version ohne INLINE auf bestimmten Graphen deutlich langsamer war. Angesichts der Tatsache, dass die Funktionen semantisch gleich arbeiten sollten, war ich darüber sehr überrascht. Noch seltsamer war es, dass es auf einem anderen Rechner mit einer anderen GHC-Version keinen merklichen Unterschied gab.
Nachdem ich eine Woche damit verbracht hatte, die Ausgabe von GHC Core zu lesen, konnte ich das Problem mit einer Zeile explizitem INLINE beheben. Irgendwann zwischen GHC 8.4.4 und GHC 8.6.5 hörte der Optimierer auf, dies eigenständig zu tun.
Ich hätte nicht mit so viel Schmutz beim Programmieren in Haskell gerechnet. Optimierer machen jedoch auch heutzutage gelegentlich Fehler, und es ist unsere Aufgabe, ihnen Hinweise zu geben. Zum Beispiel wissen wir hier, dass die Funktion inlinet werden sollte, weil sie in der imperativen Version inlinet ist, und das ist ein Grund, dem Compiler einen Hinweis zu geben.
Was kam danach?
Danach implementierte ich den Hopcroft-Karp-Algorithmus bereits mit anderen Monaden, und damit war das Programm abgeschlossen.
Dank Google Summer of Code habe ich praktische Erfahrung in funktionaler Programmierung gewonnen, die mir nicht nur geholfen hat, im nächsten Sommer ein Praktikum bei Jane Street zu bekommen (ich bin mir nicht sicher, wie bekannt dieser Ort selbst unter den Kennern von Habr ist, aber es ist einer der wenigen, wo man im Sommer funktionale Programmierung machen kann), sondern auch eine erstaunliche Welt der praktischen Anwendung dieses Paradigmas kennengelernt, die sich deutlich von meiner Erfahrung in traditionellen Sprachen unterscheidet.
Quelle: habr.com
