Миналото лято участвах в — програма за студенти от компанията Google. Всяка година организаторите избират няколко Open Source проекта, включително от толкова известни организации, като и . За работа по тези проекти Google кани студенти от целия свят.
Като участник в Google Summer of Code 2019 разработвах проект в контекста на библиотеката с организацията , която се занимава с развитието на езика Хаскел — един от най-известните функционални езици за програмиране. Alga — библиотека, предоставяща представяне на графи в Хаскел. Тя се използва, например, в — библиотека на компанията Github, която изгражда семантични дървета, графи на повиквания и зависимости и умее да ги сравнява. Моят проект се състоеше в добавянето на типобезопасно представяне за двудолни графи и алгоритми за това представяне.
В поста ще разкажа за моята реализация на алгоритъм за проверка на графа за двудолност на Хаскел. Въпреки че алгоритмът е един от най-базовите, красивата му реализация в функционален стил ми отне няколко итерации и изискваше доста работа. В резултат на това се спрях на реализация с трансформатори на монади.
За мен
Казвам се Василий Алфьоров, студент съм на четвърта година в Петербургския университет. По-рано в блога писах и . В момента съм на стаж в в Норвегия, където работя по подходи към задачата . Интересувам се от параметризирани алгоритми и функционално програмиране.
За реализацията на алгоритъма
Предговор
На студентите, участващи в програмата, е силно препоръчително да водят блог. За мен предоставиха платформа . Тази статия е превод , написан от мен там през юли на английски език, с малък предговор.
Pull Request с кода, за който става въпрос, може да бъде намерен .
За резултатите от моята работа може да се прочете (на английски) .
Постът предполага запознаване на читателя с базови понятия във функционалното програмиране, въпреки че ще се опитам да припомня всички използвани термини, когато дойде време.
Проверка на графите за двудолност
Алгоритъмът за проверка на графа за двудолност обикновено се дава в курса по алгоритми като един от най-простите графови алгоритми. Неговата идея е пряка: първо поставяме върховете в лявата или дясната част и при откриването на конфликтен ръб твърдим, че графът не е двудолен.
Няколко подробности: първо поставяме една върхова точка в лявото множество. Очевидно, всички съседи на тази върхова точка трябва да lieжат в дясното множество. След това всички съседи на съседите на тази върхова точка трябва да lieжат в лявото множество и така нататък. Продължаваме да назначаваме на върховете принадлежност, докато в компонентата на свързаност, от която започнахме, все още има върхове, на които не сме назначили съседи. След това повтаряме това действие за всички компоненти на свързаност.
Ако има ръб между върховете, попаднали в едно и също множество, не е трудно да се намери в графа нечётен цикъл, което е широко известно (и достатъчно очевидно) невъзможно в двудолния граф. В противен случай имаме коректно разделение на множества, което означава, че графът е двудолен.
Обикновено този алгоритъм се реализира с помощта на или . В императивните езици обикновено се използва търсене в дълбочина, тъй като е малко по-просто и не изисква допълнителни структури от данни. Аз също избрах търсене в дълбочина, като по-традиционно.
Така стигаме до следната схема. Обхождаме върховете на графа с помощта на търсене в дълбочина и им назначаваме множества, променяйки номера на множеството при преминаване по ръба. Ако опитаме да назначим множество на връх, на който вече е назначено, можем спокойно да твърдим, че графът не е двудолен. В момента, в който на всички върхове е назначено множество и сме проверили всички ръбове, имаме добро разделение.
Чистота на изчисленията
В Хаскел ние приемаме, че всички изчисления са чисти. Обаче, ако това наистина беше така, нямаше да имаме възможността да отпечатваме нещо на екрана. Всъщност, чистите изчисления са толкова мързеливи, че не съществува нито една чиста причина да изчисляваме нещо. Всички изчисления, които се случват в програмата, по един или друг начин се принуждават в „нечиста“ монада IO.
Монадите са начин за представяне на изчисления с ефекти в Хаскел. Обяснението на това как работят излиза извън обхвата на този пост. Добро и разбираемо описание може да се прочете на английски. .
Тук искам да отбележа, че докато някои монадите, като IO, са реализирани чрез магията на компилатора, почти всички останали са реализирани програмно и всички изчисления в тях са чисти.
Ефектите могат да бъдат много и за всеки от тях е заведена своя монада. Това е много силна и красива теория: всички монади реализират един и същ интерфейс. Ще говорим за следните три монадии:
- Или e a — изчисление, което връща стойност от тип a или хвърля изключение от тип e. Поведението на тази монада е много подобно на работа с изключения в императивни езици: грешките могат да бъдат уловени или предадени нататък. Основната разлика е, че монада е изцяло логически реализирана в стандартната библиотека на същия Haskell, докато в императивните езици обикновено се използват механизми на операционната система.
- 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, която наистина реализира именно тези ефекти, които ни трябват. Първата написана от мен реализация беше много близка до този вариант. Всъщност, в определен момент имах пет различни реализации, и в крайна сметка се спрях на друга.
На първо място, трябва да поддържаме асоциативен масив от идентификатори на дялове — това е свързано със състоянието. На второ място, трябва да можем да се спираме в случай на конфликт. Това може да бъде или Monad за Either, или MonadPlus за Maybe. Основната разлика е, че Either може да връща стойност, ако изчислението не е спряно, докато Maybe в такъв случай просто връща информация за това. Тъй като не ни трябва отделна стойност при успех (тя вече се съхранява в състоянието), избираме 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
