El verano pasado participé en un programa para estudiantes de la empresa Google. Cada año, los organizadores seleccionan varios proyectos de Open Source, incluidos algunos de organizaciones tan reconocidas como y . Para trabajar en estos proyectos, Google invita a estudiantes de todo el mundo.
Como participante de Google Summer of Code 2019, trabajé en un proyecto en el marco de la biblioteca con la organización , que se dedica al desarrollo del lenguaje Haskell, uno de los lenguajes de programación funcional más conocidos. Alga es una biblioteca que ofrece para gráficos en Haskell. Se utiliza, por ejemplo, en , una biblioteca de GitHub que construye árboles semánticos, gráficos de llamadas y dependencias a partir del código, y que puede compararlos. Mi proyecto consistió en añadir una representación segura en tipos para gráficos bipartitos y algoritmos para esa representación.
En esta publicación hablaré sobre mi implementación del algoritmo para comprobar si un gráfico es bipartito en Haskell. A pesar de que el algoritmo es uno de los más básicos, su hermosa implementación en estilo funcional me llevó varias iteraciones y requirió bastante trabajo. Como resultado, me decanté por una implementación con transformadores monádicos.
Acerca de mí
Me llamo Vasily Alfyórov, soy estudiante de cuarto año en la Universidad de San Petersburgo. Anteriormente, en el blog escribí y . En este momento estoy en una pasantía en en Noruega, donde estoy abordando el problema de . Mis áreas de interés incluyen algoritmos parametrizados y programación funcional.
Sobre la implementación del algoritmo
Prólogo
Se recomienda encarecidamente a los estudiantes que participan en el programa que mantengan un blog. Para mi blog, me proporcionaron una plataforma en . Este artículo es una traducción , que escribí allí en inglés en julio, con un pequeño prefacio.
El Pull Request con el código del que se habla se puede encontrar .
Se puede leer sobre los resultados de mi trabajo (en inglés) .
Este post asume que el lector tiene un conocimiento básico de programación funcional, aunque trataré de recordar todos los términos utilizados cuando lleguemos a ellos.
Comprobación de gráficos bipartitos
El algoritmo de verificación de bipartición de un grafo generalmente se enseña en los cursos de algoritmos como uno de los algoritmos de grafos más simples. Su idea es directa: primero, de alguna manera, colocamos los vértices en una parte izquierda o derecha, y al detectar un borde conflictivo afirmamos que el grafo no es bipartito.
Con un poco más de detalle: primero colocamos un vértice en la parte izquierda. Obviamente, todos los vecinos de este vértice deben estar en la parte derecha. Luego, todos los vecinos de los vecinos de este vértice deben estar en la parte izquierda, y así sucesivamente. Continuamos asignando partes a los vértices hasta que en el componente de conectividad del vértice con el que comenzamos aún haya vértices a los que no hemos asignado vecinos. Luego repetimos esta acción para todos los componentes de conectividad.
Si hay un borde entre vértices que han caído en la misma parte, no es difícil encontrar en el grafo un ciclo impar, que como es ampliamente sabido (y bastante obvio) es imposible en un grafo bipartito. De lo contrario, tenemos una partición válida en partes, lo que significa que el grafo es bipartito.
Como regla general, este algoritmo se implementa utilizando o . En 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. Yo también elegí la búsqueda en profundidad como la más tradicional.
Por lo tanto, hemos llegado al siguiente esquema. Recorremos los vértices del grafo mediante búsqueda en profundidad y les asignamos partes, cambiando el número de parte al pasar por un borde. Si intentamos asignar una parte a un vértice que ya tiene una parte asignada, se puede afirmar con seguridad que el grafo no es bipartito. En el momento en que a todos los vértices se les asigna una parte y hemos examinado todos los bordes, tenemos una buena partición.
Pureza de los cálculos
En Haskell suponemos que todos los cálculos son puros. Sin embargo, si realmente fuera así, no tendríamos la capacidad de imprimir nada en la pantalla. En general, los cálculos son tan perezosos que no existe una razón pura para calcular nada. Todos los cálculos que ocurren en un programa son de alguna manera forzados en una monada IO.
Las mónadas son una forma de representar cálculos con efectos. en Haskell. La explicación de cómo funcionan sale del alcance de esta publicación. Una buena y clara descripción se puede leer en inglés. .
Aquí quiero señalar que, mientras algunas mónadas, como IO, se implementan a través de la magia del compilador, casi todas las demás se implementan programáticamente 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 poderosa y hermosa: todas las mónadas implementan la misma interfaz. Hablaremos de las siguientes tres mónadas:
- Either e a — un cálculo que devuelve un valor del tipo a o lanza una excepción del tipo e. El comportamiento de esta mónada se asemeja al trabajo con excepciones en lenguajes imperativos: los errores pueden ser atrapados o pasados. La principal diferencia es que la mónada está completamente implementada lógicamente en la biblioteca estándar de Haskell, mientras que en los lenguajes imperativos generalmente se utilizan mecanismos del sistema operativo.
- State s a — un cálculo que devuelve un valor del tipo a y tiene acceso a un estado mutable del tipo s.
- Maybe a. La mónada Maybe expresa un cálculo que puede ser interrumpido en cualquier momento devolviendo Nothing. Sin embargo, hablaré de la implementación de la clase MonadPlus para el tipo Maybe, que expresa el efecto opuesto: es un cálculo que puede ser interrumpido en cualquier momento devolviendo un valor específico.
Implementación del algoritmo
Tenemos dos tipos de datos, Graph a y Bigraph a b, el primero de los cuales representa grafos con vértices etiquetados con valores del tipo a, y el segundo representa grafos bipartitos con vértices de la parte izquierda etiquetados con valores del tipo a y vértices de la parte derecha etiquetados con valores del tipo b.
Estos no son tipos de la biblioteca Alga. En Alga no hay representación para grafos bipartitos no dirigidos. Hice los tipos de esta manera para mayor claridad.
También necesitaremos funciones auxiliares con las siguientes firmas:
-- Lista de vecinos de este vértice.
neighbours :: Ord a => a -> Graph a -> [a]
-- Construir un grafo bipartito a partir de un grafo y una función que, para cada vértice, emita su parte y una etiqueta en la nueva parte, ignorando los bordes conflictivos.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Lista de vértices en el grafo
vertexList :: Ord a => Graph a -> [a]
La firma de la función que vamos a escribir se ve así:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)No es difícil notar que si durante la búsqueda en profundidad encontramos un borde conflictivo, el ciclo impar queda en la parte superior de la pila de recursión. Por lo tanto, para recuperarlo, necesitamos cortar en la pila de recursión todo hasta la primera aparición del último vértice.
Implementaremos la búsqueda en profundidad manteniendo un arreglo asociativo de números de parte para cada vértice. La pila de recursión se mantendrá automáticamente a través de la implementación de la clase Functor de la monada que elegimos: solo tenemos que agregar todos los vértices del camino al resultado retornado de la función recursiva.
Mi primera idea fue usar la monada Either, que parece implementar precisamente los efectos que necesitamos. La primera implementación que escribí estaba muy cercana a esta opción. De hecho, tuve cinco implementaciones diferentes en algún momento, y finalmente me detuve en otra.
En primer lugar, debemos mantener un arreglo asociativo de identificadores de partes; esto tiene que ver con el State. En segundo lugar, necesitamos poder detenernos en caso de detectar un conflicto. Esto puede ser o una Monad para Either, o MonadPlus para Maybe. La principal diferencia es que Either puede retornar un valor en caso de que el cálculo no se haya detenido, mientras que Maybe solo retorna información al respecto. Dado que no necesitamos un valor separado en caso de éxito (ya está almacenado en el State), elegimos Maybe. Y en el momento en que necesitamos combinar los efectos de dos monadas, surgen , que combinan precisamente estos efectos.
¿Por qué elegí un tipo tan complejo? Dos razones. Primero, la implementación se asemeja mucho a la imperativa. En segundo lugar, necesitamos manipular el valor devuelto en caso de conflicto, al retroceder de la recursión para restaurar un ciclo impar, y esto 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 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)
El bloque where es el núcleo del algoritmo. Trataré de explicar lo que sucede dentro de él.
- inVertex es la parte de la búsqueda en profundidad donde visitamos un vértice por primera vez. Aquí asignamos a ese vértice un número de parte y lanzamos onEdge para todos sus vecinos. También es el lugar donde restauramos la pila de llamadas: si msum devuelve un valor, asignamos el vértice v allí.
- onEdge es la parte donde visitamos el borde. Se llama dos veces para cada borde. Aquí comprobamos si se ha visitado el vértice desde el otro lado y lo visitamos si no es así. Si ya ha sido visitado, verificamos si el borde es conflictivo. Si lo es, devolvemos el valor: la parte superior de la pila de recursión, a la que luego se añadirán todos los demás vértices al regresar.
- processVertex verifica si cada vértice ha sido visitado y lo ejecuta inVertex si no lo ha sido.
- dfs ejecuta processVertex en todos los vértices.
Eso es todo.
Historia de la palabra INLINE
La palabra INLINE no estaba en la primera implementación del algoritmo, apareció más tarde. Cuando intenté encontrar una mejor implementación, descubrí que en algunos gráficos la versión sin INLINE funcionaba notablemente más lento. Teniendo en cuenta que semánticamente las funciones deberían funcionar igual, esto me sorprendió mucho. Aún más extraño es que en otra máquina con otra versión de GHC no había diferencia notable.
Después de pasar una semana leyendo la salida de GHC Core, pude solucionar el problema con una línea con INLINE explícito. En algún momento entre GHC 8.4.4 y GHC 8.6.5, el optimizador dejó de hacerlo por sí mismo.
No esperaba encontrar tanta suciedad en la programación en Haskell. Sin embargo, los optimizadores, incluso en nuestros días, a veces cometen errores, y darles pistas es nuestra tarea. Por ejemplo, aquí sabemos que la función debe ser inlinada, ya que está inlinada en la versión imperativa, y esto es un motivo para darle una pista al compilador.
¿Qué pasó después?
Después implementé el algoritmo de Hopcroft-Karp con otras mónadas, y ahí terminó el programa.
Gracias a Google Summer of Code, adquirí experiencia práctica en programación funcional, que no solo me ayudó a pasar a una pasantía en Jane Street el siguiente verano (no estoy seguro de cuán conocido es ese lugar incluso entre el público conocedor de Habr, pero es uno de los pocos donde se puede hacer programación funcional en verano), sino que también me presentó un sorprendente mundo de aplicaciones de esta paradigma en la práctica, que es muy diferente de mi experiencia en lenguajes tradicionales.
Fuente: habr.com
