去年の夏に参加したのですが、 Google Summer of Codeの - Google の学生向けプログラム。 毎年、主催者は、次のような有名な組織からのオープンソース プロジェクトをいくつか選択します。 Boost.org и Linux Foundation。 Google は、これらのプロジェクトに取り組むよう世界中から学生を招待しています。 

Google Summer of Code 2019 の参加者として、ライブラリ内でプロジェクトを実行しました 藻類 組織とともに Haskell.org、最も有名な関数型プログラミング言語の XNUMX つである Haskell 言語を開発しています。 Alga は以下を表すライブラリです。 タイプセーフ Haskell でのグラフ表現。 たとえば、次のように使用されます。 セマンティック — コードに基づいてセマンティック ツリー、呼び出しグラフ、依存関係グラフを構築し、それらを比較できる Github ライブラリ。 私のプロジェクトは、XNUMX 部グラフのタイプセーフ表現とその表現のためのアルゴリズムを追加することでした。 

この投稿では、Haskell でグラフの二部性をチェックするアルゴリズムの実装について説明します。 このアルゴリズムは最も基本的なものの XNUMX つですが、それを関数型スタイルで美しく実装するには数回の反復が必要で、かなりの作業が必要でした。 その結果、モナドトランスフォーマーを使用した実装に落ち着きました。 

私について

私の名前はヴァシリー・アルフェロフ、サンクトペテルブルク大学の XNUMX 年生です。 以前書いたブログで 私のプロジェクトについて パラメータ化されたアルゴリズムについて и ZuriHacへの旅行について。 現在、私はインターンシップに参加しています ベルゲン大学 ノルウェーでこの問題へのアプローチに取り組んでいます リストの色付け。 私の興味は、パラメーター化されたアルゴリズムと関数型プログラミングです。

アルゴリズムの実装について

序文

プログラムに参加する学生にはブログを書くことが強く推奨されます。 彼らは私にブログのプラットフォームを提供してくれました ハスケルの夏。 この記事は翻訳です 記事、XNUMX月に私がそこに英語で書いたもので、短い序文が付いています。 

問題のコードを含むプルリクエストが見つかります ここで.

私の仕事の結果について読むことができます（英語） ここで.

この投稿では、読者が関数型プログラミングの基本概念に精通していることを前提としていますが、必要なときに使用されているすべての用語を思い出すように努めます。

グラフの二部性のチェック 

グラフの二部性をチェックするアルゴリズムは、通常、最も単純なグラフ アルゴリズムの XNUMX つとしてアルゴリズムのコースで説明されます。 彼のアイデアは単純です。まず、何らかの方法で頂点を左側または右側の共有に配置し、矛盾するエッジが見つかった場合、グラフが XNUMX 部構成ではないと主張します。

もう少し詳しく説明すると、まず左側の共有に頂点を配置します。 明らかに、この頂点の隣接する頂点はすべて右ローブに存在する必要があります。 さらに、この頂点の隣接頂点のすべての隣接頂点は左ローブに存在する必要があり、以下同様になります。 開始した頂点の接続コンポーネント内に隣接を割り当てていない頂点がまだ存在する限り、頂点への共有の割り当てを続けます。 次に、接続されているすべてのコンポーネントに対してこのアクションを繰り返します。

同じパーティションに属する頂点間にエッジがある場合、グラフ内で奇数のサイクルを見つけるのは難しくありませんが、これは XNUMX 部グラフでは不可能であることが広く知られています (そして非常に明白です)。 それ以外の場合は、正しいパーティションが得られます。これは、グラフが XNUMX 部であることを意味します。

通常、このアルゴリズムは次を使用して実装されます。 幅優先検索 または 深さ優先探索。 命令型言語では、通常、深さ優先検索が若干単純で追加のデータ構造を必要としないため、深さ優先検索が使用されます。 また、より伝統的な深さ優先検索を選択しました。

そこで、次のようなスキームにたどり着きました。 深さ優先検索を使用してグラフの頂点を横断し、それらにシェアを割り当て、エッジに沿って移動するにつれてシェアの数を変更します。 すでに共有が割り当てられている頂点に共有を割り当てようとすると、そのグラフは XNUMX 部構成ではないと安全に言えます。 すべての頂点に共有が割り当てられ、すべてのエッジが確認された時点で、適切なパーティションが得られます。

計算の純度

Haskell では、すべての計算が次のように行われると仮定します。 きれいです。 しかし、これが本当に事実であれば、画面に何も出力することができなくなります。 まったく、 きれいな 計算が怠惰すぎて計算が一つもありません 掃除 何かを計算する理由。 プログラム内で行われるすべての計算は何らかの方法で強制的に実行されます。 「不潔」 モナドIO。

モナドは計算を表現する方法です。 効果 ハスケルで。 これらがどのように機能するかについての説明は、この投稿の範囲を超えています。 適切で明確な説明は英語で読むことができます ここで.

ここで指摘しておきたいのは、IO などの一部のモナドはコンパイラの魔法によって実装されているが、その他のほとんどすべてのモナドはソフトウェアで実装されており、それらの計算はすべて純粋であるということです。

エフェクトはたくさんあり、それぞれに独自のモナドがあります。 これは非常に強力で美しい理論です。すべてのモナドは同じインターフェイスを実装します。 次の XNUMX つのモナドについて説明します。

• ea は、a 型の値を返す計算か、e 型の例外をスローする計算です。 このモナドの動作は命令型言語の例外処理に非常に似ており、エラーは捕捉または渡されます。 主な違いは、命令型言語は通常オペレーティング システムのメカニズムを使用するのに対し、モナドは Haskell の標準ライブラリに完全に論理的に実装されることです。
• 状態 sa は、型 a の値を返し、型 s の可変状態にアクセスする計算です。
• たぶん、 might モナドは、Nothing を返すことでいつでも中断できる計算を表します。 ただし、Maybe 型の MonadPlus クラスの実装について説明します。これは逆の効果を表します。これは、特定の値を返すことでいつでも中断できる計算です。

アルゴリズムの実装

Graph a と Bigraph ab という XNUMX つのデータ タイプがあり、XNUMX つ目はタイプ a の値でラベル付けされた頂点を持つグラフを表し、XNUMX つ目はタイプ a の値でラベル付けされた頂点と右側の頂点を持つ XNUMX 部グラフを表します。 -タイプ 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 モナドを使用することでした。 私が最初に書いた実装は、このオプションに非常に近いものでした。 実際、私はある時点で XNUMX つの異なる実装を考えましたが、最終的には別の実装に落ち着きました。

まず、共有識別子の連想配列を維持する必要があります。これは状態に関するものです。 次に、競合が検出されたときに停止できる必要があります。 これは、Either の Monad か、Maybe の MonadPlus のいずれかになります。 主な違いは、どちらも計算が停止していない場合に値を返すことができるのに対し、Maybe はこの場合、これに関する情報のみを返すことです。 成功を表す別の値は必要ない (値は既に State に保存されている) ため、Maybe を選択します。 そして、XNUMX つのモナドの効果を組み合わせる必要がある瞬間に、それらは出てきます。 モナド変換子、これらの効果を正確に組み合わせます。

なぜこのような複雑なタイプを選択したのでしょうか? 理由は XNUMX つあります。 まず、実装は命令型と非常に似ていることがわかります。 次に、再帰から戻るときに競合が発生した場合に戻り値を操作して、奇妙なループを復元する必要があります。これは、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 はエッジにアクセスする部分です。 これはエッジごとに XNUMX 回呼び出されます。 ここでは、反対側の頂点が訪問されているかどうかを確認し、訪問されていない場合は訪問します。 アクセスされた場合は、エッジが競合しているかどうかを確認します。 そうであれば、再帰スタックの最上部の値を返します。戻り時に他のすべての頂点がそこに配置されます。
• processVertex は、各頂点が訪問されているかどうかを確認し、訪問されていない場合は inVertex を実行します。
• dfs はすべての頂点で processVertex を実行します。

それで全部です。

INLINEという言葉の歴史

INLINE という単語はアルゴリズムの最初の実装には存在せず、後から登場しました。 より良い実装を見つけようとしたところ、一部のグラフでは非 INLINE バージョンの方が著しく遅いことがわかりました。 意味的には関数は同じように動作するはずであることを考えると、これには非常に驚きました。 さらに奇妙なことに、異なるバージョンの GHC を搭載した別のマシンでは目立った違いはありませんでした。

8.4.4 週間かけて GHC コアの出力を読んだ後、8.6.5​​ 行の明示的な INLINE で問題を解決できました。 GHC XNUMX と GHC XNUMX の間のある時点で、オプティマイザはこれを独自に行うことを停止しました。

Haskell プログラミングでこのような汚れに遭遇するとは予想していませんでした。 しかし、今でもオプティマイザーは時々間違いを犯すので、それらにヒントを与えるのが私たちの仕事です。 たとえば、ここでは関数が命令型バージョンでインライン化されているため、インライン化する必要があることがわかり、これがコンパイラにヒントを与える理由になります。

次に何が起こりましたか？

次に、他のモナドを使用して Hopcroft-Karp アルゴリズムを実装し、プログラムは終了しました。

Google Summer of Code のおかげで、私は関数型プログラミングの実践的な経験を積むことができ、それが翌年の夏にジェーン ストリートでインターンシップに参加できるだけでなく、ハブルの知識豊富な聴衆の間でもこの場所がどの程度知られているかはわかりませんが、夏休みに関数型プログラミングに取り組むことができる数少ない場所の一つです）だけでなく、伝統的な言語での私の経験とは大きく異なる、このパラダイムを実際に適用する素晴らしい世界にも私を紹介してくれました。

出所： habr.com