O verán pasado participei - un programa para estudantes de Google. Cada ano, os organizadores seleccionan varios proxectos de código aberto, incluso de organizacións tan coñecidas como и . Google invita a estudantes de todo o mundo a traballar nestes proxectos.
Como participante de Google Summer of Code 2019, fixen un proxecto dentro da biblioteca coa organización , que está a desenvolver a linguaxe Haskell, unha das linguaxes de programación funcionais máis famosas. Alga é unha biblioteca que representa representación para gráficos en Haskell. Utilízase, por exemplo, en — unha biblioteca de Github que constrúe árbores semánticas, gráficas de chamadas e dependencias baseadas no código e pode comparalas. O meu proxecto consistía en engadir unha representación de tipo seguro para gráficos e algoritmos bipartitos para esa representación.
Neste post falarei da miña implementación dun algoritmo para comprobar a bipartitidade dun gráfico en Haskell. Aínda que o algoritmo é un dos máis básicos, implementalo moi ben nun estilo funcional levoume varias iteracións e requiriu bastante traballo. Como resultado, decidín unha implementación con transformadores de mónadas.
Sobre min
Chámome Vasily Alferov, son estudante de cuarto ano na HSE de San Petersburgo. Antes no blog escribín и . Agora mesmo estou en prácticas en en Noruega, onde estou traballando en enfoques do problema . Os meus intereses inclúen os algoritmos parametrizados e a programación funcional.
Sobre a implementación do algoritmo
Prefacio
Recoméndase encarecidamente aos estudantes que participen no programa que fagan un blogue. Ofrecéronme unha plataforma para o blog . Este artigo é unha tradución , escrito por min alí en xullo en inglés, cun pequeno prefacio.
Pódese atopar Pull Request co código en cuestión .
Podes ler sobre os resultados do meu traballo (en inglés) .
Con esta entrada preténdese familiarizar ao lector cos conceptos básicos da programación funcional, aínda que tentarei recordar todos os termos empregados cando chegue o momento.
Comprobación de gráficos para o bipartitismo
Nun curso sobre algoritmos adoita dar un algoritmo para comprobar a bipartididade dun gráfico como un dos algoritmos de gráficos máis sinxelos. A súa idea é sinxela: primeiro dalgunha maneira poñemos vértices na parte esquerda ou dereita, e cando se atopa unha aresta en conflito, afirmamos que o gráfico non é bipartito.
Un pouco máis de detalle: primeiro poñemos algún vértice na parte esquerda. Obviamente, todos os veciños deste vértice deben estar no lóbulo dereito. Ademais, todos os veciños dos veciños deste vértice deben estar no lóbulo esquerdo, etc. Seguimos asignando recursos compartidos a vértices mentres aínda haxa vértices no compoñente conectado do vértice co que comezamos que non teñamos asignados veciños. Despois repetimos esta acción para todos os compoñentes conectados.
Se hai unha aresta entre os vértices que caen na mesma partición, non é difícil atopar un ciclo impar no gráfico, o que é moi coñecido (e obviamente) imposible nun gráfico bipartito. En caso contrario, temos unha partición correcta, o que significa que o gráfico é bipartito.
Normalmente, este algoritmo implícase usando ou . Nas linguas imperativas, adoita utilizarse a busca en profundidade xa que é un pouco máis sinxela e non require estruturas de datos adicionais. Tamén escollín a busca en profundidade xa que é máis tradicional.
Así, chegamos ao seguinte esquema. Percorremos os vértices da gráfica mediante a busca en profundidade e asignámoslles partes compartidas, cambiando o número da parte a medida que nos movemos polo bordo. Se tentamos asignar un recurso compartido a un vértice que xa ten un recurso compartido, podemos dicir con seguridade que o gráfico non é bipartito. No momento en que todos os vértices teñen asignada unha parte e miramos todos os bordos, temos unha boa partición.
Pureza dos cálculos
En Haskell asumimos que todos os cálculos son limpar. Non obstante, se este fose realmente o caso, non teríamos forma de imprimir nada na pantalla. En todo, limpo os cálculos son tan preguiceiros que non hai un limpar razóns para calcular algo. Todos os cálculos que se producen no programa son forzados dalgún xeito "impuro" mónada IO.
As mónadas son unha forma de representar os cálculos efectos en Haskell. Explicar como funcionan está fóra do alcance desta publicación. Pódese ler unha boa e clara descrición en inglés .
Aquí quero sinalar que aínda que algunhas mónadas, como IO, se implementan mediante a maxia do compilador, case todas as outras están implementadas en software e todos os cálculos nelas son puros.
Hai moitos efectos e cada un ten a súa propia mónada. Esta é unha teoría moi forte e fermosa: todas as mónadas implementan a mesma interface. Falaremos das seguintes tres mónadas:
- Ou e a é un cálculo que devolve un valor de tipo a ou arroxa unha excepción de tipo e. O comportamento desta mónada é moi semellante ao manexo de excepcións en linguas imperativas: os erros pódense detectar ou transmitir. A principal diferenza é que a mónada está completamente implementada loxicamente na biblioteca estándar de Haskell, mentres que as linguaxes imperativas adoitan usar mecanismos do sistema operativo.
- O estado s a é un cálculo que devolve un valor de tipo a e ten acceso a un estado mutable de tipo s.
- Quizais a. A mónada Quizais expresa un cálculo que se pode interromper en calquera momento devolvendo Nada. Non obstante, falaremos da implementación da clase MonadPlus para o tipo Maybe, que expresa o efecto contrario: é un cálculo que se pode interromper en calquera momento devolvendo un valor específico.
Implantación do algoritmo
Temos dous tipos de datos, Gráfico a e Bigraph a b, o primeiro dos cales representa gráficos con vértices etiquetados con valores de tipo a, e o segundo representa gráficos bipartitos con vértices do lado esquerdo etiquetados con valores de tipo a e dereito. -vértices laterais etiquetados con valores de tipo b.
Estes non son tipos da biblioteca Alga. Alga non ten unha representación para os gráficos bipartitos non dirixidos. Fixen os tipos como este para claridade.
Tamén necesitaremos funcións auxiliares coas seguintes sinaturas:
-- Список соседей данной вершины.
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)É doado ver que se durante a busca en profundidade atopamos un bordo conflitivo, o ciclo impar atópase enriba da pila de recursión. Así, para restauralo, necesitamos cortar todo, desde a pila de recursión ata a primeira aparición do último vértice.
Implementamos a busca en profundidade mantendo unha matriz asociativa de números de compartición para cada vértice. A pila de recursividade manterase automaticamente mediante a implementación da clase Functor da mónada que eliximos: só necesitaremos poñer todos os vértices do camiño no resultado devolto pola función recursiva.
A miña primeira idea foi usar a mónada Either, que parece implementar exactamente os efectos que necesitamos. A primeira implementación que escribín estivo moi preto desta opción. De feito, tiven cinco implementacións diferentes nun momento e finalmente decidín con outra.
En primeiro lugar, necesitamos manter unha matriz asociativa de identificadores de compartición; isto é algo sobre Estado. En segundo lugar, temos que ser capaces de parar cando se detecta un conflito. Isto pode ser Monad for Either ou MonadPlus para Maybe. A principal diferenza é que Calquera pode devolver un valor se o cálculo non se detivo, e Quizais só devolve información sobre isto neste caso. Como non necesitamos un valor separado para o éxito (xa está almacenado en Estado), escollemos Quizais. E no momento no que necesitamos combinar os efectos de dúas mónadas, saen , que precisamente combinan estes efectos.
Por que escollín un tipo tan complexo? Dúas razóns. En primeiro lugar, a implementación resulta ser moi semellante ao imperativo. En segundo lugar, necesitamos manipular o valor de retorno en caso de conflito cando volvemos de recursividade para restaurar o bucle impar, que é moito máis doado de facer na mónada Maybe.
Así conseguimos esta implementación.
{-# 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 bloque onde é o núcleo do algoritmo. Intentarei explicar o que está a pasar no seu interior.
- inVertex é a parte da busca en profundidade onde visitamos o vértice por primeira vez. Aquí asignamos un número de compartición ao vértice e executamos onEdge en todos os veciños. Tamén é aquí onde restauramos a pila de chamadas: se msum devolveu un valor, colocamos o vértice v alí.
- onEdge é a parte onde visitamos o bordo. Chámase dúas veces por cada bordo. Aquí comprobamos se o vértice do outro lado foi visitado, e visitámolo se non. Se se visita, comprobamos se o bordo é conflitivo. Se é así, devolvemos o valor, a parte superior da pila de recursividade, onde todos os demais vértices se colocarán ao regresar.
- processVertex comproba para cada vértice se foi visitado e executa inVertex nel se non.
- dfs executa processVertex en todos os vértices.
Isto é todo.
Historia da palabra INLINE
A palabra INLINE non estaba na primeira implementación do algoritmo; apareceu máis tarde. Cando intentei atopar unha implementación mellor, descubrín que a versión non INLINE era notablemente máis lenta nalgúns gráficos. Tendo en conta que semanticamente as funcións deberían funcionar igual, isto sorprendeume moito. Aínda máis estraño, noutra máquina cunha versión diferente de GHC non había diferenzas notables.
Despois de pasar unha semana lendo a saída de GHC Core, puiden solucionar o problema cunha liña de INLINE explícita. Nalgún momento entre GHC 8.4.4 e GHC 8.6.5 o optimizador deixou de facelo por si só.
Non esperaba atopar tanta suciedade na programación de Haskell. Non obstante, aínda hoxe en día, os optimizadores cometen erros ás veces e o noso traballo é darlles pistas. Por exemplo, aquí sabemos que a función debe estar inlineada porque está inlineada na versión imperativa, e esta é unha razón para darlle unha pista ao compilador.
Que pasou despois?
Despois implementei o algoritmo Hopcroft-Karp con outras mónadas, e ese foi o final do programa.
Grazas a Google Summer of Code, adquirei experiencia práctica en programación funcional, o que non só me axudou a facer prácticas en Jane Street o verán seguinte (non estou seguro de que tan coñecido é este lugar mesmo entre o público coñecedor de Habr, pero é un dos poucos onde podes veranear para dedicarme á programación funcional), pero tamén me introduciu no marabilloso mundo de aplicar este paradigma na práctica, significativamente diferente da miña experiencia nas linguas tradicionais.
Fonte: www.habr.com