Миналото лято участвах в — програма за студенти от компанията Google. Ежегодно организаторите избират няколко Open Source проекта, включително от такива известни организации като и . За работа по тези проекти Google кани студенти от цял свят.
Като участник в Google Summer of Code 2019 направих проект в рамките на библиотеката с организацията , която се занимава с развитието на езика Хаскел — един от най-известните функционални езици за програмиране. Alga — библиотека, предлагаща представяне на графи в Хаскел. Тя се използва, например, в — библиотека на компанията Github, която строи семантични дървета, графи на повиквания и зависимости и умее да ги сравнява. Моят проект се състоеше в добавяне на типобезопасно представление за двудолни графи и алгоритми за това представление.
В поста ще разкажа за моята реализация на алгоритъма за проверка на граф за двудолност на Хаскел. Въпреки че алгоритъмът е един от най-базовите, неговата красива реализация в функционален стил ми отне няколко итерации и изискваше доста работа. В резултат стигнах до реализиране с трансформатори на монади.
За мен
Казвам се Василий Алфьоров, студент съм на четвърти курс в Санктпетербургския университет. По-рано в блога съм писал и . В момента съм на стаж в в Норвегия, където се занимавам с подходи към задачата . Областите, които ме интересуват, включват параметризирани алгоритми и функционално програмиране.
За реализирането на алгоритъма
Предговор
Студентите, участващи в програмата, се настоятелно насърчават да водят блог. За мен за блога предоставиха платформа . Тази статия е превод , написан от мен там през юли на английски, с малко предисловие.
Pull Request с кода, за който става въпрос, може да се намери .
За резултатите от моята работа може да се прочете (на английски) .
Постът предполага познаване на основни понятия във функционалното програмиране, въпреки че ще се постарая да напомням всички използвани термини, когато дойде време за тях.
Проверка на двудолност на графове
Алгоритъмът за проверка на двудолност на графа обикновено се представя в курса по алгоритми като един от най-простите графови алгоритми. Идеята му е проста: първо по някакъв начин разпределяме връховете в лявата или дясната част, а при откритие на конфликтен ръб потвърждаваме, че графът не е двудолен.
По-подробно: първо поставяме някой връх в лявата част. Ясно е, че всички съседи на този връх трябва да са в дясната част. След това, всички съседи на съседите на този връх трябва да са в лявата част и така нататък. Продължаваме да назначаваме части на връховете, докато в компонентата на свързаността на върха, с който започнахме, все още има върхове, на които не сме назначили съседите. След това повтаряме това действие за всички компоненти на свързаност.
Ако има ръб между върховете, попадащи в една и съща част, не е трудно да се намери в графа нечетен цикъл, което, както е широко известно (и достатъчно очевидно) е невъзможно в двудолен граф. В противен случай имаме коректно разпределение на части, а следователно графът е двудолен.
Обикновено този алгоритъм се реализира с помощта на или . В имперетивните езици обикновено се използва търсене в дълбочина, тъй като е малко по-просто и не изисква допълнителни структури от данни. Аз също избрах търсене в дълбочина, като по-традиционно.
По този начин стигнахме до следната схема. Обхождаме върховете на графа с помощта на търсене в дълбочина и назначаваме им части, променяйки номера на частта при преминаване през ръб. Ако се опитаме да назначим част на върха, на който вече е назначена част, можем спокойно да твърдим, че графът не е двудолен. В момента, когато на всички върхове е назначена част и сме погледнали всички ръбове, имаме добро разпределение.
Чистота на изчисленията
В Хаскел предполагаме, че всички изчисления са чисти. Въпреки това, ако това наистина беше така, нямаше да имаме възможност да отпечатваме нещо на екрана. Всъщност, чистите изчисления са толкова лениви, че не съществува нито една чиста причина да изчисляваме каквото и да е. Всички изчисления, които се случват в програмата, по един или друг начин се принуждават в „нечиста“ монада IO.
Монадите – начин за представяне на изчисленията с ефекти в Хаскел. Обяснението на това как работят, излиза извън рамките на този пост. Добро и ясно описание може да се прочете на английски .
Тук искам да отбележа, че докато някои монади, като IO, са реализирани чрез магията на компилатора, почти всички останали са реализирани програмно и всичките изчисления в тях са чисти.
Има много ефекти и за всеки е създадена своя монада. Това е много силна и красива теория: всичките монади реализират един и същ интерфейс. Ще говорим за следните три монади:
- Either e a — изчисление, което връща стойност от тип a или хвърля изключение от тип e. Поведението на тази монада е много подобно на работа с изключения в императивни езици: грешките могат да бъдат уловени или предадени напред. Основната разлика е, че монадата е напълно логически реализирана в стандартната библиотека на Хаскел, докато в императивните езици обикновено се използват механизми на операционната система.
- State s a — изчисление, което връща стойност от тип a и има достъп до изменяемо състояние от тип s.
- Maybe a. Монадата Maybe изразява изчисление, което може да бъде прекратено по всяко време с връщането на Nothing. Въпреки това, ще говорим за реализацията на класа MonadPlus за типа Maybe, който изразява обратния ефект: това е изчисление, което може да бъде прекратено по всяко време с връщането на конкретна стойност.
Реализация на алгоритъма
Имаме два типа данни, Graph a и Bigraph a b, като първият представлява графи с върхове, маркирани със стойности от тип a, а вторият представлява двудолни графи с върхове от лявата страна, маркирани със стойности от тип a и върхове от дясната страна, маркирани със стойности от тип b.
Тези не са типове от библиотеката Alga. В Alga няма представяне за ненасочени двудолни графи. Типовете ги направих такива за визуализация.
Също така ще имаме нужда от помощни функции със следните сигнатури:
-- Списък на съседи на тази връх.
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)Не е трудно да се забележи, че ако по време на търсенето в дълбочина сме намерили конфликтно ребро, нечетният цикъл се намира на върха на стека на рекурсията. Така че, за да го възстановим, трябва да отрежем всичко от стека на рекурсията до първото вхождение на последния връх.
Ние реализираме търсене в дълбочина, поддържайки асоциативен масив с номера на дяловете за всеки връх. Стекът на рекурсията ще се поддържа автоматично чрез реализацията на класа Functor на избраната от нас монада: само трябва да слагаме всички върхове от пътя в резултата, върнат от рекурсивната функция.
Първата ми идея беше да използвам монада Either, която сякаш реализира точно тези ефекти, които ни трябват. Първата написана от мен реализация беше много близка до този вариант. Всъщност, имах пет различни реализации в някакъв момент, и в крайна сметка се спряна на друга.
Първо, трябва да поддържаме асоциативен масив с идентификатори на дяловете — това е нещо свързано с State. На второ място, трябва да можем да спрем в случай на открит конфликт. Това може да бъде или Monad за Either, или MonadPlus за Maybe. Основната разлика е, че Either може да върне стойност, ако изчислението не е спряно, а Maybe само предоставя информация в такъв случай. Тъй като нямаме нужда от отделна стойност в случай на успех (тя вече е съхранена в State), избираме Maybe. А в момента, когато трябва да комбинираме ефектите на две монади, изникват , които именно комбинират тези ефекти.
Защо избрах такъв сложен тип? Две причини. Първо, реализацията се доближава много до императивната. Второ, трябва да манипулираме стойността, която се връща в случай на конфликт при обратно връщане от рекурсия за възстановяване на нечетен цикъл, а това е много по-лесно да се направи в монада Maybe.
Така получаваме такава реализация.
{-# 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)
Блок where — това е ядрото на алгоритъма. Ще се опитам да обясня какво се случва вътре в него.
- inVertex — това е част от дълбочинното търсене, в която посещаваме върха за първи път. Тук присвояваме на върха номер на дял и стартираме onEdge за всички съседи. Също това е мястото, където възстановяваме стека на извикванията: ако msum е върнало стойност, добавяме върха v там.
- onEdge е част, в която посещаваме ръба. Тя се извиква два пъти за всеки ръб. Тук проверяваме дали върхът от другата страна е посещен и го посещаваме, ако не е. Ако е посещен, проверяваме дали ръбът е конфликтен. Ако е, връщаме стойността — върха на стека на рекурсията, където после ще се навеси всичките останали върхове.
- processVertex проверява за всеки връх дали е посещен и стартира inVertex, ако не е.
- dfs стартира processVertex за всички върхове.
На това е всичко.
История на думата INLINE
Думата INLINE не беше в първоначалната реализация на алгоритъма, тя се появи по-късно. Когато се опитвах да намеря по-добра реализация, открих, че на някои графи версията без INLINE работи значително по-бавно. С оглед на това, че семантично функциите трябва да работят еднакво, това ме изненада. Още по-странно беше, че на друга машина с друга версия на GHC не се забелязваше никаква разлика.
След като прекарах седмица в четене на изхода от GHC Core, успях да поправя проблема с една линия с явен INLINE. В някакъв момент между GHC 8.4.4 и GHC 8.6.5 оптимизаторът спря да прави това автоматично.
Не очаквах да се срещна с такава мръсотия в програмирането на Хаскел. Въпреки това оптимизаторите все още понякога правят грешки и е наша задача да им даваме подсказки. Например, тук знаем, че функцията трябва да бъде инлайнена, тъй като е инлайнена в императивната версия, и това е повод да дадем подсказка на компилатора.
Какво стана после?
След това реализирах алгоритъма на Хопкрофта-Карпа вече с други монади и с това програмата приключи.
Благодарение на Google Summer of Code придобих практически опит в функционалното програмиране, който не само ми помогна да премина на стаж в Jane Street следващото лято (не съм сигурен колко известно е това място дори сред знайната публика на Хабра, но то е едно от малкото, където лятото можете да се занимавате с функционално програмиране), но и ми откри удивителния свят на приложението на тази парадигма на практика, значително различен от моя опит с традиционните езици.
Източник: habr.com
