No verão passado participei - um programa para estudantes do Google. Todos os anos, os organizadores selecionam vários projetos de código aberto, inclusive de organizações conhecidas como и . O Google convida estudantes de todo o mundo para trabalhar nesses projetos.
Como participante do Google Summer of Code 2019, fiz um projeto dentro da biblioteca com a organização , que está desenvolvendo a linguagem Haskell - uma das linguagens de programação funcional mais famosas. Alga é uma biblioteca que representa representação para gráficos em Haskell. É usado, por exemplo, em - uma biblioteca Github que constrói árvores semânticas, gráficos de chamadas e dependências com base em código e pode compará-los. Meu projeto era adicionar uma representação de tipo seguro para gráficos e algoritmos bipartidos para essa representação.
Neste post falarei sobre minha implementação de um algoritmo para verificar a bipartição de um gráfico em Haskell. Embora o algoritmo seja um dos mais básicos, implementá-lo lindamente em um estilo funcional exigiu várias iterações e exigiu muito trabalho. Como resultado, optei por uma implementação com transformadores mônadas.
Quem sou eu
Meu nome é Vasily Alferov, sou um estudante do quarto ano da Escola Superior de Economia de São Petersburgo. Anteriormente no blog eu escrevi и . Neste momento estou em estágio na na Noruega, onde estou trabalhando em abordagens para o problema . Meus interesses incluem algoritmos parametrizados e programação funcional.
Sobre a implementação do algoritmo
Prefácio
Os alunos que participam do programa são fortemente incentivados a blogar. Eles me forneceram uma plataforma para o blog . Este artigo é uma tradução , escrito por mim lá em julho em inglês, com um breve prefácio.
Pull Request com o código em questão pode ser encontrado .
Você pode ler sobre os resultados do meu trabalho (em inglês) .
Este post tem como objetivo familiarizar o leitor com os conceitos básicos de programação funcional, embora tentarei relembrar todos os termos utilizados quando chegar a hora.
Verificando gráficos para bipartidaridade
Um algoritmo para verificar a bipartitidade de um gráfico é geralmente fornecido em um curso sobre algoritmos como um dos algoritmos de gráfico mais simples. Sua ideia é direta: primeiro, de alguma forma, colocamos vértices no compartilhamento esquerdo ou direito e, quando uma aresta conflitante é encontrada, afirmamos que o grafo não é bipartido.
Um pouco mais de detalhe: primeiro colocamos algum vértice no share esquerdo. Obviamente, todos os vizinhos deste vértice devem estar no lobo direito. Além disso, todos os vizinhos deste vértice devem estar no lobo esquerdo e assim por diante. Continuamos atribuindo compartilhamentos aos vértices enquanto ainda houver vértices no componente conectado do vértice com o qual começamos e aos quais não atribuímos vizinhos. Em seguida, repetimos esta ação para todos os componentes conectados.
Se houver uma aresta entre vértices que caem na mesma partição, não será difícil encontrar um ciclo ímpar no grafo, o que é amplamente conhecido (e obviamente) impossível em um grafo bipartido. Caso contrário, temos uma partição correta, o que significa que o gráfico é bipartido.
Normalmente, este algoritmo é implementado usando ou . Em linguagens imperativas, a pesquisa em profundidade é geralmente usada porque é um pouco mais simples e não requer estruturas de dados adicionais. Também escolhi a pesquisa em profundidade por ser mais tradicional.
Assim, chegamos ao seguinte esquema. Atravessamos os vértices do gráfico usando a pesquisa em profundidade e atribuímos compartilhamentos a eles, alterando o número do compartilhamento à medida que nos movemos ao longo da aresta. Se tentarmos atribuir um compartilhamento a um vértice que já possui um compartilhamento atribuído, podemos dizer com segurança que o grafo não é bipartido. No momento em que todos os vértices recebem um compartilhamento e olhamos todas as arestas, temos uma boa partição.
Pureza dos cálculos
Em Haskell assumimos que todos os cálculos são limpo. No entanto, se este fosse realmente o caso, não teríamos como imprimir nada na tela. De forma alguma, limpar os cálculos são tão preguiçosos que não há um limpo razões para calcular algo. Todos os cálculos que ocorrem no programa são de alguma forma forçados a "imundo" mônada IO.
Mônadas são uma forma de representar cálculos com efeitos em Haskell. Explicar como eles funcionam está além do escopo desta postagem. Uma descrição boa e clara pode ser lida em inglês .
Quero salientar aqui que, embora algumas mônadas, como IO, sejam implementadas por meio da magia do compilador, quase todas as outras são implementadas em software e todos os cálculos nelas contidos 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. Falaremos sobre as três mônadas a seguir:
- Ou ea é um cálculo que retorna um valor do tipo a ou lança uma exceção do tipo e. O comportamento desta 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 é implementada de forma totalmente lógica na biblioteca padrão em Haskell, enquanto as linguagens imperativas geralmente usam mecanismos do sistema operacional.
- Estado sa é um cálculo que retorna um valor do tipo a e tem acesso ao estado mutável do tipo s.
- Talvez um. A mônada Maybe expressa um cálculo que pode ser interrompido a qualquer momento retornando Nothing. Porém, falaremos sobre a implementação da classe MonadPlus para o tipo Maybe, que expressa o efeito oposto: é um cálculo que pode ser interrompido a qualquer momento retornando um valor específico.
Implementação do algoritmo
Temos dois tipos de dados, Graph a e Bigraph ab, o primeiro dos quais representa gráficos com vértices rotulados com valores do tipo a, e o segundo representa gráficos bipartidos com vértices do lado esquerdo rotulados com valores do tipo a e direito vértices laterais rotulados com valores do tipo b.
Estes não são tipos da biblioteca Alga. Alga não possui representação para grafos bipartidos não direcionados. Eu fiz os tipos assim para maior clareza.
Também precisaremos de funções auxiliares com as seguintes assinaturas:
-- Список соседей данной вершины.
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)É fácil ver que se durante a busca em profundidade encontramos uma aresta conflitante, o ciclo ímpar fica no topo da pilha de recursão. Assim, para restaurá-lo, precisamos cortar tudo, desde a pilha de recursão até a primeira ocorrência do último vértice.
Implementamos a pesquisa em profundidade mantendo uma matriz associativa de números de compartilhamento para cada vértice. A pilha de recursão será mantida automaticamente através da implementação da classe Functor da mônada que escolhemos: precisaremos apenas colocar todos os vértices do caminho no resultado retornado pela função recursiva.
Minha primeira ideia foi usar a mónada Both, que parece implementar exatamente os efeitos que precisamos. A primeira implementação que escrevi estava muito próxima dessa opção. Na verdade, tive cinco implementações diferentes em um ponto e acabei optando por outra.
Primeiro, precisamos manter uma matriz associativa de identificadores de compartilhamento – isso é algo sobre Estado. Em segundo lugar, precisamos de ser capazes de parar quando é detectado um conflito. Pode ser Monad para qualquer um ou MonadPlus para talvez. A principal diferença é que Both pode retornar um valor se o cálculo não tiver sido interrompido, e Maybe retorna apenas informações sobre isso neste caso. Como não precisamos de um valor separado para o sucesso (ele já está armazenado no Estado), escolhemos Talvez. E no momento em que precisamos combinar os efeitos de duas mônadas, elas saem , que combinam precisamente esses efeitos.
Por que escolhi um tipo tão complexo? Duas razões. Em primeiro lugar, a implementação acaba por ser muito semelhante à imperativa. Segundo, precisamos manipular o valor de retorno em caso de conflito ao retornar da recursão para restaurar o loop ímpar, o que é muito mais fácil de fazer na mônada Maybe.
Assim, obtemos esta 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 <- 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)
O bloco where é o núcleo do algoritmo. Vou tentar explicar o que está acontecendo dentro dele.
- inVertex é a parte da pesquisa em profundidade onde visitamos o vértice pela primeira vez. Aqui atribuímos um número de compartilhamento ao vértice e executamos onEdge em todos os vizinhos. É aqui também que restauramos a pilha de chamadas: se msum retornou um valor, colocamos o vértice v lá.
- onEdge é a parte onde visitamos a borda. É chamado duas vezes para cada aresta. Aqui verificamos se o vértice do outro lado foi visitado e, caso contrário, visitamos. Se visitado, verificamos se a aresta é conflitante. Se for, retornamos o valor - o topo da pilha de recursão, onde todos os outros vértices serão colocados no retorno.
- processVertex verifica cada vértice se ele foi visitado e executa inVertex nele, caso contrário.
- dfs executa processVertex em todos os vértices.
Isso é tudo.
História da palavra INLINE
A palavra INLINE não estava na primeira implementação do algoritmo; apareceu mais tarde. Quando tentei encontrar uma implementação melhor, descobri que a versão não INLINE era visivelmente mais lenta em alguns gráficos. Considerando que semanticamente as funções deveriam funcionar da mesma forma, isso me surpreendeu muito. Ainda mais estranho, em outra máquina com uma versão diferente do GHC não houve diferença perceptível.
Depois de passar uma semana lendo a saída do GHC Core, consegui resolver o problema com uma linha de INLINE explícito. Em algum momento entre o GHC 8.4.4 e o GHC 8.6.5, o otimizador parou de fazer isso sozinho.
Eu não esperava encontrar tanta sujeira na programação Haskell. No entanto, ainda hoje, os otimizadores às vezes cometem erros e é nosso trabalho dar-lhes dicas. Por exemplo, aqui sabemos que a função deve ser embutida porque está embutida na versão imperativa, e este é um motivo para dar uma dica ao compilador.
O que aconteceu depois?
Então implementei o algoritmo Hopcroft-Karp com outras mônadas e esse foi o fim do programa.
Graças ao Google Summer of Code, ganhei experiência prática em programação funcional, o que não só me ajudou a conseguir um estágio na Jane Street no verão seguinte (não tenho certeza de quão conhecido esse lugar é, mesmo entre o público experiente de Habr, mas é um dos poucos onde você pode praticar programação funcional), mas também me apresentou ao maravilhoso mundo da aplicação desse paradigma na prática, significativamente diferente da minha experiência em linguagens tradicionais.
Fonte: habr.com