Миналото лято участвах в - програма за студенти от Google. Всяка година организаторите избират няколко проекта с отворен код, включително от такива известни организации като и . Google кани студенти от цял свят да работят по тези проекти.
Като участник в Google Summer of Code 2019, направих проект в библиотеката с организацията , която разработва езика Haskell – един от най-известните езици за функционално програмиране. Alga е библиотека, която представлява представяне на графики в Haskell. Използва се например в — Github библиотека, която изгражда семантични дървета, графики на повиквания и зависимости въз основа на код и може да ги сравнява. Моят проект беше да добавя безопасно за типа представяне за двустранни графики и алгоритми за това представяне.
В тази публикация ще говоря за моята реализация на алгоритъм за проверка на графика за двустранност в Haskell. Въпреки че алгоритъмът е един от най-основните, красивото му внедряване във функционален стил ми отне няколко повторения и изискваше доста работа. В резултат на това се спрях на реализация с монадни трансформатори.
За мен
Казвам се Василий Алферов, студент съм четвърта година в HSE в Санкт Петербург. По-рано в блога писах и . В момента съм на стаж в в Норвегия, където работя върху подходи към проблема . Интересите ми включват параметризирани алгоритми и функционално програмиране.
Относно изпълнението на алгоритъма
предговор
Студентите, участващи в програмата, са силно насърчавани да водят блог. Предоставиха ми платформа за блога . Тази статия е превод , написана от мен там през юли на английски, с кратък предговор.
Може да се намери Pull Request с въпросния код .
Можете да прочетете за резултатите от моята работа (на английски) .
Тази публикация има за цел да запознае читателя с основните понятия във функционалното програмиране, въпреки че ще се опитам да си припомня всички използвани термини, когато му дойде времето.
Проверка на графиките за двустранност
Алгоритъм за проверка на графа за двустранност обикновено се дава в курс по алгоритми като един от най-простите алгоритми за графи. Идеята му е ясна: първо по някакъв начин поставяме върхове в левия или десния дял и когато се открие конфликтно ребро, ние твърдим, че графът не е двустранен.
Малко повече подробности: първо поставяме някакъв връх в левия дял. Очевидно всички съседи на този връх трябва да лежат в десния лоб. Освен това, всички съседи на съседите на този връх трябва да лежат в левия лоб и т.н. Продължаваме да присвояваме дялове на върхове, докато все още има върхове в свързания компонент на върха, с който започнахме, на които не сме присвоили съседи. След това повтаряме това действие за всички свързани компоненти.
Ако има ребро между върховете, които попадат в една и съща част, не е трудно да се намери нечетен цикъл в графиката, което е широко известно (и съвсем очевидно) невъзможно в двустранен граф. В противен случай имаме правилно разбиване, което означава, че графиката е двучастна.
Обикновено този алгоритъм се реализира с помощта на или . В императивните езици обикновено се използва търсене в дълбочина, тъй като е малко по-просто и не изисква допълнителни структури от данни. Също така избрах търсене в дълбочина, тъй като е по-традиционно.
Така стигнахме до следната схема. Преминаваме през върховете на графиката с помощта на търсене в дълбочина и им присвояваме дялове, променяйки номера на дяла, докато се движим по ръба. Ако се опитаме да присвоим дял на връх, който вече има присвоен дял, можем спокойно да кажем, че графът не е двустранен. В момента, в който на всички върхове е присвоен дял и ние разгледаме всички ръбове, имаме добро разделение.
Чистота на изчисленията
В Haskell приемаме, че всички изчисления са чиста. Но ако това наистина беше така, нямаше да имаме начин да отпечатаме нищо на екрана. Изобщо, чист изчисленията са толкова мързеливи, че няма такъв чисти причини да се изчисли нещо. Всички изчисления, извършвани в програмата, са някак принудени "нечист" монада IO.
Монадите са начин за представяне на изчисления ефекти в Haskell. Обяснението как работят е извън обхвата на тази публикация. Добро и ясно описание може да се прочете на английски .
Тук искам да отбележа, че докато някои монади, като IO, са имплементирани чрез магия на компилатор, почти всички други са имплементирани в софтуер и всички изчисления в тях са чисти.
Има много ефекти и всеки има своя собствена монада. Това е много силна и красива теория: всички монади прилагат един и същ интерфейс. Ще говорим за следните три монади:
- Или ea е изчисление, което връща стойност от тип a, или хвърля изключение от тип e. Поведението на тази монада е много подобно на обработката на изключения в императивните езици: грешките могат да бъдат уловени или предадени. Основната разлика е, че монадата е напълно логично внедрена в стандартната библиотека в Haskell, докато императивните езици обикновено използват механизми на операционната система.
- Състояние sa е изчисление, което връща стойност от тип a и има достъп до променливо състояние от тип s.
- Може би а. Монадата Maybe изразява изчисление, което може да бъде прекъснато по всяко време чрез връщане на Nothing. Ние обаче ще говорим за реализацията на класа MonadPlus за типа Maybe, който изразява обратния ефект: това е изчисление, което може да бъде прекъснато по всяко време чрез връщане на конкретна стойност.
Реализация на алгоритъма
Имаме два типа данни, Graph a и Bigraph ab, първият от които представлява графики с върхове, обозначени със стойности от тип 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 за Или, или MonadPlus за Може би. Основната разлика е, че Either може да върне стойност, ако изчислението не е спряно, а 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 <- 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)
Блокът 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 оптимизаторът спря да прави това сам.
Не очаквах да срещна такава мръсотия в програмирането на Haskell. Но дори и днес оптимизаторите понякога правят грешки и нашата работа е да им даваме съвети. Например, тук знаем, че функцията трябва да бъде вградена, защото е вградена в императивната версия и това е причина да дадем подсказка на компилатора.
Какво се случи след това?
След това внедрих алгоритъма на Хопкрофт-Карп с други монади и това беше краят на програмата.
Благодарение на Google Summer of Code придобих практически опит във функционалното програмиране, което не само ми помогна да получа стаж в Jane Street следващото лято (не съм сигурен колко добре е известно това място дори сред осведомената аудитория на Habr, но е едно от малкото, където можете през лятото да се занимавате с функционално програмиране), но също така ме въведе в прекрасния свят на прилагането на тази парадигма на практика, значително различен от моя опит в традиционните езици.
Източник: www.habr.com