No verão passado, participei de — um programa para estudantes da Google. Todos os anos, os organizadores selecionam vários projetos de Código Aberto, incluindo aqueles de organizações renomadas como e . Para trabalhar nesses projetos, a Google convida estudantes de todo o mundo.
Como participante do Google Summer of Code 2019, desenvolvi um projeto dentro da biblioteca com a organização , que se dedica ao desenvolvimento da linguagem Haskell — uma das linguagens funcionais mais conhecidas. Alga é uma biblioteca que representa tipada de forma segura para grafos em Haskell. Ela é usada, por exemplo, em — uma biblioteca da Github que constrói, a partir do código, árvores semânticas, grafos de chamadas e dependências, podendo compará-los. Meu projeto consistiu em adicionar ali uma representação tipada de forma segura para grafos bipartidos e algoritmos para essa representação.
Neste post, vou falar sobre a implementação do algoritmo de verificação de bipartição de grafos em Haskell. Embora o algoritmo seja um dos mais básicos, sua implementação elegante em estilo funcional levou várias iterações e exigiu bastante trabalho. No final, optei por uma implementação com transformadores monádicos.
Sobre mim
Meu nome é Vasily Alfyórv, sou estudante do quarto ano da Higher School of Economics de São Petersburgo. Anteriormente, escrevi neste blog e . Neste exato momento, estou em um estágio na na Noruega, onde estou explorando abordagens para o problema de . Meus interesses incluem algoritmos parametrizados e programação funcional.
Sobre a implementação do algoritmo
Prefácio
Os estudantes que participam do programa são fortemente incentivados a manter um blog. Para meu blog, foi oferecida uma plataforma chamada . Este artigo é uma tradução , que escrevi para lá em julho, em inglês, com um breve prefácio.
O Pull Request com o código mencionado pode ser encontrado .
Sobre os resultados do meu trabalho, você pode ler (em inglês) .
O post presume que o leitor tenha familiaridade com os conceitos básicos de programação funcional, embora eu tente relembrar todos os termos utilizados quando chegarmos a eles.
Verificação de grafos bipartidos
O algoritmo para verificar se um grafo é bipartido geralmente é apresentado em cursos de algoritmos como um dos algoritmos de grafo mais simples. Sua ideia é direta: primeiro, colocamos de algum modo os vértices na parte esquerda ou direita, e ao detectar uma aresta conflitante, afirmamos que o grafo não é bipartido.
Um pouco mais detalhadamente: primeiro, colocamos um vértice na parte esquerda. É evidente que todos os vizinhos desse vértice devem estar na parte direita. Em seguida, todos os vizinhos dos vizinhos desse vértice devem estar na parte esquerda, e assim por diante. Continuamos atribuindo partes aos vértices até que, no componente de conectividade do vértice com o qual começamos, ainda existam vértices aos quais não designamos vizinhos. Então, repetimos essa ação para todos os componentes de conectividade.
Se houver uma aresta entre vértices que caíram na mesma parte, não é difícil encontrar um ciclo ímpar no grafo, como é amplamente conhecido (e bastante óbvio) impossível em um grafo bipartido. Caso contrário, temos uma partição correta em partes, e portanto, o grafo é bipartido.
Como regra geral, esse algoritmo é implementado com ou . Em linguagens imperativas, geralmente se usa busca em profundidade, que é um pouco mais simples e não requer estruturas de dados adicionais. Eu também escolhi busca em profundidade como a mais tradicional.
Assim, chegamos ao seguinte esquema. Percorremos os vértices do grafo usando busca em profundidade e atribuímos a eles partes, trocando o número da parte ao passar por uma aresta. Se tentarmos atribuir uma parte a um vértice que já tem uma parte designada, podemos afirmar com confiança que o grafo não é bipartido. No momento em que todas as partes foram atribuídas aos vértices e verificamos todas as arestas, temos uma boa partição.
Pureza dos cálculos
Em Haskell, presumimos que todos os cálculos são puros. No entanto, se realmente fosse assim, não teríamos a capacidade de imprimir nada na tela. De modo geral, cálculos puros são tão preguiçosos que não existe nenhuma razão para calcular algo. Todos os cálculos que ocorrem no programa, de uma forma ou de outra, são forçados na monada 'não pura'. Monad é uma forma de representar cálculos com
efeitos. эффектами em Haskell. A explicação de como eles funcionam está além do escopo deste post. Uma descrição boa e clara pode ser lida em inglês. .
Aqui quero observar que, enquanto algumas mônadas, como IO, são implementadas através da mágica do compilador, quase todas as outras são implementadas programaticamente e todos os cálculos nelas são puros.
Existem muitos efeitos e cada um tem sua própria mônada. Esta é uma teoria muito forte e bonita: todas as mônadas implementam a mesma interface. Vamos falar sobre as três seguintes mônadas:
- Either e a — um cálculo que retorna um valor do tipo a ou lança uma exceção do tipo e. O comportamento dessa mônada é muito semelhante ao tratamento de exceções em linguagens imperativas: erros podem ser capturados ou repassados. A principal diferença é que a mônada é totalmente implementada logicamente na biblioteca padrão em Haskell, enquanto em linguagens imperativas geralmente são usados mecanismos do sistema operacional.
- State s a — um cálculo que retorna um valor do tipo a e tem acesso a um estado mutável do tipo s.
- Maybe a. A mônada Maybe expressa um cálculo que pode ser interrompido a qualquer momento com o retorno de Nothing. No entanto, vamos falar sobre a implementação da classe MonadPlus para o tipo Maybe, que expressa o efeito oposto: este é um cálculo que pode ser interrompido a qualquer momento com o retorno de um valor específico.
Implementação do algoritmo
Temos dois tipos de dados, Graph a e Bigraph a b, sendo que o primeiro representa grafos com vértices rotulados com valores do tipo a, e o segundo representa grafos bipartidos com vértices da parte esquerda rotulados com valores do tipo a e vértices da parte direita rotulados com valores do tipo b.
Estes não são tipos da biblioteca Alga. Em Alga, não há representação para grafos bipartidos não direcionais. Eu criei os tipos desta forma para fins de clareza.
Também precisaremos de funções auxiliares com as seguintes assinaturas:
-- Lista de vizinhos deste vértice.
neighbours :: Ord a => a -> Graph a -> [a]
-- Construir um grafo bipartido a partir de um grafo e uma função que, para cada vértice, retorna sua parte e rótulo na nova parte, ignorando arestas conflitantes.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Lista de vértices no grafo
vertexList :: Ord a => Graph a -> [a]
A assinatura da função que vamos escrever se parece com isto:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Não é difícil notar que, se durante a busca em profundidade encontrarmos uma aresta conflitante, o ciclo ímpar estará no topo da pilha de recursão. Assim, para recuperá-lo, precisamos cortar a pilha de recursão até a primeira entrada do último vértice.
Implementaremos a busca em profundidade mantendo um array associativo de números de parte para cada vértice. A pilha de recursão será mantida automaticamente através da implementação da classe Functor da monada escolhida: só precisamos colocar todos os vértices no caminho no resultado retornado pela função recursiva.
Minha primeira ideia foi usar a monada Either, que parece implementar exatamente os efeitos que precisamos. A primeira implementação que escrevi era muito parecida com esta variante. Na verdade, eu tive cinco implementações diferentes em um determinado momento, e acabei me decidindo por outra.
Primeiramente, precisamos manter um array associativo de identificadores de partes — isso tem a ver com State. Em segundo lugar, precisamos ser capazes de parar em caso de detecção de um conflito. Isso pode ser ou Monad para Either, ou MonadPlus para Maybe. A principal diferença é que Either pode retornar um valor caso o cálculo não tenha sido interrompido, enquanto Maybe retorna apenas informações sobre isso. Como não precisamos de um valor separado em caso de sucesso (ele já está armazenado em State), escolhemos Maybe. E no momento em que precisamos combinar os efeitos de duas monads, aparecem , que combinam exatamente esses efeitos.
Por que escolhi um tipo tão complexo? Duas razões. Primeiro, a implementação se assemelha bastante à imperativa. Segundo, precisamos manipular o valor retornado em caso de conflito, ao voltar da recursão para restaurar um ciclo ímpar, o que é muito mais fácil de fazer na monada Maybe.
Assim, obtemos essa implementação.
{-# 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 a -> PartMonad a
onEdge p v = do m 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 [a]
oddCycle c = tail (dropWhile ((/=) last c) c)
O bloco where é o núcleo do algoritmo. Vou tentar explicar o que acontece dentro dele.
- inVertex é a parte da busca em profundidade, onde visitamos um vértice pela primeira vez. Aqui atribuímos ao vértice um número de parte e executamos onEdge para todos os vizinhos. Este também é o local onde restauramos a pilha de chamadas: se msum retornou um valor, anexamos o vértice v lá.
- onEdge — é a parte onde visitamos a borda. É chamada duas vezes para cada borda. Aqui verificamos se o vértice do outro lado já foi visitado e o visitamos se não. Se já foi visitado, verificamos se a borda é conflitiva. Se for, retornamos o valor — o topo da pilha de recursão, para onde todas as outras vértices serão anexadas ao retornar.
- processVertex verifica se cada vértice já foi visitado e inicia inVertex nele se não foi.
- dfs inicia processVertex em todos os vértices.
Isso é tudo.
A História da Palavra INLINE
A palavra INLINE não estava na primeira implementação do algoritmo, surgiu mais tarde. Quando tentei encontrar uma melhor implementação, notei que em alguns gráficos a versão sem INLINE funcionava visivelmente mais devagar. Considerando que semanticamente as funções deveriam funcionar igualmente, isso me surpreendeu bastante. Ainda mais estranho foi que em outra máquina com uma versão diferente do GHC não havia diferença perceptível.
Depois de passar uma semana lendo a saída do GHC Core, consegui corrigir o problema com uma única linha com INLINE explícito. Em algum momento entre GHC 8.4.4 e GHC 8.6.5, o otimizador parou de fazer isso automaticamente.
Não esperava encontrar tanta confusão na programação em Haskell. No entanto, otimizadores ainda cometem erros, mesmo nos dias de hoje, e dar-lhes dicas é nossa tarefa. Por exemplo, aqui sabemos que a função deve ser inlinada, uma vez que ela é inlinada na versão imperativa, e isso é motivo para dar uma dica ao compilador.
E então?
Então implementei o algoritmo de Hopcroft-Karp já com outras monadas, e com isso o programa terminou.
Graças ao Google Summer of Code, adquiri experiência prática em programação funcional, que não só me ajudou a conseguir um estágio na Jane Street no verão seguinte (não estou certo de quão conhecida essa empresa é mesmo entre o público familiarizado no Habr, mas é um dos poucos lugares onde você pode fazer programação funcional no verão), mas também me apresentou a um mundo incrível de aplicação dessa paradigma na prática, muito diferente da minha experiência em linguagens tradicionais.
Fonte: habr.com
