Letzten Sommer habe ich an — einem Programm für Studenten von Google, teilgenommen. Jährlich wählen die Organisatoren mehrere Open Source-Projekte aus, darunter solche bekannter Organisationen wie und . Für die Arbeit an diesen Projekten lädt Google Studenten aus der ganzen Welt ein.
Als Teilnehmer von Google Summer of Code 2019 arbeitete ich an einem Projekt im Rahmen der Bibliothek in Zusammenarbeit mit der Organisation , die sich mit der Weiterentwicklung der Programmiersprache Haskell — einer der bekanntesten funktionalen Programmiersprachen — beschäftigt. Alga ist eine Bibliothek, die Darstellungen für Graphen in Haskell bietet. Sie wird beispielsweise in der -Bibliothek von Github verwendet, die aus Code semantische Bäume und Aufruf- sowie 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 meine Implementierung eines Algorithmus zur Überprüfung der Zweifarbigkeit von Graphen in Haskell vorstellen. Obwohl der Algorithmus einer der grundlegendsten ist, benötigte meine hübsche Implementierung im funktionalen Stil mehrere Iterationen und viel Arbeit. Letztendlich entschied ich mich für eine Implementierung mit Monaden-Transformern.
Über mich
Mein Name ist Wladimir Alfjorow, ich bin Student im vierten Jahr an der Hochschule für Wirtschaft in St. Petersburg. Zuvor habe ich in meinem Blog und . Momentan bin ich im Praktikum an der in Norwegen, wo ich mich mit Ansätzen für das Thema beschäftige. In meinem Interessensbereich liegen parametrisierbare Algorithmen und funktionale Programmierung.
Zur Implementierung des Algorithmus
Vorwort
den Teilnehmern des Programms wird dringend empfohlen, einen Blog zu führen. Für meinen Blog wurde mir die Plattform zur Verfügung gestellt. Dieser Artikel ist eine Übersetzung , die ich dort im Juli auf Englisch verfasst habe, mit einem kurzen Vorwort.
Der Pull Request mit dem besprochenen Code ist zu finden .
Über die Ergebnisse meiner Arbeit kann man (auf Englisch) lesen. .
Dieser Beitrag vermittelt dem Leser grundlegende Konzepte der funktionalen Programmierung, wobei ich versuchen werde, alle verwendeten Begriffe zum richtigen Zeitpunkt zu erläutern.
Überprüfung von Graphen auf Bipolarität
Der Algorithmus zur Überprüfung, ob ein Graph bipartit ist, wird im Algorithmenkurs oft als einer der einfachsten Graphalgorithmen behandelt. Die Idee dahinter ist einfach: Zuerst ordnen wir die Knoten irgendwie einer linken oder rechten Partition zu. Wenn wir dann eine widersprüchliche Kante entdecken, bestätigen wir, dass der Graph nicht bipartit ist.
Ein bisschen genauer: Zuerst ordnen wir einen bestimmten Knoten der linken Partition zu. Offensichtlich müssen alle Nachbarn dieses Knotens in der rechten Partition liegen. Weiterhin müssen alle Nachbarn der Nachbarn dieses Knotens in der linken Partition liegen, und so weiter. Wir setzen die Zuweisung von Knoten zu Partitionen fort, solange es in der Zusammenhangskomponente des Knotens, mit dem wir begonnen haben, noch Knoten gibt, deren Nachbarn wir nicht zugewiesen haben. Dann wiederholen wir diese Aktion für alle Zusammenhangskomponenten.
Wenn eine Kante zwischen Knoten, die in dasselbe Teil gesetzt wurden, existiert, ist es nicht schwierig, im Graphen einen ungeraden Zyklus zu finden, was allgemein bekannt ist und in einem bipartiten Graphen offensichtlich unmöglich ist. Ansonsten haben wir eine korrekte Partitionierung in Teile, was bedeutet, dass der Graph bipartit ist.
In der Regel wird dieser Algorithmus mit Hilfe von 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.
Somit sind wir zu folgendem Schema gekommen. Wir durchlaufen die Knoten des Graphen mittels Tiefensuche und weisen ihnen Teile zu, wobei wir die Nummer des Teils beim Überqueren einer Kante ändern. Wenn wir versuchen, einem Knoten, der bereits einen Teil zugewiesen bekommen hat, einen weiteren Teil zuzuweisen, können wir mit Sicherheit sagen, dass der Graph nicht bipartit ist. In dem Moment, in dem allen Knoten ein Teil zugewiesen wurde und wir alle Kanten betrachtet haben, haben wir eine gute Partitionierung.
Reinheit der Berechnungen
In Haskell nehmen wir an, dass alle Berechnungen rein sind. Wenn dem so wäre, hätten wir überhaupt keine Möglichkeit, etwas auf dem Bildschirm auszugeben. sauber Berechnungen sind so faul, dass es keinen einzigen Grund gibt, etwas zu berechnen. sauberen Alle Berechnungen, die im Programm stattfinden, werden irgendwie in „unsauberen“ IO-Monaden gezwungen.
Monaden sind ein Weg, Berechnungen mit Effekten in Haskell darzustellen. Eine Erklärung, wie sie funktionieren, sprengt den Rahmen dieses Beitrags. Eine gute und verständliche Beschreibung findet sich auf Englisch. .
Ich möchte anmerken, dass während einige Monaden, wie IO, durch Compiler-Magie implementiert werden, fast alle anderen programmatisch umgesetzt sind und alle Berechnungen darin rein sind.
Es gibt viele Arten 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 nächsten drei Monaden sprechen:
- Entweder e a — eine Berechnung, die einen Wert vom Typ a zurückgibt oder eine Ausnahme vom Typ e auslöst. Das Verhalten dieses Monads ähnelt stark der Arbeit mit Ausnahmen in imperativen Sprachen: Fehler können aufgefangen oder weitergegeben werden. Der Hauptunterschied besteht darin, dass der Monad vollständig logisch in der Standardbibliothek in demselben Haskell implementiert ist, während in imperativen Sprachen in der Regel 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. Der Maybe-Monad 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: eine Berechnung, die jederzeit durch die Rückgabe eines bestimmten Wertes unterbrochen werden kann.
Implementierung des Algorithmus
Wir bieten zwei Datentypen an: Graph a und Bigraph a b. Der erste repräsentiert Graphen mit Knoten, die mit Werten des Typs a beschriftet sind, während der zweite bipartite Graphen darstellt, bei denen die Knoten der linken Seite mit Werten des Typs a und die Knoten der rechten Seite mit Werten des Typs b beschriftet sind.
Diese Typen stammen nicht aus der Alga-Bibliothek. In Alga gibt es keine Repräsentation für ungerichtete bipartite Graphen. Ich habe die Typen zur Veranschaulichung so erstellt.
Wir benötigen außerdem Hilfsfunktionen mit den folgenden Signaturen:
-- Liste der Nachbarn des gegebenen Knotens.
neighbours :: Ord a => a -> Graph a -> [a]
-- Erstelle einen bipartiten Graphen aus dem Graphen und einer Funktion, die für jeden Knoten
-- dessen Anteil und Markierung im neuen Anteil ausgibt, wobei konfliktbehaftete 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 konfliktträchtige Kante gefunden haben, der ungerade Zyklus oben im Rekursionsstapel liegt. Um diesen wiederherzustellen, müssen wir alles bis zum ersten Auftreten des letzten Knotens vom Rekursionsstapel abtrennen.
Wir implementieren die Tiefensuche, indem wir für jeden Knoten ein assoziatives Array von Teilnummern führen. Der Rekursionsstapel wird automatisch durch die Implementierung der von uns gewählten Monad-Klasse unterstützt: Wir müssen nur alle Knoten des Pfades in das Ergebnis einfügen, das aus der rekursiven Funktion zurückgegeben wird.
Meine erste Idee war, die Monad Either zu verwenden, die genau die Effekte zu realisieren scheint, die wir benötigen. Meine erste Implementierung war sehr nahe an dieser Variante. Tatsächlich hatte ich irgendwann fünf verschiedene Implementierungen, und letztendlich entschied ich mich für eine andere.
Zunächst müssen wir ein assoziatives Array von Share-IDs verwalten – das gehört zum State. Zweitens müssen wir in der Lage sein, im Falle eines Konflikts anzuhalten. 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 keinen separaten Wert im Erfolgsfall benötigen (dieser ist bereits im State gespeichert), wählen wir Maybe. Und in dem Moment, in dem wir die Effekte von zwei Monaden kombinieren müssen, tauchen , die genau diese Effekte kombinieren, auf.
Warum habe ich so einen komplexen Typ gewählt? Zwei Gründe. Erstens, die Implementierung ähnelt stark der imperativen. Zweitens müssen wir mit dem Wert, der im Falle eines Konflikts zurückgegeben wird, bei der Rückkehr aus der Rekursion umgehen, um den ungeraden Zyklus wiederherzustellen, und das lässt sich in der Maybe-Monade viel einfacher bewerkstelligen.
So erhalten wir diese Implementierung.
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE ScopedTypeVariables #-}
data Teil = LinkerTeil | RechterTeil
andererTeil :: Teil -> Teil
andererTeil LinkerTeil = RechterTeil
andererTeil RechterTeil = LinkerTeil
typ TeilMap a = Map.Map a Teil
typ UngeradeCycle a = [a]
toEither :: Ord a => TeilMap a -> a -> Either a a
toEither m v = case fromJust (v `Map.lookup` m) of
LinkerTeil -> Left v
RechterTeil -> Right v
typ TeilMonad a = MaybeT (State (TeilMap a)) [a]
detectParts :: forall a. Ord a => Graph a -> Either (UngeradeCycle a) (Bigraph a a)
detectParts g = case runState (runMaybeT dfs) Map.empty of
(Just c, _) -> Left $ ungeradeCycle c
(Nothing, m) -> Right $ toBipartiteWith (toEither m) g
where
inVertex :: Teil -> a -> TeilMonad a
inVertex p v = ((:) v) <$ do modify $ Map.insert v p
let q = andererTeil p
msum [ onEdge q u | u a -> TeilMonad a
onEdge p v = do m inVertex p v
Just q -> do guard (q /= p)
return [v]
processVertex :: a -> TeilMonad a
processVertex v = do m <- get
guard (v `Map.notMember` m)
inVertex LinkerTeil v
dfs :: TeilMonad a
dfs = msum [ processVertex v | v [a]
ungeradeCycle c = tail (dropWhile ((/=) last c) c)
Ein Block ist der Kern des Algorithmus. Ich werde versuchen zu erklären, was darin passiert.
- inVertex ist der Teil der Tiefensuche, in dem wir einen Gipfel zum ersten Mal besuchen. Hier weisen wir dem Gipfel eine Teilnummer zu und starten onEdge für alle Nachbarn. Außerdem ist dies der Ort, an dem wir den Aufrufstack wiederherstellen: Wenn msum einen Wert zurückgibt, hängen wir dort den Gipfel v an.
- onEdge ist der Abschnitt, in dem wir die Kante besuchen. Sie wird zweimal für jede Kante aufgerufen. Hier überprüfen wir, ob der Gipfel von der anderen Seite besucht wurde, und besuchen ihn, wenn dies nicht der Fall ist. Wenn er bereits besucht wurde, prüfen wir, ob die Kante konfliktträchtig ist. Wenn ja, geben wir den Wert zurück – den obersten Teil des Rekursionsstapels, an den dann alle anderen Gipfel beim Zurückkehren angehängt werden.
- processVertex überprüft für jeden Gipfel, ob er besucht wurde, und startet inVertex, wenn dies nicht der Fall ist.
- dfs startet processVertex für alle Gipfel.
Das ist alles.
Die Geschichte des Wortes INLINE
Das Wort INLINE war in der ersten Implementierung des Algorithmus nicht vorhanden; es kam später hinzu. Als ich versuchte, eine bessere Implementierung zu finden, stellte ich fest, dass die Version ohne INLINE in einigen Graphen deutlich langsamer arbeitete. Angesichts der Tatsache, dass die Funktionen semantisch gleich arbeiten sollten, war ich darüber sehr erstaunt. Umso merkwürdiger, dass auf einem anderen Rechner mit einer anderen Version von GHC keinerlei Unterschiede bemerkbar waren.
Nachdem ich eine Woche damit verbracht hatte, die Ausgabe von GHC Core zu lesen, konnte ich das Problem mit einem einzigen Befehl und explizitem INLINE beheben. Irgendwann zwischen GHC 8.4.4 und GHC 8.6.5 hörte der Optimierer auf, dies von selbst zu erledigen.
Ich hatte nicht erwartet, auf so viel Unordnung beim Programmieren in Haskell zu stoßen. Dennoch machen Optimierer selbst heutzutage manchmal Fehler, und es ist unsere Aufgabe, ihnen Hinweise zu geben. Zum Beispiel wissen wir hier, dass die Funktion inlinet werden sollte, da sie in der imperativen Version bereits inlined ist, und das ist ein Grund, dem Compiler einen Hinweis zu geben.
Was geschah dann?
Dann implementierte ich den Hopcroft-Karp-Algorithmus mit anderen Monaden, und damit war das Programm abgeschlossen.
Dank Google Summer of Code habe ich praktische Erfahrungen im funktionalen Programmieren gesammelt, die mir nicht nur geholfen haben, ein Praktikum bei Jane Street in der nächsten Sommerperiode zu bekommen (ich bin mir nicht sicher, wie bekannt dieser Ort selbst unter der geekigen Community von Habr ist, aber es ist einer der wenigen Orte, wo man im Sommer funktionales Programmieren praktizieren kann), sondern haben mich auch mit der faszinierenden Welt der praktischen Anwendung dieser Paradigmen vertraut gemacht, die sich erheblich von meinen Erfahrungen mit traditionellen Programmiersprachen unterscheidet.
Quelle: habr.com
