Минулого літа я брав участь у — програма для студентів від компанії Google. Щорічно організатори відбирають кілька Open Source-проектів, зокрема від таких відомих організацій, як и . Для роботи над цими проектами Google запрошує студентів з усього світу.
Як учасник Google Summer of Code 2019 я робив проект у рамках бібліотеки з організацією , що займається розвитком мови Хаскелль - однієї з найвідоміших функціональних мов програмування. Alga - бібліотека, що представляє подання для графів у Хаскеллі. Вона використовується, наприклад, в — бібліотеці компанії Github, яка будує за кодом семантичні дерева, графи викликів та залежностей та вміє їх порівнювати. Мій проект полягав у додаванні туди типобезпечної вистави для дводольних графів та алгоритмів для цієї вистави.
У пості розповім про свою реалізацію алгоритму перевірки графа на дводольність на Хаскелле. Незважаючи на те, що алгоритм є одним із найбільш базових, його гарна реалізація у функціональному стилі зайняла у мене кілька ітерацій і зажадала чимало роботи. В результаті я зупинився на реалізації із трансформерами монад.
Про себе
Мене звуть Василь Алферов, я студент четвертого курсу Пітерської Вишки. Раніше у блозі я писав и . Прямо зараз я перебуваю на стажуванні в у Норвегії, де займаюся підходами до завдання . До сфери моїх інтересів входять параметризовані алгоритми та функціональне програмування.
Про реалізацію алгоритму
Передмова
Студентам, які беруть участь у програмі, рекомендується вести блог. Мені для блогу надали майданчик . Ця стаття — переклад , написана мною туди в липні англійською мовою, з невеликою передмовою.
Pull Request з кодом, про який йдеться, можна знайти .
Про результати моєї роботи можна почитати (англійською) .
Пост передбачає знайомство читача з базовими поняттями у функціональному програмуванні, хоча я постараюся нагадати всі терміни, коли до них дійде час.
Перевірка графів на дводольність
Алгоритм перевірки графа на дводольність зазвичай дається у курсі алгоритмів як із найпростіших графових алгоритмів. Його ідея прямолінійна: спочатку ми якимось чином кладемо вершини у ліву чи праву частку, а при виявленні конфліктного ребра стверджуємо, що граф не дводольний.
Дещо докладніше: спочатку ми кладемо якусь вершину в ліву частку. Очевидно, всі сусіди цієї вершини мають лежати у правій частці. Далі всі сусіди сусідів цієї вершини повинні лежати в лівій частині, і так далі. Ми продовжуємо призначати вершинам частки до тих пір, поки в компоненті зв'язності вершини, з якої ми почали, є ще вершини, яким ми не призначили сусідів. Потім ми повторюємо цю дію всім компонент зв'язності.
Якщо є ребро між вершинами, що потрапили в одну й ту саму частку, нескладно знайти в графі непарний цикл, як відомо (і досить очевидно) неможливий у дводольному графі. Інакше ми маємо коректне розбиття на частки, а значить, граф є дводольним.
Як правило, цей алгоритм реалізують за допомогою або . У імперативних мовах зазвичай використовують пошук у глибину, як трохи простіший і вимагає додаткових структур даних. Я також вибрав пошук у глибину як більш традиційний.
Таким чином, ми дійшли наступної схеми. Ми обходимо вершини графа за допомогою пошуку в глибину і призначаємо їм частки, змінюючи номер частки під час переходу по ребру. Якщо ми намагаємося призначити частку вершині, біля якої частка вже призначена, можна сміливо стверджувати, що граф не дводольним. У той момент, коли всім вершинам призначена частка і ми подивилися на всі ребра, ми маємо гарне розбиття.
Чистота обчислень
У Хаскеллі ми припускаємо, що всі обчислення є чистими. Однак, якби це справді було так, у нас не було б можливості надрукувати щось на екрані. Взагалі, чисті обчислення настільки ліниві, що не існує жодної чистої причини щось обчислювати. Усі обчислення, що відбуваються в програмі, так чи інакше форсуються в «нечистий» монаді IO.
Монади - спосіб подання обчислень з ефектами у Хаскеллі. Пояснення того, як вони працюють, виходить за межі цієї посади. Хороший і зрозумілий опис можна почитати англійською .
Тут я хочу помітити, що в той час як деякі монади, такі як IO, реалізовані через магію компілятора, майже всі інші реалізовані програмно і всі обчислення в них чисті.
Ефектів буває дуже багато і під кожен заведено свою монаду. Це дуже сильна і красива теорія: всі монади реалізують той самий інтерфейс. Ми говоритимемо про наступні три монади:
- Either ea — обчислення, що повертає значення типу a або виключення типу e, що кидає. Поведінка цієї монади дуже схожа на роботу з винятками в імперативних мовах: помилки можуть бути зловлені або передані далі. Основна різниця в тому, що монада повністю логічно реалізована в стандартній бібліотеці на тому ж Хаскеллі, тоді як у імперативних мовах зазвичай використовуються механізми операційної системи.
- State sa - обчислення, що повертає значення типу a і має доступ до стану типу s.
- Maybe a. Монада 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, яка начебто реалізує ті ефекти, які нам потрібні. Перша написана мною реалізація була дуже близька до цього варіанту. Насправді, я мав п'ять різних реалізацій у якийсь момент, і я зрештою зупинився на іншій.
По-перше, нам потрібно підтримувати асоціативний масив ідентифікаторів часток — це щось про 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 <- 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 це частина, в якій ми відвідуємо ребро. Вона викликається двічі кожному за ребра. Тут ми перевіряємо, чи відвідана вершина з іншого боку, і відвідуємо її, якщо ні. Якщо відвідана, перевіряємо, чи не є ребро конфліктним. Якщо є, повертаємо значення - саму верхівку стека рекурсії, куди потім при поверненні навісять всі інші вершини.
- procesVertex перевіряє для кожної вершини, чи відвідана вона, і запускає на ній вVertex, якщо ні.
- dfs запускає procesVertex на всіх вершинах.
На цьому все.
Історія слова INLINE
Слова INLINE був у першої реалізації алгоритму, воно з'явилося пізніше. Коли я намагався знайти найкращу реалізацію, я виявив, що на деяких графах версія без INLINE працює помітно повільніше. З урахуванням того, що семантичні функції повинні працювати однаково, це мене дуже здивувало. Ще дивніше, що на іншій машині з іншою версією GHC жодної різниці помітно не було.
Після того, як я витратив тиждень на читання висновку GHC Core, я зміг виправити проблему одним рядком із явним INLINE. В якийсь момент між GHC 8.4.4 та GHC 8.6.5 оптимізатор перестав це робити самостійно.
Я не очікував зустріти такий бруд у програмуванні на Хаскеллі. Однак оптимізатори все ж таки навіть у наш час іноді роблять помилки і давати їм підказки — наше завдання. Наприклад, тут ми знаємо, що функція має бути заінлайнована, оскільки вона заінлайнована в імперативній версії, і це привід дати компілятору підказку.
Що було далі?
Далі я реалізував алгоритм Хопкрофта Карпа вже з іншими монадами, і на цьому програма закінчилася.
Завдяки Google Summer of Code я набув практичного досвіду у функціональному програмуванні, який не тільки допоміг мені пройти на стажування в Jane Street наступного літа (не впевнений, наскільки це місце відоме навіть серед знаючої аудиторії Хабра, але воно одне з небагатьох, де можна влітку займатися функціональним програмуванням), але й познайомив із дивовижним світом застосування цієї парадигми на практиці, що значно відрізняється від мого досвіду в традиційних мовах.
Джерело: habr.com