主持人 > GSoC 2019：检查图表的二分性和 monad 转换器

GSoC 2019：检查图表的二分性和 monad 转换器

去年夏天我参加了 代码的谷歌暑期 - Google 为学生提供的计划。 每年，主办方都会选择多个开源项目，其中包括来自以下知名组织的项目： Boost 网站 и Linux基金会。 谷歌邀请世界各地的学生参与这些项目。 

作为 2019 年 Google Summer of Code 的参与者，我在图书馆内做了一个项目 藻类 与组织 Haskell.org，它正在开发 Haskell 语言 - 最著名的函数式编程语言之一。 Alga 是一个库，代表 类型安全 Haskell 中图的表示。 例如，它用于 语义 — 一个 Github 库，可基于代码构建语义树、调用和依赖图，并可以对它们进行比较。 我的项目是为二分图添加类型安全的表示以及该表示的算法。 

在这篇文章中，我将讨论我在 Haskell 中检查图二分性的算法的实现。 尽管该算法是最基本的算法之一，但以函数式风格完美地实现它需要我多次迭代，并且需要相当多的工作。 因此，我决定使用 monad 转换器来实现。 

GSoC 2019：检查图表的二分性和 monad 转换器

关于我

我叫 Vasily Alferov，是圣彼得堡 HSE 的四年级学生。 我之前在博客中写过 关于我的关于参数化算法的项目 и 关于祖里哈克之旅。 现在我正在实习 卑尔根大学 在挪威，我正在研究解决该问题的方法 列表着色。 我的兴趣包括参数化算法和函数式编程。

关于算法的实现

前言

强烈鼓励参与该计划的学生写博客。 他们为我提供了一个博客平台 哈斯克尔之夏。 这篇文章是翻译的 文章，是我七月份用英文写的，有一个简短的序言。 

可以找到带有相关代码的 Pull Request 这里.

您可以阅读我的工作成果（英文） 这里.

这篇文章的目的是让读者熟悉函数式编程的基本概念，尽管到时候我会尝试回忆使用的所有术语。

检查图的二分性 

检查图二分性的算法通常在算法课程中作为最简单的图算法之一给出。 他的想法很简单：首先，我们以某种方式将顶点放在左共享或右共享中，当发现冲突边时，我们断言该图不是二分图。

更详细一点：首先我们在左侧部分放置一些顶点。 显然，该顶点的所有邻居都必须位于右叶。 此外，该顶点的邻居的所有邻居必须位于左叶，依此类推。 只要我们开始的顶点的连通分量中仍然存在尚未分配邻居的顶点，我们就会继续向顶点分配份额。 然后我们对所有连接的组件重复此操作。

如果落入同一分区的顶点之间存在边，则不难在图中找到奇数环，这在二分图中众所周知（而且很明显）是不可能的。 否则，我们就有了正确的划分，这意味着该图是二分图。

通常，该算法是使用 广度优先搜索 или 深度优先搜索。 在命令式语言中，通常使用深度优先搜索，因为它稍微简单一些并且不需要额外的数据结构。 我还选择了深度优先搜索，因为它更传统。

因此，我们得出了以下方案。 我们使用深度优先搜索遍历图的顶点并为其分配份额，当我们沿着边缘移动时更改份额的数量。 如果我们尝试将份额分配给已经分配了份额的顶点，我们可以有把握地说该图不是二分图。 当所有顶点都分配了一个份额并且我们查看了所有边时，我们就有了一个很好的分区。

计算的纯度

在 Haskell 中，我们假设所有计算都是 干净。 然而，如果情况确实如此，我们将无法在屏幕上打印任何内容。 总而言之， 清洁 计算懒得没有一个 чШсС，РѕР№ 计算某事的理由。 程序中发生的所有计算都以某种方式被迫进行 “不干净” 单子IO。

Monad 是一种表示计算的方法 效果 在哈斯克尔。 解释它们如何工作超出了本文的范围。 良好且清晰的描述可以用英文阅读 这里.

这里我想指出的是，虽然有些 monad（例如 IO）是通过编译器魔法实现的，但几乎所有其他 monad 都是用软件实现的，并且其中的所有计算都是纯粹的。

效果有很多，每种效果都有自己的单子。 这是一个非常强大和美丽的理论：所有 monad 都实现相同的接口。 我们将讨论以下三个 monad：

  • ea 是一个返回 a 类型值或抛出 e 类型异常的计算。 这个 monad 的行为与命令式语言中的异常处理非常相似：可以捕获或传递错误。 主要区别在于，monad 完全在 Haskell 中的标准库中逻辑实现，而命令式语言通常使用操作系统机制。
  • 状态 sa 是一个返回类型 a 的值并可以访问类型 s 的可变状态的计算。
  • 也许。 Maybe monad 表达了一种可以随时通过返回 Nothing 来中断的计算。 然而，我们将讨论 Maybe 类型的 MonadPlus 类的实现，它表达了相反的效果：它是一个可以通过返回特定值随时中断的计算。

算法的实现

我们有两种数据类型，Graph a 和 Bigraph ab，第一个表示顶点标记为 a 类型值的图，第二个表示左侧顶点标记为 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)

很容易看出，如果在深度优先搜索期间我们发现了冲突边，则奇数循环位于递归堆栈的顶部。 因此，为了恢复它，我们需要切断从递归堆栈到最后一个顶点第一次出现的所有内容。

我们通过维护每个顶点的共享号的关联数组来实现深度优先搜索。 递归堆栈将通过我们选择的 monad 的 Functor 类的实现来自动维护：我们只需要将路径中的所有顶点放入递归函数返回的结果中即可。

我的第一个想法是使用 Either monad，它似乎完全实现了我们需要的效果。 我编写的第一个实现非常接近这个选项。 事实上，我曾经有过五种不同的实现，最终选择了另一种。

首先，我们需要维护一个共享标识符的关联数组——这与状态有关。 其次，我们需要能够在检测到冲突时停止。 这可以是用于 Either 的 Monad，也可以是用于 Maybe 的 MonadPlus。 主要区别在于，如果计算尚未停止，Either 可以返回一个值，而 Maybe 在这种情况下仅返回与此相关的信息。 由于我们不需要单独的成功值（它已经存储在 State 中），因此我们选择 Maybe。 当我们需要结合两个单子的效果时，它们就出来了 单子变压器，它精确地结合了这些效果。

为什么我选择这么复杂的类型？ 有两个原因。 首先，其实现与命令式非常相似。 其次，当从递归返回时，我们需要在发生冲突的情况下操作返回值以恢复奇数循环，这在 Maybe monad 中更容易做到。

这样我们就得到了这个实现。

{-# 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 这个词并不是在该算法的第一次实现中出现的；它是后来才出现的。 当我试图找到更好的实现时，我发现非内联版本在某些图表上明显较慢。 考虑到从语义上讲，这些函数应该工作相同，这让我感到非常惊讶。 更奇怪的是，在另一台具有不同版本 GHC 的机器上没有明显的差异。

在花了一周时间阅读 GHC Core 输出后，我能够通过一行显式 INLINE 解决该问题。 在 GHC 8.4.4 和 GHC 8.6.5 之间的某个时刻，优化器停止自行执行此操作。

我没想到在 Haskell 编程中会遇到这样的污垢。 然而，即使在今天，优化器有时也会犯错误，我们的工作就是给他们提示。 例如，这里我们知道该函数应该内联，因为它在命令式版本中是内联的，这就是给编译器一个提示的原因。

接下来发生了什么

然后我用其他 monad 实现了 Hopcroft-Karp 算法，程序就结束了。

感谢 Google Summer of Code，我获得了函数式编程的实践经验，这不仅帮助我在接下来的夏天获得了 Jane Street 的实习机会（我不确定这个地方在 Habr 知识渊博的观众中有多出名，但它是一个是少数几个可以在夏天从事函数式编程的地方），同时也向我介绍了在实践中应用这种范式的奇妙世界，这与我在传统语言中的经历有很大不同。

来源： habr.com

添加评论