主持人 > GSoC 2019：檢查圖表的二分性和 monad 轉換器

GSoC 2019：檢查圖表的二分性和 monad 轉換器

去年夏天我參加了 代碼的谷歌暑期 - Google 為學生提供的方案。 每年，主辦單位都會選擇多個開源項目，其中包括來自以下知名組織的項目： Boost.org и 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 知識淵博的觀眾中有多出名，但它是一個是少數幾個可以在夏天從事函數式程式設計的地方），同時也向我介紹了在實踐中應用這種範式的奇妙世界，這與我在傳統語言中的經歷有很大不同。

來源： www.habr.com

添加評論