GSoC 2019: Проверка графов на двудольность и трансформеры монад

Прошлым летом я участвовал в Google Summer of Code ^[1] — программе для студентов от компании Google. Ежегодно организаторы отбирают несколько Open Source-проектов, в том числе от таких известных организаций, как Boost.org ^[2] и The Linux Foundation ^[3]. Для работы над этими проектами Google приглашает студентов со всего мира. 

Как участник Google Summer of Code 2019 я делал проект в рамках библиотеки Alga ^[4] с организацией Haskell.org ^[5], занимающейся развитием языка Хаскелль — одного из самых известных функциональных языков программирования. Alga — библиотека, представляющая типобезопасное ^[6] представление для графов в Хаскелле. Она используется, например, в semantic ^[7] — библиотеке компании Github, строящей по коду семантические деревья, графы вызовов и зависимостей и умеющей их сравнивать. Мой проект состоял в добавлении туда типобезопасного представления для двудольных графов и алгоритмов для этого представления. 

В посте я расскажу про свою реализацию алгоритма проверки графа на двудольность на Хаскелле. Несмотря на то, что алгоритм является одним из самых базовых, его красивая реализация в функциональном стиле заняла у меня несколько итераций и потребовала довольно много работы. В результате я остановился на реализации с трансформерами монад. 

О себе

Меня зовут Василий Алфёров, я студент четвёртого курса Питерской Вышки. Ранее в блоге я писал про мой проект про параметризованные алгоритмы ^[8] и про поездку на ZuriHac ^[9]. Прямо сейчас я нахожусь на стажировке в Бергенском университете ^[10] в Норвегии, где занимаюсь подходами к задаче List Coloring ^[11]. В сферу моих интересов входят параметризованные алгоритмы и функциональное программирование.

О реализации алгоритма

Предисловие

Студентам, участвующим в программе, настоятельно рекомендуется вести блог. Мне для блога предоставили площадку Summer of Haskell ^[12]. Эта статья — перевод статьи ^[13], написанной мной туда в июле на английском языке, с небольшим предисловием. 

Pull Request с кодом, про который идёт речь, можно найти тут ^[14].

Про результаты моей работы можно почитать (на английском) здесь ^[15].

Пост предполагает знакомство читателя с базовыми понятиями в функциональном программировании, хотя я постараюсь напомнить все используемые термины, когда до них дойдёт время.

Проверка графов на двудольность 

Алгоритм проверки графа на двудольность обычно даётся в курсе алгоритмов как один из простейших графовых алгоритмов. Его идея прямолинейна: сначала мы каким-то образом кладём вершины в левую или правую долю, а при обнаружении конфликтного ребра утверждаем, что граф не является двудольным.

Чуть подробнее: сначала мы кладём какую-то вершину в левую долю. Очевидно, все соседи этой вершины должны лежать в правой доле. Далее, все соседи соседей этой вершины должны лежать в левой доле, и так далее. Мы продолжаем назначать вершинам доли до тех пор, пока в компоненте связности вершины, с которой мы начали, ещё есть вершины, которым мы не назначили соседей. Затем мы повторяем это действие для всех компонент связности.

Если есть ребро между вершинами, попавшими в одну и ту же долю, несложно найти в графе нечётный цикл, как широко известно (и достаточно очевидно) невозможный в двудольном графе. Иначе у нас есть корректное разбиение на доли, а значит, граф является двудольным.

Как правило, этот алгоритм реализуют с помощью поиска в ширину ^[16] или поиска в глубину ^[17]. В императивных языках обычно используют поиск в глубину, как чуть-чуть более простой и не требующий дополнительных структур данных. Я также выбрал поиск в глубину как более традиционный.

Таким образом, мы пришли к следующей схеме. Мы обходим вершины графа с помощью поиска в глубину и назначаем им доли, меняя номер доли при переходе по ребру. Если мы пытаемся назначить долю вершине, у которой доля уже назначена, можно смело утверждать, что граф не является двудольным. В тот момент, когда всем вершинам назначена доля и мы посмотрели на все рёбра, у нас есть хорошее разбиение.

Чистота вычислений

В Хаскелле мы предполагаем, что все вычисления являются чистыми. Однако, если бы это действительно было так, у нас не было бы возможности напечатать что-либо на экран. Вообще, чистые вычисления настолько ленивы, что не существует ни одной чистой причины что-либо вычислять. Все вычисления, происходящие в программе, так или иначе форсируются в «нечистой» монаде IO.

Монады — способ представления вычислений с эффектами в Хаскелле. Объяснение того, как они работают, выходит за рамки этого поста. Хорошее и понятное описание можно почитать на английском тут ^[18].

Здесь я хочу заметить, что в то время как некоторые монады, такие, как 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. А в тот момент, когда нам нужно комбинировать эффекты двух монад, вылезают трансформеры монад ^[19], которые как раз и комбинируют эти эффекты.

Почему я выбрал такой сложный тип? Две причины. Во-первых, реализация получается очень похожей на императивную. Во-вторых, нам нужно манипулировать значением, возвращаемым в случае конфликта, при возврате назад из рекурсии для восстановления нечётного цикла, а это гораздо проще делать в монаде 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 оптимизатор перестал это делать самостоятельно.

Я не ожидал встретить такую грязь в программировании на Хаскелле. Однако оптимизаторы всё же даже в наше время иногда совершают ошибки и давать им подсказки — наша задача. Например, здесь мы знаем, что функция должна быть заинлайнена, так как она заинлайнена в императивной версии, и это повод дать компилятору подсказку.

Что было дальше?

Дальше я реализовал алгоритм Хопкрофта-Карпа уже с другими монадами, и на этом программа закончилась.

Благодаря Google Summer of Code я приобрёл практический опыт в функциональном программировании, который не только помог мне пройти на стажировку в Jane Street на следующее лето (не уверен, насколько это место известно даже среди знающей аудитории Хабра, но оно — одно из немногих, где можно летом заниматься функциональным программированием), но и познакомил с удивительным миром применения этой парадигмы на практике, значительно отличающимся от моего опыта в традиционных языках.

Автор: hse_spb

Источник ^[20]