지난 여름에 제가 참여했던 코드의 구글 여름 - Google 학생들을 위한 프로그램입니다. 매년 주최측은 다음과 같은 잘 알려진 조직을 포함하여 여러 오픈 소스 프로젝트를 선택합니다. Boost.org и 리눅스 재단. Google은 이러한 프로젝트에 참여하도록 전 세계의 학생들을 초대합니다. 

Google Summer of Code 2019에 참여하여 도서관 내에서 프로젝트를 진행했습니다. 알가 조직과 함께 Haskell.org, 가장 유명한 함수형 프로그래밍 언어 중 하나인 Haskell 언어를 개발하고 있습니다. Alga는 다음을 나타내는 라이브러리입니다. 안전한 타입 Haskell의 그래프 표현. 예를 들어 다음에서 사용됩니다. 시맨틱 — 코드를 기반으로 의미 체계, 호출 및 종속성 그래프를 구축하고 비교할 수 있는 Github 라이브러리입니다. 내 프로젝트는 이분 그래프에 대한 유형 안전 표현과 해당 표현에 대한 알고리즘을 추가하는 것이었습니다. 

이번 포스팅에서는 Haskell에서 그래프의 이분성을 확인하는 알고리즘을 구현하는 방법에 대해 이야기하겠습니다. 알고리즘이 가장 기본적인 것 중 하나임에도 불구하고 이를 기능적 스타일로 아름답게 구현하려면 여러 번의 반복이 필요했고 꽤 많은 작업이 필요했습니다. 결과적으로 저는 모나드 변환기를 사용한 구현을 결정했습니다. 

성명서

제 이름은 Vasily Alferov이고 상트페테르부르크 HSE의 XNUMX학년 학생입니다. 제가 예전에 블로그에 썼던 매개변수화된 알고리즘에 관한 내 프로젝트에 대해 и ZuriHac 여행에 대해. 지금은 인턴십 중이에요. 베르겐대학교 노르웨이에서 문제에 대한 접근 방식을 연구하고 있습니다. 목록 색칠하기. 내 관심 분야에는 매개변수화된 알고리즘과 함수형 프로그래밍이 포함됩니다.

알고리즘 구현에 대해

머리말

프로그램에 참여하는 학생들은 블로그 활동을 적극 권장합니다. 그들은 나에게 블로그 플랫폼을 제공했습니다 하스켈의 여름. 이 글은 번역본입니다 조항, 짧은 서문과 함께 제가 XNUMX월에 그곳에서 영어로 썼습니다. 

문제의 코드가 포함된 Pull Request를 찾을 수 있습니다. 여기에.

내 작업 결과를 읽을 수 있습니다(영어). 여기에.

이 게시물은 독자가 함수형 프로그래밍의 기본 개념에 익숙해지도록 의도되었지만, 때가 되면 사용된 모든 용어를 기억해내려고 노력할 것입니다.

그래프의 이분성 확인 

그래프의 이분성을 확인하는 알고리즘은 일반적으로 가장 간단한 그래프 알고리즘 중 하나로 알고리즘 강좌에서 제공됩니다. 그의 아이디어는 간단합니다. 먼저 어떻게든 왼쪽이나 오른쪽 공유에 정점을 배치하고 충돌하는 가장자리가 발견되면 그래프가 이분형이 아니라고 주장합니다.

조금 더 자세히 설명하자면 먼저 왼쪽 공유에 정점을 배치합니다. 분명히 이 꼭지점의 모든 이웃은 오른쪽 엽에 있어야 합니다. 또한, 이 정점의 이웃의 모든 이웃은 왼쪽 엽에 있어야 합니다. 우리가 시작한 정점의 연결된 구성 요소에 이웃을 할당하지 않은 정점이 여전히 있는 한 정점에 공유를 계속 할당합니다. 그런 다음 연결된 모든 구성 요소에 대해 이 작업을 반복합니다.

동일한 분할에 속하는 정점 사이에 간선이 있는 경우 그래프에서 홀수 사이클을 찾는 것이 어렵지 않습니다. 이는 이분 그래프에서는 불가능하다는 것이 널리 알려져 있습니다. 그렇지 않으면 올바른 분할이 있으며 이는 그래프가 이분형임을 의미합니다.

일반적으로 이 알고리즘은 다음을 사용하여 구현됩니다. 너비 우선 탐색 또는 깊이 우선 탐색. 명령형 언어에서는 깊이 우선 검색이 약간 더 간단하고 추가 데이터 구조가 필요하지 않기 때문에 일반적으로 사용됩니다. 또한 더 전통적인 깊이 우선 검색을 선택했습니다.

따라서 우리는 다음과 같은 계획을 세웠습니다. 깊이 우선 검색을 사용하여 그래프의 꼭지점을 탐색하고 공유를 할당하여 가장자리를 따라 이동할 때 공유의 수를 변경합니다. 이미 공유가 할당된 정점에 공유를 할당하려고 하면 그래프가 이분형이 아니라고 안전하게 말할 수 있습니다. 모든 꼭지점에 공유가 할당되고 모든 가장자리를 살펴본 순간 좋은 파티션을 갖게 됩니다.

계산의 순수성

Haskell에서는 모든 계산이 다음과 같다고 가정합니다. 깨끗합니다. 그러나 이것이 사실이라면 화면에 아무것도 인쇄할 방법이 없을 것입니다. 조금도, 깨끗한 계산이 너무 게으른데 하나도 없네 깨끗한 무언가를 계산하는 이유. 프로그램에서 발생하는 모든 계산은 어떻게든 강제로 수행됩니다. "더러운" 모나드 IO.

모나드는 계산을 표현하는 방법입니다. 효과 하스켈에서. 작동 방식을 설명하는 것은 이 게시물의 범위를 벗어납니다. 훌륭하고 명확한 설명을 영어로 읽을 수 있습니다. 여기에.

여기서는 IO와 같은 일부 모나드가 컴파일러 마법을 통해 구현되는 반면, 거의 모든 모나드는 소프트웨어로 구현되며 그 안의 모든 계산은 순수하다는 점을 지적하고 싶습니다.

많은 효과가 있으며 각각 고유한 모나드가 있습니다. 이것은 매우 강력하고 아름다운 이론입니다. 모든 모나드는 동일한 인터페이스를 구현합니다. 우리는 다음 세 가지 모나드에 대해 이야기할 것입니다:

• ea는 a 유형의 값을 반환하거나 e 유형의 예외를 발생시키는 계산입니다. 이 모나드의 동작은 명령형 언어의 예외 처리와 매우 유사합니다. 즉, 오류를 포착하거나 전달할 수 있습니다. 주요 차이점은 모나드는 Haskell의 표준 라이브러리에서 완전히 논리적으로 구현되는 반면 명령형 언어는 일반적으로 운영 체제 메커니즘을 사용한다는 것입니다.
• 상태 sa는 a 유형의 값을 반환하고 s 유형의 변경 가능한 상태에 액세스할 수 있는 계산입니다.
• 아마. Maybe 모나드는 Nothing을 반환함으로써 언제든지 중단될 수 있는 계산을 표현합니다. 그러나 우리는 Maybe 유형에 대한 MonadPlus 클래스의 구현에 대해 이야기할 것입니다. 이는 반대 효과를 표현합니다. 이는 특정 값을 반환함으로써 언제든지 중단될 수 있는 계산입니다.

알고리즘 구현

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 클래스 구현을 통해 자동으로 유지 관리됩니다. 경로의 모든 정점을 재귀 함수에서 반환된 결과에 넣기만 하면 됩니다.

나의 첫 번째 아이디어는 우리에게 필요한 효과를 정확하게 구현하는 것으로 보이는 양쪽 모나드를 사용하는 것이었습니다. 제가 작성한 첫 번째 구현은 이 옵션에 매우 가깝습니다. 사실, 저는 한 지점에서 다섯 가지 다른 구현을 수행했고 결국 다른 구현으로 결정했습니다.

첫째, 공유 식별자의 연관 배열을 유지해야 합니다. 이는 State에 관한 것입니다. 둘째, 충돌이 감지되면 중지할 수 있어야 합니다. 이는 둘 중 하나를 위한 Monad일 수도 있고 Maybe를 위한 MonadPlus일 수도 있습니다. 주요 차이점은 계산이 중지되지 않은 경우 둘 중 하나가 값을 반환할 수 있고 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는 우리가 엣지를 방문하는 부분입니다. 각 가장자리에 대해 두 번 호출됩니다. 여기서는 반대편 정점을 방문했는지 확인하고 그렇지 않은 경우 방문합니다. 방문하면 가장자리가 충돌하는지 확인합니다. 만약 그렇다면, 우리는 재귀 스택의 맨 위 값을 반환하며, 반환 시 다른 모든 정점이 배치됩니다.
• processVertex는 각 꼭지점을 방문했는지 여부를 확인하고 방문하지 않은 경우 inVertex를 실행합니다.
• dfs는 모든 정점에서 processVertex를 실행합니다.

그게 다야.

INLINE이라는 단어의 역사

INLINE이라는 단어는 알고리즘의 첫 번째 구현에는 없었지만 나중에 나타났습니다. 더 나은 구현을 찾으려고 노력했을 때 INLINE이 아닌 버전이 일부 그래프에서 눈에 띄게 느려지는 것을 발견했습니다. 기능이 의미상 동일하게 작동해야 한다는 점을 고려하면 이는 매우 놀랐습니다. 더 이상하게도, 다른 버전의 GHC를 사용하는 다른 컴퓨터에서는 눈에 띄는 차이가 없었습니다.

일주일 동안 GHC Core 출력을 읽은 후 명시적인 INLINE 한 줄로 문제를 해결할 수 있었습니다. GHC 8.4.4와 GHC 8.6.5 사이의 어느 시점에서 최적화 프로그램은 이 작업을 자체적으로 중단했습니다.

나는 Haskell 프로그래밍에서 그런 먼지를 만날 것이라고는 예상하지 못했습니다. 그러나 오늘날에도 옵티마이저는 때때로 실수를 하며, 그들에게 힌트를 주는 것이 우리의 임무입니다. 예를 들어 여기서 우리는 함수가 명령형 버전에서 인라인되기 때문에 인라인되어야 한다는 것을 알고 있으며 이것이 컴파일러에 힌트를 제공하는 이유입니다.

다음에 무슨 일이 있었던거야?

그런 다음 다른 모나드와 함께 Hopcroft-Karp 알고리즘을 구현했고, 그것이 프로그램의 끝이었습니다.

Google Summer of Code 덕분에 저는 함수형 프로그래밍에 대한 실무 경험을 얻었고, 이는 다음 여름에 Jane Street에서 인턴십을 하는 데 도움이 되었을 뿐만 아니라(Habr의 지식이 풍부한 청중들 사이에서도 이 곳이 얼마나 잘 알려져 있는지는 모르겠지만, 함수형 프로그래밍에 참여하기 위해 여름을 보낼 수 있는 소수의 곳 중) 뿐만 아니라 전통적인 언어에서의 경험과는 상당히 다른 이 패러다임을 실제로 적용하는 멋진 세계를 소개했습니다.

출처 : habr.com