Letzten Sommer habe ich daran teilgenommen - ein Programm für Studenten von Google. Jedes Jahr wählen die Organisatoren mehrere Open-Source-Projekte aus, darunter von so namhaften Organisationen wie и . Google lädt Studierende aus aller Welt ein, an diesen Projekten zu arbeiten.
Als Teilnehmer am Google Summer of Code 2019 habe ich ein Projekt innerhalb der Bibliothek durchgeführt mit der Organisation , das die Haskell-Sprache entwickelt – eine der bekanntesten funktionalen Programmiersprachen. Alga ist eine Bibliothek, die repräsentiert Darstellung für Graphen in Haskell. Es wird beispielsweise verwendet in – eine Github-Bibliothek, die semantische Bäume, Aufruf- und Abhängigkeitsdiagramme basierend auf Code erstellt und diese vergleichen kann. Mein Projekt bestand darin, eine typsichere Darstellung für bipartite Graphen und Algorithmen für diese Darstellung hinzuzufügen.
In diesem Beitrag werde ich über meine Implementierung eines Algorithmus zur Überprüfung eines Diagramms auf Bipartitität in Haskell sprechen. Auch wenn der Algorithmus einer der grundlegendsten ist, erforderte die schöne Implementierung in einem funktionalen Stil mehrere Iterationen und erforderte ziemlich viel Arbeit. Aus diesem Grund habe ich mich für eine Implementierung mit Monadentransformatoren entschieden.
Über mich
Mein Name ist Vasily Alferov, ich studiere im vierten Jahr an der HSE in St. Petersburg. Zu Beginn des Blogs habe ich geschrieben и . Im Moment mache ich ein Praktikum bei in Norwegen, wo ich an Lösungsansätzen für das Problem arbeite . Zu meinen Interessen gehören parametrisierte Algorithmen und funktionale Programmierung.
Über die Implementierung des Algorithmus
Vorwort
Den Teilnehmern des Programms wird dringend empfohlen, zu bloggen. Sie stellten mir eine Plattform für den Blog zur Verfügung . Dieser Artikel ist eine Übersetzung , von mir dort im Juli auf Englisch geschrieben, mit einem kurzen Vorwort.
Pull Request mit dem betreffenden Code gefunden werden kann .
Die Ergebnisse meiner Arbeit können Sie hier nachlesen (auf Englisch) .
Dieser Beitrag soll den Leser mit den Grundkonzepten der funktionalen Programmierung vertraut machen, ich werde jedoch versuchen, mich zu gegebener Zeit an alle verwendeten Begriffe zu erinnern.
Überprüfen von Diagrammen auf Bipartitität
Ein Algorithmus zur Überprüfung eines Graphen auf Bipartitität wird in einem Kurs über Algorithmen normalerweise als einer der einfachsten Graphalgorithmen vorgestellt. Seine Idee ist einfach: Zuerst platzieren wir Eckpunkte irgendwie im linken oder rechten Teil, und wenn eine widersprüchliche Kante gefunden wird, behaupten wir, dass der Graph nicht zweiteilig ist.
Etwas detaillierter: Zuerst setzen wir einen Scheitelpunkt in den linken Teil. Offensichtlich müssen alle Nachbarn dieses Scheitelpunkts im rechten Lappen liegen. Außerdem müssen alle Nachbarn der Nachbarn dieses Scheitelpunkts im linken Lappen liegen und so weiter. Wir weisen Scheitelpunkten weiterhin Anteile zu, solange es in der verbundenen Komponente des Scheitelpunkts, mit dem wir begonnen haben, noch Scheitelpunkte gibt, denen wir keine Nachbarn zugewiesen haben. Anschließend wiederholen wir diese Aktion für alle angeschlossenen Komponenten.
Wenn es eine Kante zwischen Eckpunkten gibt, die in dieselbe Partition fallen, ist es nicht schwierig, einen ungeraden Zyklus im Graphen zu finden, was in einem bipartiten Graphen allgemein bekannt (und ganz offensichtlich) unmöglich ist. Andernfalls haben wir eine korrekte Partition, was bedeutet, dass der Graph zweiteilig ist.
Typischerweise wird dieser Algorithmus mit implementiert oder . In imperativen Sprachen wird normalerweise die Tiefensuche verwendet, da sie etwas einfacher ist und keine zusätzlichen Datenstrukturen erfordert. Ich habe mich auch für die Tiefensuche entschieden, da sie traditioneller ist.
So kamen wir zu folgendem Schema. Wir durchqueren die Eckpunkte des Diagramms mithilfe der Tiefensuche und weisen ihnen Anteile zu, wobei wir die Anzahl der Anteile ändern, während wir uns entlang der Kante bewegen. Wenn wir versuchen, einem Scheitelpunkt, dem bereits ein Anteil zugewiesen wurde, einen Anteil zuzuweisen, können wir mit Sicherheit sagen, dass der Graph nicht zweiteilig ist. Sobald allen Eckpunkten ein Anteil zugewiesen ist und wir uns alle Kanten angeschaut haben, haben wir eine gute Aufteilung.
Reinheit der Berechnungen
In Haskell gehen wir davon aus, dass alle Berechnungen korrekt sind sauber Wenn dies jedoch tatsächlich der Fall wäre, hätten wir keine Möglichkeit, etwas auf dem Bildschirm auszudrucken. Überhaupt, sauber Berechnungen sind so faul, dass es keine gibt sauber Gründe, etwas zu berechnen. Alle im Programm vorkommenden Berechnungen werden irgendwie erzwungen "unrein" Monade IO.
Monaden sind eine Möglichkeit, Berechnungen darzustellen Auswirkungen in Haskell. Es würde den Rahmen dieses Beitrags sprengen, zu erklären, wie sie funktionieren. Eine gute und klare Beschreibung kann auf Englisch gelesen werden .
Hier möchte ich darauf hinweisen, dass einige Monaden, wie z. B. IO, zwar durch Compiler-Magie implementiert werden, fast alle anderen jedoch in Software implementiert sind und alle darin enthaltenen Berechnungen rein sind.
Es gibt viele Effekte und jeder hat seine eigene Monade. Dies ist eine sehr starke und schöne Theorie: Alle Monaden implementieren dieselbe Schnittstelle. Wir werden über die folgenden drei Monaden sprechen:
- Entweder ist ea eine Berechnung, die einen Wert vom Typ a zurückgibt oder eine Ausnahme vom Typ e auslöst. Das Verhalten dieser Monade ist der Ausnahmebehandlung in imperativen Sprachen sehr ähnlich: Fehler können abgefangen oder weitergegeben werden. Der Hauptunterschied besteht darin, dass die Monade in der Standardbibliothek in Haskell vollständig logisch implementiert ist, während imperative Sprachen normalerweise Betriebssystemmechanismen verwenden.
- State sa ist eine Berechnung, die einen Wert vom Typ a zurückgibt und Zugriff auf einen veränderlichen Status vom Typ s hat.
- Vielleicht ein. 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 MonadPlus-Klasse für den Typ Maybe sprechen, die den gegenteiligen Effekt zum Ausdruck bringt: Es handelt sich um eine Berechnung, die jederzeit durch die Rückgabe eines bestimmten Werts unterbrochen werden kann.
Implementierung des Algorithmus
Wir haben zwei Datentypen, Graph a und Bigraph ab, von denen der erste Graphen mit Scheitelpunkten darstellt, die mit Werten vom Typ a beschriftet sind, und der zweite bipartite Graphen mit linken Scheitelpunkten darstellt, die mit Werten vom Typ a und rechts beschriftet sind -Seitenscheitelpunkte mit Werten vom Typ b beschriftet.
Dies sind keine Typen aus der Alga-Bibliothek. Alga verfügt über keine Darstellung für ungerichtete bipartite Graphen. Der Übersichtlichkeit halber habe ich die Typen so gestaltet.
Wir benötigen außerdem Hilfsfunktionen mit den folgenden Signaturen:
-- Список соседей данной вершины.
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)Es ist leicht zu erkennen, dass, wenn wir während der Tiefensuche eine widersprüchliche Kante gefunden haben, der ungerade Zyklus oben auf dem Rekursionsstapel liegt. Um es wiederherzustellen, müssen wir daher alles vom Rekursionsstapel bis zum ersten Vorkommen des letzten Scheitelpunkts abschneiden.
Wir implementieren die Tiefensuche, indem wir für jeden Scheitelpunkt ein assoziatives Array von Anteilsnummern pflegen. Der Rekursionsstapel wird automatisch durch die Implementierung der Functor-Klasse der von uns gewählten Monade verwaltet: Wir müssen lediglich alle Eckpunkte aus dem Pfad in das von der rekursiven Funktion zurückgegebene Ergebnis einfügen.
Meine erste Idee war, die Entweder-Monade zu verwenden, die genau die Effekte zu erzielen scheint, die wir brauchen. Die erste Implementierung, die ich geschrieben habe, kam dieser Option sehr nahe. Tatsächlich hatte ich zu einem Zeitpunkt fünf verschiedene Implementierungen und entschied mich schließlich für eine andere.
Zuerst müssen wir ein assoziatives Array von Freigabebezeichnern verwalten – hier geht es um State. Zweitens müssen wir in der Lage sein, anzuhalten, wenn ein Konflikt erkannt wird. Dies kann entweder „Monad“ für „Entweder“ oder „MonadPlus“ für „Vielleicht“ sein. Der Hauptunterschied besteht darin, dass Both einen Wert zurückgeben kann, wenn die Berechnung nicht gestoppt wurde, und Maybe in diesem Fall nur Informationen darüber zurückgibt. Da wir für den Erfolg keinen separaten Wert benötigen (er ist bereits in State gespeichert), wählen wir Maybe. Und in dem Moment, in dem wir die Wirkungen zweier Monaden kombinieren müssen, kommen sie zum Vorschein , die genau diese Effekte kombinieren.
Warum habe ich mich für einen so komplexen Typ entschieden? Zwei Gründe. Erstens stellt sich heraus, dass die Implementierung dem Imperativ sehr ähnlich ist. Zweitens müssen wir den Rückgabewert im Falle eines Konflikts manipulieren, wenn wir von der Rekursion zurückkehren, um die ungerade Schleife wiederherzustellen, was in der Maybe-Monade viel einfacher ist.
Somit erhalten wir diese 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 <- 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)
Der Where-Block ist der Kern des Algorithmus. Ich werde versuchen zu erklären, was darin passiert.
- inVertex ist der Teil der Tiefensuche, bei dem wir den Scheitelpunkt zum ersten Mal besuchen. Hier weisen wir dem Scheitelpunkt eine Freigabenummer zu und führen onEdge für alle Nachbarn aus. Hier stellen wir auch den Aufrufstapel wieder her: Wenn msum einen Wert zurückgegeben hat, verschieben wir Vertex v dorthin.
- onEdge ist der Teil, in dem wir den Rand besuchen. Es wird für jede Kante zweimal aufgerufen. Hier prüfen wir, ob der Scheitelpunkt auf der anderen Seite besucht wurde, und besuchen ihn, wenn nicht. Bei einem Besuch prüfen wir, ob die Kante einen Konflikt aufweist. Wenn dies der Fall ist, geben wir den Wert zurück – ganz oben im Rekursionsstapel, wo dann alle anderen Scheitelpunkte bei der Rückgabe platziert werden.
- ProcessVertex prüft für jeden Vertex, ob er besucht wurde, und führt inVertex darauf aus, wenn nicht.
- dfs führt ProcessVertex auf allen Scheitelpunkten aus.
Das ist alles.
Geschichte des Wortes INLINE
Das Wort INLINE kam in der ersten Implementierung des Algorithmus nicht vor; es tauchte später auf. Als ich versuchte, eine bessere Implementierung zu finden, stellte ich fest, dass die Nicht-INLINE-Version in einigen Diagrammen merklich langsamer war. Wenn man bedenkt, dass die Funktionen semantisch gleich funktionieren sollten, hat mich das sehr überrascht. Noch seltsamer: Auf einem anderen Rechner mit einer anderen GHC-Version gab es keinen merklichen Unterschied.
Nachdem ich eine Woche damit verbracht hatte, die GHC Core-Ausgabe 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 selbstständig zu tun.
Ich hatte nicht erwartet, bei der Haskell-Programmierung auf solchen Schmutz zu stoßen. Allerdings machen Optimierer auch heute noch manchmal Fehler und es ist unsere Aufgabe, ihnen Hinweise zu geben. Hier wissen wir beispielsweise, dass die Funktion inline sein sollte, da sie in der imperativen Version inline ist, und dies ist ein Grund, dem Compiler einen Hinweis zu geben.
Was ist als nächstes passiert?
Dann habe ich den Hopcroft-Karp-Algorithmus mit anderen Monaden implementiert, und das war das Ende des Programms.
Dank Google Summer of Code habe ich praktische Erfahrung in der funktionalen Programmierung gesammelt, was mir nicht nur geholfen hat, im darauffolgenden Sommer ein Praktikum bei Jane Street zu bekommen (ich bin mir nicht sicher, wie bekannt dieser Ort selbst bei Habrs sachkundigem Publikum ist, aber es ist einer). (einer der wenigen, in denen man sich im Sommer mit funktionaler Programmierung befassen kann), führte mich aber auch in die wunderbare Welt der praktischen Anwendung dieses Paradigmas ein, die sich deutlich von meiner Erfahrung mit traditionellen Sprachen unterscheidet.
Source: habr.com