W zeszłym lecie brałem udział w — programie dla studentów od firmy Google. Co roku organizatorzy wybierają kilka projektów Open Source, w tym od takich znanych organizacji jak i . Aby pracować nad tymi projektami, Google zaprasza studentów z całego świata.
Jako uczestnik Google Summer of Code 2019 realizowałem projekt w ramach biblioteki z organizacją , zajmującą się rozwojem języka Haskell — jednego z najbardziej znanych języków programowania funkcyjnego. Alga to biblioteka, która przedstawia reprezentacje grafów w Haskellu. Jest używana, na przykład, w — bibliotece firmy Github, która buduje przy pomocy kodu drzewa semantyczne, grafy wywołań i zależności oraz potrafi je porównywać. Mój projekt polegał na dodaniu tam typowo bezpiecznej reprezentacji dla grafów dwudzielnych oraz algorytmów dla tej reprezentacji.
W poście opowiem o mojej implementacji algorytmu sprawdzania grafu na dwudzielność w Haskellu. Mimo że algorytm jest jednym z najprostszych, jego piękna implementacja w stylu funkcyjnym zajęła mi kilka iteracji i wymagała dość dużo pracy. W rezultacie zdecydowałem się na implementację z transformatorami monad.
O mnie
Nazywam się Wasilij Alfiorow, jestem studentem czwartego roku w Petersburskiej Wyższej Szkole Ekonomicznej. Wcześniej na blogu pisałem i . W tym momencie odbywam staż na w Norwegii, gdzie zajmuję się podejściami do zadania . Moje zainteresowania obejmują algorytmy parametryzowane oraz programowanie funkcyjne.
O implementacji algorytmu
Wstęp
Studentom biorącym udział w programie zdecydowanie zaleca się prowadzenie bloga. Dostałem platformę do bloga . Ten artykuł to tłumaczenie , które napisałem tam w lipcu po angielsku, z krótkim wprowadzeniem.
Pull Request z kodem, o którym mowa, można znaleźć .
O wynikach mojej pracy można przeczytać (w języku angielskim) .
Post zakłada zaznajomienie czytelnika z podstawowymi pojęciami programowania funkcyjnego, choć postaram się przypomnieć wszystkie używane terminy, gdy przyjdzie na nie czas.
Sprawdzanie grafów na dwudzielność
Algorytm sprawdzania, czy graf jest dwudzielny, zwykle jest przedstawiany w kursach algorytmów jako jeden z najprostszych algorytmów grafowych. Jego idea jest prosta: najpierw w jakiś sposób umieszczamy wierzchołki w lewej lub prawej części, a przy wykryciu konfliktowej krawędzi stwierdzamy, że graf nie jest dwudzielny.
Nieco dokładniej: najpierw umieszczamy jakiś wierzchołek w lewej części. Oczywiście wszyscy sąsiedzi tego wierzchołka muszą znajdować się w prawej części. Następnie wszyscy sąsiedzi sąsiadów tego wierzchołka muszą znajdować się w lewej części itd. Kontynuujemy przypisywanie wierzchołków do części, dopóki w spójnym składniku wierzchołka, od którego zaczęliśmy, są jeszcze wierzchołki, którym nie przypisano sąsiadów. Następnie powtarzamy tę czynność dla wszystkich składników spójności.
Jeśli istnieje krawędź między wierzchołkami, które znajdują się w tej samej części, nietrudno znaleźć w grafie nieparzysty cykl, co jest powszechnie wiadomo (i dość oczywiste), że nie może mieć miejsca w grafie dwudzielnym. W przeciwnym razie mamy poprawny podział na części, co oznacza, że graf jest dwudzielny.
Zwykle ten algorytm realizuje się za pomocą lub . W językach imperatywnych zazwyczaj stosuje się przeszukiwanie w głąb, jako nieco prostsze i nieskrzyniające dodatkowych struktur danych. Wybrałem też przeszukiwanie w głąb jako bardziej tradycyjne.
W ten sposób doszliśmy do następującego schematu. Przechodzimy przez wierzchołki grafu za pomocą przeszukiwania w głąb i przypisujemy im części, zmieniając numer części podczas przechodzenia po krawędzi. Jeśli próbujemy przypisać część wierzchołkowi, któremu już przypisano część, można śmiało stwierdzić, że graf nie jest dwudzielny. W momencie, gdy wszystkim wierzchołkom przypisano część i zbadaliśmy wszystkie krawędzie, mamy dobry podział.
Czystość obliczeń
W Haskellu zakładamy, że wszystkie obliczenia są czyste. Jednak gdyby tak było w rzeczywistości, nie mielibyśmy możliwości wyświetlenia czegokolwiek na ekranie. W ogóle, czyste obliczenia są tak leniwe, że nie ma żadnego czystego powodu, by coś obliczać. Wszystkie obliczenia, które odbywają się w programie, są w jakiś sposób wymuszone w «nieczystej» monadzie IO.
Monady to sposób reprezentacji obliczeń z efektami w Haskellu. Wyjaśnienie, jak działają, wykracza poza ramy tego posta. Dobre i klarowne opisy można przeczytać po angielsku .
Chcę zauważyć, że podczas gdy niektóre monady, takie jak IO, są zaimplementowane za pomocą magii kompilatora, prawie wszystkie inne są realizowane programowo, a wszystkie obliczenia w nich są czyste.
Efektów jest bardzo wiele i dla każdego stworzono swoją monadę. To bardzo silna i piękna teoria: wszystkie monady implementują ten sam interfejs. Będziemy mówić o następujących trzech monadach:
- Either e a — obliczenie, które zwraca wartość typu a lub rzuca wyjątek typu e. Zachowanie tej monady jest bardzo podobne do pracy z wyjątkami w językach imperatywnych: błędy mogą być przechwytywane lub przenoszone dalej. Główna różnica polega na tym, że monada jest w pełni logicznie zaimplementowana w standardowej bibliotece tego samego Haskella, podczas gdy w językach imperatywnych zazwyczaj używa się mechanizmów systemu operacyjnego.
- State s a — obliczenie, które zwraca wartość typu a i ma dostęp do zmiennego stanu typu s.
- Maybe a. Monada Maybe wyraża obliczenie, które może zostać przerwane zwrotem Nothing w dowolnym momencie. Jednak będziemy mówić o implementacji klasy MonadPlus dla typu Maybe, wyrażającej przeciwny efekt: to obliczenie, które może być przerwane zwrotem konkretnej wartości w dowolnym momencie.
Implementacja algorytmu
Mamy dwa typy danych, Graph a i Bigraph a b, z których pierwszy reprezentuje grafy z węzłami oznaczonymi wartościami typu a, a drugi reprezentuje grafy dwudzielne z węzłami lewej części oznaczonymi wartościami typu a i węzłami prawej części oznaczonymi wartościami typu b.
To nie są typy z biblioteki Alga. W Alga nie ma przedstawienia dla nieskierowanych grafów dwudzielnych. Typy zrobiłem takie dla przejrzystości.
Potrzebujemy również funkcji pomocniczych o następujących sygnaturach:
-- Lista sąsiednich wierzchołków.
neighbours :: Ord a => a -> Graph a -> [a]
-- Zbudować graf dwudzielny na podstawie grafu i funkcji, która dla każdego wierzchołka
-- zwraca jego część i znacznik w nowej części, ignorując konfliktowe krawędzie.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Lista wierzchołków w grafie
vertexList :: Ord a => Graph a -> [a]
Sygnatura funkcji, którą będziemy pisać, wygląda następująco:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Łatwo zauważyć, że jeśli podczas przeszukiwania w głąb znaleźliśmy konfliktową krawędź, nieparzysta pętla znajduje się na szczycie stosu rekurencji. W związku z tym, aby ją odtworzyć, musimy odciąć od stosu rekursji wszystko do pierwszego wystąpienia ostatniego wierzchołka.
Zaimplementujemy przeszukiwanie w głąb, utrzymując asocjacyjny zbiór numerów części dla każdego wierzchołka. Stos rekurencji będzie automatycznie utrzymywany poprzez implementację klasy Functor wybranej przez nas monady: wystarczy umieścić wszystkie wierzchołki z ścieżki w wyniku zwracanym z funkcji rekurencyjnej.
Moim pierwszym pomysłem było użycie monady Either, która zdaje się realizować efekty, których potrzebujemy. Moja pierwsza implementacja była bardzo bliska tej wersji. W rzeczywistości miałem pięć różnych implementacji w pewnym momencie, a ostatecznie zatrzymałem się na innej.
Po pierwsze, musimy utrzymać asocjacyjny zbiór identyfikatorów części — to coś związanego z State. Po drugie, musimy móc zatrzymać się w przypadku wykrycia konfliktu. Może to być albo Monad dla Either, albo MonadPlus dla Maybe. Główna różnica polega na tym, że Either może zwracać wartość w przypadku, gdy obliczenie nie zostało zatrzymane, podczas gdy Maybe w takim przypadku zwraca tylko informację o tym. Ponieważ nie potrzebujemy oddzielnej wartości w przypadku sukcesu (już jest przechowywana w State), wybieramy Maybe. A w momencie, gdy musimy łączyć efekty dwóch monad, wystają , które właśnie łączą te efekty.
Dlaczego wybrałem taki skomplikowany typ? Dwie przyczyny. Po pierwsze, realizacja jest bardzo zbliżona do imperatywnej. Po drugie, musimy manipulować wartością zwracaną w przypadku konfliktu, przy powrocie z rekurencji w celu odtworzenia nieparzystego cyklu, a to dużo łatwiej zrobić w monadzie Maybe.
W ten sposób uzyskujemy taką realizację.
{-# 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)
Blok where jest rdzeniem algorytmu. Postaram się wyjaśnić, co wewnątrz niego się dzieje.
- inVertex to część przeszukiwania w głąb, w której odwiedzamy wierzchołek po raz pierwszy. Tutaj przypisujemy wierzchołkowi numer części i uruchamiamy onEdge dla wszystkich sąsiadów. To również miejsce, w którym odtwarzamy stos wywołań: jeśli msum zwróciło wartość, dodajemy wierzchołek v.
- onEdge — to część, w której odwiedzamy krawędź. Jest wywoływana dwa razy dla każdej krawędzi. Tutaj sprawdzamy, czy wierzchołek z drugiej strony został odwiedzony, i odwiedzamy go, jeśli nie. Jeśli został już odwiedzony, sprawdzamy, czy krawędź jest konfliktowa. Jeśli jest, zwracamy wartość — samą górę stosu rekurencji, na którą następnie podczas zwrotu nałożą się wszystkie pozostałe wierzchołki.
- processVertex sprawdza dla każdego wierzchołka, czy został odwiedzony, i uruchamia na nim inVertex, jeśli nie.
- dfs uruchamia processVertex dla wszystkich wierzchołków.
To wszystko.
Historia słowa INLINE
Słowa INLINE nie było w pierwszej realizacji algorytmu, pojawiło się później. Gdy próbowałem znaleźć lepszą implementację, odkryłem, że w przypadku niektórych grafów wersja bez INLINE działa zauważalnie wolniej. Mimo że semantycznie funkcje powinny działać identycznie, bardzo mnie to zdziwiło. Jeszcze bardziej dziwne było to, że na innym komputerze z inną wersją GHC nie zauważyłem żadnej różnicy.
Po tygodniu spędzonym na czytaniu wyjścia GHC Core udało mi się naprawić problem jedną linią z użyciem wyraźnego INLINE. W pewnym momencie między GHC 8.4.4 a GHC 8.6.5 optymalizator przestał robić to samodzielnie.
Nie spodziewałem się napotkać takiego bałaganu w programowaniu w Haskellu. Niemniej jednak optymalizatory nawet w dzisiejszych czasach czasami popełniają błędy, a naszą rolą jest dostarczanie im wskazówek. Na przykład tutaj wiemy, że funkcja powinna być zainlinowana, ponieważ jest zainlinowana w wersji imperatywnej, i to jest powód, by dać kompilatorowi wskazówkę.
Co było dalej?
Potem zaimplementowałem algorytm Hopcrofta-Karpa już z innymi monadami, i na tym program się zakończył.
Dzięki Google Summer of Code zdobyłem praktyczne doświadczenie w programowaniu funkcyjnym, które nie tylko pomogło mi przejść na staż w Jane Street latem, ale również wprowadziło mnie w niesamowity świat zastosowania tej paradygmatyki w praktyce, wyraźnie różniący się od mojego doświadczenia w tradycyjnych językach.
Źródło: habr.com
