Zeszłego lata brałam w nich udział - program dla studentów od Google. Co roku organizatorzy wybierają kilka projektów Open Source, m.in. od tak znanych organizacji jak и . Google zaprasza studentów z całego świata do pracy nad tymi projektami.
Jako uczestnik Google Summer of Code 2019 realizowałem projekt w bibliotece z organizacją , która rozwija język Haskell – jeden z najsłynniejszych języków programowania funkcjonalnego. Alga to biblioteka, która reprezentuje reprezentacja wykresów w Haskell. Używa się go np — biblioteka Github, która buduje drzewa semantyczne, wykresy wywołań i zależności w oparciu o kod i może je porównywać. Mój projekt polegał na dodaniu bezpiecznej dla typu reprezentacji grafów dwudzielnych i algorytmów tej reprezentacji.
W tym poście opowiem o mojej implementacji algorytmu sprawdzania dwustronności grafu w Haskell. Mimo że algorytm jest jednym z najbardziej podstawowych, jego piękne wdrożenie w funkcjonalnym stylu zajęło mi kilka iteracji i wymagało sporo pracy. W rezultacie zdecydowałem się na realizację z transformatorami monadowymi.
O mnie
Nazywam się Wasilij Alferow, jestem studentem czwartego roku HSE w Petersburgu. Pisałam wcześniej na blogu и . Obecnie jestem na stażu w w Norwegii, gdzie pracuję nad podejściem do problemu . Moje zainteresowania obejmują algorytmy sparametryzowane i programowanie funkcjonalne.
O implementacji algorytmu
Przedmowa
Gorąco zachęcamy uczniów biorących udział w programie do blogowania. Zapewnili mi platformę dla bloga . Ten artykuł jest tłumaczeniem , napisany przeze mnie tam w lipcu w języku angielskim, z krótką przedmową.
Można znaleźć żądanie ściągnięcia z danym kodem .
O wynikach mojej pracy możesz przeczytać (w języku angielskim) .
Post ten ma na celu zapoznanie czytelnika z podstawowymi pojęciami z zakresu programowania funkcyjnego, chociaż w odpowiednim momencie postaram się przywołać wszystkie używane terminy.
Sprawdzanie wykresów pod kątem dwustronności
Algorytm sprawdzania dwustronności wykresu jest zwykle podawany na kursie o algorytmach jako jeden z najprostszych algorytmów grafowych. Jego pomysł jest prosty: najpierw w jakiś sposób umieszczamy wierzchołki w lewym lub prawym udziale, a gdy zostanie znaleziona sprzeczna krawędź, stwierdzamy, że graf nie jest dwudzielny.
Trochę więcej szczegółów: najpierw umieścimy wierzchołek w lewym udziale. Oczywiście wszyscy sąsiedzi tego wierzchołka muszą leżeć w prawym płacie. Co więcej, wszyscy sąsiedzi sąsiadów tego wierzchołka muszą leżeć w lewym płacie i tak dalej. Kontynuujemy przypisywanie udziałów do wierzchołków, dopóki w połączonym komponencie wierzchołka, od którego zaczęliśmy, nadal znajdują się wierzchołki, do których nie przypisaliśmy sąsiadów. Następnie powtarzamy tę czynność dla wszystkich podłączonych komponentów.
Jeśli pomiędzy wierzchołkami należącymi do tego samego podziału istnieje krawędź, nie jest trudno znaleźć na grafie cykl nieparzysty, co jest powszechnie znane (i całkiem oczywiste) niemożliwe w grafie dwudzielnym. W przeciwnym razie mamy prawidłowy podział, co oznacza, że graf jest dwudzielny.
Zazwyczaj algorytm ten jest implementowany przy użyciu lub . W językach imperatywnych zwykle stosuje się przeszukiwanie w głąb, ponieważ jest nieco prostsze i nie wymaga dodatkowych struktur danych. Wybrałem także wyszukiwanie w głąb, ponieważ jest ono bardziej tradycyjne.
W ten sposób doszliśmy do następującego schematu. Przemierzamy wierzchołki grafu metodą przeszukiwania w głąb i przypisujemy im udziały, zmieniając numer udziału w miarę przesuwania się wzdłuż krawędzi. Jeśli spróbujemy przypisać udział do wierzchołka, który ma już przypisany udział, to śmiało możemy powiedzieć, że graf nie jest dwudzielny. W momencie, gdy wszystkim wierzchołkom zostanie przypisany udział i przyjrzymy się wszystkim krawędziom, mamy dobrą partycję.
Czystość obliczeń
W Haskell zakładamy, że wszystkie obliczenia są czysty. Gdyby jednak tak było naprawdę, nie mielibyśmy możliwości wydrukowania czegokolwiek na ekranie. W ogóle, czysty obliczenia są tak leniwe, że ich nie ma czysty powodów, aby coś obliczyć. Wszelkie obliczenia zachodzące w programie są w jakiś sposób wymuszane "nieczysty" monada IO.
Monady służą do reprezentowania obliczeń efekty w Haskellu. Wyjaśnienie, jak działają, wykracza poza zakres tego posta. Dobry i przejrzysty opis można przeczytać w języku angielskim .
W tym miejscu chcę podkreślić, że chociaż niektóre monady, takie jak IO, są implementowane za pomocą magii kompilatora, prawie wszystkie inne są implementowane w oprogramowaniu i wszystkie zawarte w nich obliczenia są czyste.
Efektów jest wiele i każdy ma swoją własną monadę. To bardzo mocna i piękna teoria: wszystkie monady implementują ten sam interfejs. Porozmawiamy o następujących trzech monadach:
- Albo ea jest obliczeniem, które zwraca wartość typu a, albo zgłasza wyjątek typu e. Zachowanie tej monady jest bardzo podobne do obsługi wyjątków w językach imperatywnych: błędy mogą zostać wyłapane lub przekazane dalej. Główna różnica polega na tym, że monada jest całkowicie logicznie zaimplementowana w standardowej bibliotece w Haskell, podczas gdy języki imperatywne zwykle korzystają z mechanizmów systemu operacyjnego.
- Stan sa to obliczenie, które zwraca wartość typu a i ma dostęp do modyfikowalnego stanu typu s.
- Może. Monada Maybe wyraża obliczenia, które można przerwać w dowolnym momencie, zwracając Nothing. Porozmawiamy jednak o implementacji klasy MonadPlus dla typu Maybe, która wyraża efekt odwrotny: jest to obliczenie, które w dowolnym momencie można przerwać zwracając określoną wartość.
Implementacja algorytmu
Mamy dwa typy danych, Graph a i Bigraph ab, z których pierwszy reprezentuje grafy z wierzchołkami oznaczonymi wartościami typu a, a drugi reprezentuje grafy dwudzielne z wierzchołkami po lewej stronie oznaczonymi wartościami typu a i prawej -boczne wierzchołki oznaczone wartościami typu b.
To nie są typy z biblioteki Alga. Alga nie ma reprezentacji nieskierowanych grafów dwudzielnych. Dla przejrzystości stworzyłem takie typy.
Będziemy także potrzebować funkcji pomocniczych z następującymi podpisami:
-- Список соседей данной вершины.
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)Łatwo zauważyć, że jeśli podczas przeszukiwania w głąb znaleźliśmy sprzeczną krawędź, cykl nieparzysty leży na szczycie stosu rekurencji. Zatem, aby go przywrócić, musimy odciąć wszystko od stosu rekurencji aż do pierwszego wystąpienia ostatniego wierzchołka.
Implementujemy przeszukiwanie w głąb, utrzymując tablicę asocjacyjną numerów udziałów dla każdego wierzchołka. Stos rekurencji zostanie automatycznie utrzymany poprzez implementację klasy Functor wybranej przez nas monady: wystarczy, że wstawimy wszystkie wierzchołki ścieżki do wyniku zwróconego przez funkcję rekurencyjną.
Moim pierwszym pomysłem było użycie monady Albo, która wydaje się implementować dokładnie takie efekty, jakich potrzebujemy. Pierwsza implementacja, którą napisałem, była bardzo zbliżona do tej opcji. Tak naprawdę w pewnym momencie miałem pięć różnych implementacji i ostatecznie zdecydowałem się na inną.
Po pierwsze, musimy zachować tablicę asocjacyjną identyfikatorów udziałów — jest to coś związanego ze stanem. Po drugie, musimy być w stanie zatrzymać się w przypadku wykrycia konfliktu. Może to być Monada dla „Oboje” lub MonadPlus dla „Może”. Główna różnica polega na tym, że albo może zwrócić wartość, jeśli obliczenia nie zostały zatrzymane, a Maybe zwraca w tym przypadku tylko informację na ten temat. Ponieważ do osiągnięcia sukcesu nie potrzebujemy osobnej wartości (jest ona już przechowywana w stanie), wybieramy Może. I w momencie, gdy musimy połączyć działanie dwóch monad, wychodzą one , które dokładnie łączą te efekty.
Dlaczego wybrałem tak złożony typ? Dwa powody. Po pierwsze, implementacja okazuje się bardzo podobna do imperatywu. Po drugie, musimy manipulować wartością zwracaną w przypadku konfliktu podczas powrotu z rekurencji, aby przywrócić nieparzystą pętlę, co jest znacznie łatwiejsze do wykonania w monadzie Maybe.
W ten sposób otrzymujemy tę implementację.
{-# 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)
Blok Where jest rdzeniem algorytmu. Postaram się wyjaśnić co się w nim dzieje.
- inVertex to część wyszukiwania w głąb, w której po raz pierwszy odwiedzamy wierzchołek. Tutaj przypisujemy numer udziału do wierzchołka i uruchamiamy onEdge na wszystkich sąsiadach. W tym miejscu przywracamy stos wywołań: jeśli msum zwróciło wartość, wrzucamy tam wierzchołek v.
- onEdge to część, w której odwiedzamy krawędź. Jest wywoływana dwukrotnie dla każdej krawędzi. Tutaj sprawdzamy, czy wierzchołek po drugiej stronie został odwiedzony i odwiedzamy go, jeśli nie. Jeśli odwiedzimy, sprawdzamy, czy krawędź nie powoduje konfliktu. Jeśli tak, zwracamy wartość - sam szczyt stosu rekurencji, gdzie po powrocie zostaną umieszczone wszystkie pozostałe wierzchołki.
- ProcessVertex sprawdza dla każdego wierzchołka, czy został on odwiedzony, i jeśli nie, uruchamia na nim inVertex.
- dfs uruchamia ProcessVertex na wszystkich wierzchołkach.
I to wszystko.
Historia słowa INLINE
Słowo INLINE nie występowało w pierwszej implementacji algorytmu; pojawiło się później. Kiedy próbowałem znaleźć lepszą implementację, odkryłem, że wersja inna niż INLINE była zauważalnie wolniejsza na niektórych wykresach. Biorąc pod uwagę, że semantycznie funkcje powinny działać tak samo, bardzo mnie to zaskoczyło. Co dziwniejsze, na innej maszynie z inną wersją GHC nie było zauważalnej różnicy.
Po tygodniu spędzonym na czytaniu wyników GHC Core udało mi się rozwiązać problem za pomocą jednej linii wyraźnego INLINE. W pewnym momencie pomiędzy GHC 8.4.4 i GHC 8.6.5 optymalizator przestał to robić samodzielnie.
Nie spodziewałem się spotkać takiego brudu w programowaniu Haskell. Jednak nawet dzisiaj optymalizatorzy czasami popełniają błędy, a naszym zadaniem jest dawanie im wskazówek. Na przykład tutaj wiemy, że funkcja powinna być wbudowana, ponieważ jest wbudowana w wersji imperatywnej i jest to powód, aby dać podpowiedź kompilatorowi.
Co stało się potem?
Następnie zaimplementowałem algorytm Hopcrofta-Karpa z innymi monadami i na tym skończył się program.
Dzięki Google Summer of Code zdobyłem praktyczne doświadczenie w programowaniu funkcjonalnym, co nie tylko pomogło mi zdobyć staż w Jane Street następnego lata (nie jestem pewien, jak dobrze znane jest to miejsce nawet wśród znającej się na rzeczy publiczności Habr, ale jest jednym z nielicznych, gdzie można latem zająć się programowaniem funkcjonalnym), ale także wprowadziło mnie w cudowny świat stosowania tego paradygmatu w praktyce, znacząco różniący się od moich doświadczeń z językami tradycyjnymi.
Źródło: www.habr.com