El verano pasado participé en - un programa para estudiantes de Google. Cada año, los organizadores seleccionan varios proyectos de código abierto, incluidos los de organizaciones tan conocidas como и . Google invita a estudiantes de todo el mundo a trabajar en estos proyectos.
Como participante de Google Summer of Code 2019, realicé un proyecto dentro de la biblioteca con la organizacion , que está desarrollando el lenguaje Haskell, uno de los lenguajes de programación funcional más famosos. Alga es una biblioteca que representa representación de gráficos en Haskell. Se utiliza, por ejemplo, en - una biblioteca de Github que crea árboles semánticos, gráficos de llamadas y dependencias basados en código y puede compararlos. Mi proyecto era agregar una representación con seguridad de tipos para gráficos bipartitos y algoritmos para esa representación.
En esta publicación hablaré sobre mi implementación de un algoritmo para verificar la bipartición de un gráfico en Haskell. Aunque el algoritmo es uno de los más básicos, implementarlo maravillosamente en un estilo funcional me llevó varias iteraciones y requirió bastante trabajo. Como resultado, me decidí por una implementación con transformadores de mónada.
Acerca de mí
Mi nombre es Vasily Alferov, soy estudiante de cuarto año en la HSE de San Petersburgo. Anteriormente en el blog escribí и . Ahora mismo estoy haciendo prácticas en en Noruega, donde estoy trabajando en enfoques para el problema . Mis intereses incluyen algoritmos parametrizados y programación funcional.
Sobre la implementación del algoritmo.
prefacio
Se recomienda encarecidamente a los estudiantes que participan en el programa que escriban blogs. Me proporcionaron una plataforma para el blog. . Este artículo es una traducción. , escrito por mí allí en julio en inglés, con un breve prefacio.
Se puede encontrar la solicitud de extracción con el código en cuestión. .
Puedes leer sobre los resultados de mi trabajo (en inglés) .
Esta publicación asume que el lector está familiarizado con los conceptos básicos de la programación funcional, aunque intentaré recordar todos los términos utilizados cuando llegue el momento.
Comprobación de gráficos para determinar si hay bipartidismo
Un algoritmo para verificar la bipartición de un gráfico generalmente se proporciona en un curso sobre algoritmos como uno de los algoritmos de gráficos más simples. Su idea es sencilla: primero, de alguna manera colocamos vértices en el lado izquierdo o derecho, y cuando se encuentra un borde en conflicto, afirmamos que el gráfico no es bipartito.
Un poco más de detalle: primero ponemos algún vértice en el recurso compartido izquierdo. Obviamente, todos los vecinos de este vértice deben estar en el lóbulo derecho. Además, todos los vecinos de los vecinos de este vértice deben estar en el lóbulo izquierdo, y así sucesivamente. Continuamos asignando recursos compartidos a los vértices siempre que todavía haya vértices en el componente conectado del vértice con el que comenzamos y al que no hayamos asignado vecinos. Luego repetimos esta acción para todos los componentes conectados.
Si hay una arista entre los vértices que caen en la misma partición, no es difícil encontrar un ciclo impar en el gráfico, lo cual es ampliamente conocido (y obviamente) imposible en un gráfico bipartito. De lo contrario, tenemos una partición correcta, lo que significa que el gráfico es bipartito.
Normalmente, este algoritmo se implementa utilizando o . En los lenguajes imperativos, se suele utilizar la búsqueda en profundidad, ya que es un poco más sencilla y no requiere estructuras de datos adicionales. También elegí la búsqueda en profundidad porque es más tradicional.
Así llegamos al siguiente esquema. Atravesamos los vértices del gráfico utilizando la búsqueda en profundidad y les asignamos acciones, cambiando el número de acciones a medida que nos movemos a lo largo del borde. Si intentamos asignar una parte a un vértice que ya tiene una parte asignada, podemos decir con seguridad que el gráfico no es bipartito. En el momento en que a todos los vértices se les asigna una parte y hemos observado todos los bordes, tenemos una buena partición.
Pureza de los cálculos
En Haskell asumimos que todos los cálculos son limpio Sin embargo, si este fuera realmente el caso, no tendríamos forma de imprimir nada en la pantalla. En absoluto, limpio Los cálculos son tan vagos que no hay uno. limpio Razones para calcular algo. Todos los cálculos que ocurren en el programa se ven obligados de alguna manera a "inmundo" mónada IO.
Las mónadas son una forma de representar cálculos con efectos en Haskel. Explicar cómo funcionan está más allá del alcance de esta publicación. Se puede leer una descripción buena y clara en inglés. .
Aquí quiero señalar que, si bien algunas mónadas, como IO, se implementan mediante la magia del compilador, casi todas las demás se implementan en software y todos los cálculos en ellas son puros.
Hay muchos efectos y cada uno tiene su propia mónada. Esta es una teoría muy fuerte y hermosa: todas las mónadas implementan la misma interfaz. Hablaremos de las siguientes tres mónadas:
- O ea es un cálculo que devuelve un valor de tipo a o genera una excepción de tipo e. El comportamiento de esta mónada es muy similar al manejo de excepciones en lenguajes imperativos: los errores pueden detectarse o transmitirse. La principal diferencia es que la mónada se implementa de forma completamente lógica en la biblioteca estándar de Haskell, mientras que los lenguajes imperativos suelen utilizar mecanismos del sistema operativo.
- El estado sa es un cálculo que devuelve un valor de tipo a y tiene acceso al estado mutable de tipo s.
- Tal vez un. La mónada Maybe expresa un cálculo que puede interrumpirse en cualquier momento devolviendo Nothing. Sin embargo, hablaremos de la implementación de la clase MonadPlus para el tipo Maybe, que expresa el efecto contrario: es un cálculo que puede interrumpirse en cualquier momento devolviendo un valor específico.
Implementación del algoritmo.
Tenemos dos tipos de datos, Graph a y Bigraph ab, el primero de los cuales representa gráficos con vértices etiquetados con valores de tipo a, y el segundo representa gráficos bipartitos con vértices del lado izquierdo etiquetados con valores de tipo a y derecho. -vértices laterales etiquetados con valores de tipo b.
Estos no son tipos de la biblioteca de Alga. Alga no tiene representación para gráficos bipartitos no dirigidos. Hice los tipos como este para mayor claridad.
También necesitaremos funciones auxiliares con las siguientes firmas:
-- Список соседей данной вершины.
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)Es fácil ver que si durante la búsqueda en profundidad encontramos un borde conflictivo, el ciclo impar se encuentra en la parte superior de la pila de recursividad. Por lo tanto, para restaurarlo, necesitamos cortar todo, desde la pila de recursividad hasta la primera aparición del último vértice.
Implementamos la búsqueda en profundidad manteniendo una matriz asociativa de números compartidos para cada vértice. La pila de recursividad se mantendrá automáticamente mediante la implementación de la clase Functor de la mónada que hemos elegido: solo necesitaremos colocar todos los vértices de la ruta en el resultado devuelto por la función recursiva.
Mi primera idea fue utilizar la mónada Cualquiera, que parece implementar exactamente los efectos que necesitamos. La primera implementación que escribí estaba muy cerca de esta opción. De hecho, tuve cinco implementaciones diferentes en un momento y finalmente me decidí por otra.
Primero, necesitamos mantener una matriz asociativa de identificadores de acciones; esto es algo relacionado con el Estado. En segundo lugar, debemos poder detenernos cuando se detecte un conflicto. Puede ser Monad para Cualquiera o MonadPlus para Quizás. La principal diferencia es que Both puede devolver un valor si el cálculo no se ha detenido, y Maybe devuelve sólo información sobre este en este caso. Como no necesitamos un valor separado para el éxito (ya está almacenado en Estado), elegimos Quizás. Y en el momento en que necesitamos combinar los efectos de dos mónadas, salen , que combinan precisamente estos efectos.
¿Por qué elegí un tipo tan complejo? Dos razones. En primer lugar, la implementación resulta muy similar a la imperativa. En segundo lugar, necesitamos manipular el valor de retorno en caso de conflicto al regresar de la recursividad para restaurar el bucle impar, lo cual es mucho más fácil de hacer en la mónada Maybe.
Así obtenemos 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)
El bloque donde es el núcleo del algoritmo. Intentaré explicar lo que sucede en su interior.
- inVertex es la parte de la búsqueda en profundidad donde visitamos el vértice por primera vez. Aquí asignamos un número compartido al vértice y ejecutamos onEdge en todos los vecinos. Aquí también es donde restauramos la pila de llamadas: si msum devolvió un valor, empujamos el vértice v allí.
- onEdge es la parte donde visitamos el borde. Se llama dos veces para cada arista. Aquí comprobamos si el vértice del otro lado ha sido visitado y lo visitamos en caso contrario. Si se visita, comprobamos si el borde está en conflicto. Si es así, devolvemos el valor: la parte superior de la pila de recursividad, donde se colocarán todos los demás vértices al regresar.
- ProcessVertex comprueba si cada vértice ha sido visitado y, en caso contrario, ejecuta inVertex en él.
- dfs ejecuta ProcessVertex en todos los vértices.
Eso es todo.
Historia de la palabra EN LÍNEA
La palabra INLINE no estuvo en la primera implementación del algoritmo; apareció más tarde. Cuando intenté encontrar una mejor implementación, descubrí que la versión que no está EN LÍNEA era notablemente más lenta en algunos gráficos. Teniendo en cuenta que semánticamente las funciones deberían funcionar igual, esto me sorprendió mucho. Aún más extraño, en otra máquina con una versión diferente de GHC no hubo ninguna diferencia notable.
Después de pasar una semana leyendo el resultado de GHC Core, pude solucionar el problema con una línea INLINE explícita. En algún momento entre GHC 8.4.4 y GHC 8.6.5, el optimizador dejó de hacer esto por sí solo.
No esperaba encontrar tanta suciedad en la programación de Haskell. Sin embargo, incluso hoy en día, los optimizadores a veces cometen errores y nuestro trabajo es darles pistas. Por ejemplo, aquí sabemos que la función debe estar incorporada porque está incorporada en la versión imperativa, y esta es una razón para darle una pista al compilador.
¿Qué pasó después?
Luego implementé el algoritmo Hopcroft-Karp con otras mónadas y ese fue el final del programa.
Gracias a Google Summer of Code, obtuve experiencia práctica en programación funcional, lo que no solo me ayudó a conseguir una pasantía en Jane Street el verano siguiente (no estoy seguro de qué tan conocido es este lugar incluso entre la audiencia conocedora de Habr, pero es uno de los pocos donde puedes dedicarte en verano a la programación funcional), pero también me introdujo al maravilloso mundo de aplicar este paradigma en la práctica, significativamente diferente de mi experiencia en lenguajes tradicionales.
Fuente: habr.com