L'été dernier, j'ai participé à un programme pour les étudiants proposé par Google. Chaque année, les organisateurs sélectionnent plusieurs projets Open Source, y compris ceux de grandes organisations comme et . Pour travailler sur ces projets, Google invite des étudiants du monde entier.
En tant que participant au Google Summer of Code 2019, j'ai réalisé un projet dans le cadre de la bibliothèque avec l'organisation , qui se consacre au développement du langage Haskell, l'un des langages de programmation fonctionnels les plus connus. Alga est une bibliothèque qui propose pour les graphes en Haskell. Elle est utilisée, par exemple, dans — une bibliothèque de GitHub qui construit des arbres sémantiques, des graphes d'appels et de dépendances à partir du code et qui peut les comparer. Mon projet consistait à ajouter une représentation sûre de types pour les graphes bipartis et des algorithmes pour cette représentation.
Dans ce post, je vais parler de ma mise en œuvre de l'algorithme de vérification de bipartition des graphes en Haskell. Bien que cet algorithme soit l'un des plus basiques, sa mise en œuvre élégante en style fonctionnel m'a demandé plusieurs itérations et beaucoup de travail. Au final, je me suis arrêté sur une implémentation utilisant des monades transformantes.
À propos de moi
Je m'appelle Vassili Alfiorov, je suis étudiant en quatrième année à l'Université de Saint-Pétersbourg. J'ai précédemment écrit sur mon blog et . En ce moment, je fais un stage à en Norvège, où je travaille sur des approches pour la tâche de . Mes domaines d'intérêt incluent les algorithmes paramétrés et la programmation fonctionnelle.
Sur la mise en œuvre de l'algorithme
Préface
Il est fortement recommandé aux étudiants participant au programme de tenir un blog. Pour mon blog, j'ai eu un espace sur . Cet article est une traduction , que j'ai écrite là-bas en juillet en anglais, avec une petite introduction.
Le Pull Request avec le code dont il s'agit peut être trouvé .
On peut lire sur les résultats de mon travail (en anglais) .
Ce post suppose que le lecteur est familier avec les concepts de base de la programmation fonctionnelle, bien que j'essaierai de rappeler tous les termes utilisés au moment opportun.
Vérification des graphes pour la bipartition
L'algorithme de vérification d'un graphe pour la bipartition est généralement présenté dans le cours des algorithmes comme l'un des algorithmes graphiques les plus simples. Son idée est directe : d'abord, nous plaçons d'une manière ou d'une autre les sommets dans la partie gauche ou droite, et lors de la détection d'une arête conflictuelle, nous affirmons que le graphe n'est pas biparti.
Un peu plus en détail : d'abord, nous plaçons un sommet quelconque dans la partie gauche. Il est évident que tous les voisins de ce sommet doivent se trouver dans la partie droite. Ensuite, tous les voisins des voisins de ce sommet doivent se trouver dans la partie gauche, et ainsi de suite. Nous continuons à attribuer des parties aux sommets tant qu'il y a des sommets dans le composant connexe à partir duquel nous avons commencé, auxquels nous n'avons pas encore attribué de voisins. Ensuite, nous répétons cette action pour tous les composants connexes.
S'il existe une arête entre des sommets appartenant à la même partie, il n'est pas difficile de trouver un cycle impair dans le graphe, ce qui est largement connu (et assez évident) comme étant impossible dans un graphe biparti. Sinon, nous avons une partition correcte en parties, ce qui signifie que le graphe est biparti.
En règle générale, cet algorithme est implémenté à l'aide de ou . Dans les langages impératifs, on utilise généralement la recherche en profondeur, qui est légèrement plus simple et ne nécessite pas de structures de données supplémentaires. J'ai également choisi la recherche en profondeur comme étant plus traditionnelle.
Ainsi, nous avons abouti au schéma suivant. Nous parcourons les sommets du graphe en utilisant la recherche en profondeur et leur attribuons des parties, changeant le numéro de la partie lors du passage par une arête. Si nous essayons d'attribuer une partie à un sommet auquel une partie a déjà été attribuée, nous pouvons affirmer sans aucun doute que le graphe n'est pas biparti. Au moment où toutes les sommets ont reçu une partie et que nous avons examiné toutes les arêtes, nous avons une bonne partition.
La pureté des calculs
Dans Haskell, nous supposons que tous les calculs sont purs. Cependant, si c'était réellement le cas, nous ne pourrions pas imprimer quoi que ce soit à l'écran. En fait, les calculs purs sont si paresseux qu'il n'existe aucune raison pure de faire des calculs. Tous les calculs se déroulant dans le programme sont, d'une manière ou d'une autre, forcés dans la monade "impure" IO.
Les monades sont un moyen de représenter des calculs avec des effets. en Haskell. L'explication de leur fonctionnement dépasse le cadre de cet article. Vous pouvez lire une bonne description claire en anglais. .
Ici, je tiens à souligner que, tandis que certaines monades, comme IO, sont mises en œuvre par la magie du compilateur, presque toutes les autres sont implémentées de manière programmatique et tous les calculs qui y sont effectués sont purs.
Il existe de nombreux effets, chacun ayant sa propre monade. C'est une théorie très puissante et magnifique : toutes les monades implémentent la même interface. Nous allons parler des trois monades suivantes :
- Either e a — un calcul qui renvoie une valeur de type a ou lance une exception de type e. Le comportement de cette monade ressemble beaucoup à la gestion des exceptions dans les langages impératifs : les erreurs peuvent être capturées ou propagées. La principale différence est que la monade est entièrement réalisée logiquement dans la bibliothèque standard écrite dans le même Haskell, alors que dans les langages impératifs, on utilise généralement les mécanismes du système d'exploitation.
- State s a — un calcul qui renvoie une valeur de type a et a accès à un état mutable de type s.
- Maybe a. La monade Maybe exprime un calcul qui peut être interrompu à tout moment par le retour de Nothing. Cependant, nous allons discuter de l'implémentation de la classe MonadPlus pour le type Maybe, qui exprime l'effet opposé : c'est un calcul qui peut être interrompu à tout moment par le retour d'une valeur spécifique.
Implémentation de l'algorithme
Nous avons deux types de données, Graph a et Bigraph a b, où le premier représente des graphes avec des sommets étiquetés de valeurs de type a, et le second représente des graphes bipartis avec des sommets de la partie gauche étiquetés de valeurs de type a et des sommets de la partie droite étiquetés de valeurs de type b.
Ce ne sont pas des types de la bibliothèque Alga. Alga n'a pas de représentation pour les graphes bipartis non orientés. J'ai fait ces types de cette manière pour plus de clarté.
Nous aurons également besoin de fonctions auxiliaires avec les signatures suivantes :
-- Liste des voisins de ce sommet.
neighbours :: Ord a => a -> Graph a -> [a]
-- Construire un graphe bipartite à partir d'un graphe et d'une fonction, pour chaque sommet
-- retournant sa part et une étiquette dans la nouvelle part, en ignorant les arêtes conflictuelles.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Liste des sommets dans le graphe
vertexList :: Ord a => Graph a -> [a]
La signature de la fonction que nous allons écrire ressemble à ceci :
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)Il est facile de voir que si, lors de la recherche en profondeur, nous avons trouvé une arête conflictuelle, le cycle impair se trouve en haut de la pile de récursion. Ainsi, pour le reconstruire, nous devons couper la pile de récursion jusqu'à la première occurrence du dernier sommet.
Nous allons implémenter une recherche en profondeur, en maintenant un tableau associatif des numéros de part pour chaque sommet. La pile de récursion sera automatiquement maintenue grâce à l'implémentation de la classe Functor de la monade choisie : il suffira juste de placer tous les sommets du chemin dans le résultat retourné par la fonction récursive.
Ma première idée était d'utiliser la monade Either, qui semble implémenter exactement les effets dont nous avons besoin. La première version que j'ai écrite était très proche de cette option. En fait, j'avais cinq réalisations différentes à un moment donné, et j'ai finalement opté pour une autre.
Tout d'abord, nous devons maintenir un tableau associatif des identifiants de part - c'est quelque chose lié à State. Deuxièmement, nous devons savoir nous arrêter en cas de détection d'un conflit. Cela peut être soit Monad pour Either, soit MonadPlus pour Maybe. La principale différence est que Either peut retourner une valeur si le calcul n'a pas été arrêté, alors que Maybe retourne seulement une information à ce sujet. Étant donné que nous n'avons pas besoin d'une valeur distincte en cas de succès (elle est déjà stockée dans State), nous choisissons Maybe. Et au moment où nous devons combiner les effets des deux monades, surgissent , qui combinent justement ces effets.
Pourquoi ai-je choisi un type aussi complexe ? Deux raisons. Tout d'abord, l'implémentation se rapproche beaucoup de l'approche impérative. Deuxièmement, nous devons manipuler la valeur renvoyée en cas de conflit lors du retour de la récursion pour restaurer un cycle impair, ce qui est beaucoup plus simple à faire avec la monade Maybe.
Ainsi, nous obtenons une telle implémentation.
{-# 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)
Le bloc where est le cœur de l'algorithme. Je vais essayer d'expliquer ce qui se passe à l'intérieur.
- inVertex est la partie de la recherche en profondeur où nous visitons le sommet pour la première fois. Ici, nous attribuons un numéro de part au sommet et lançons onEdge pour tous les voisins. C'est également l'endroit où nous restaurons la pile d'appels : si msum renvoie une valeur, nous y ajoutons le sommet v.
- onEdge — c'est la partie où nous visitons une arête. Elle est appelée deux fois pour chaque arête. Ici, nous vérifions si le sommet de l'autre côté a été visité, et nous le visitons s'il ne l'est pas. S'il est visité, nous vérifions si l'arête est conflictuelle. Si c'est le cas, nous retournons la valeur — le sommet le plus haut de la pile de récursivité, où toutes les autres sommets seront empilés lors du retour.
- processVertex vérifie pour chaque sommet s'il a été visité, et exécute inVertex dessus s'il ne l'est pas.
- dfs exécute processVertex sur tous les sommets.
C'est tout.
Histoire du mot INLINE
Le mot INLINE n'était pas présent dans la première implémentation de l'algorithme, il est apparu plus tard. Lorsque j'essayais de trouver la meilleure implémentation, j'ai découvert que sur certains graphes, la version sans INLINE fonctionnait nettement plus lentement. Étant donné que sémantiquement les fonctions devraient fonctionner de la même manière, cela m'a beaucoup surpris. Encore plus étrange, sur une autre machine avec une autre version de GHC, il n'y avait aucune différence notable.
Après avoir passé une semaine à lire la sortie de GHC Core, j'ai pu résoudre le problème par une seule ligne avec INLINE explicite. À un moment donné entre GHC 8.4.4 et GHC 8.6.5, l'optimiseur a cessé de le faire automatiquement.
Je ne m'attendais pas à rencontrer autant de désordre en programmant en Haskell. Cependant, les optimiseurs commettent encore parfois des erreurs même à notre époque et il est de notre responsabilité de leur donner des indices. Par exemple, ici nous savons que la fonction doit être inlinée, car elle est inlinée dans la version impérative, et c'est une raison de donner un indice au compilateur.
Que s'est-il passé ensuite ?
Ensuite, j'ai implémenté l'algorithme de Hopcroft-Karp avec d'autres monades, et sur cela le programme a pris fin.
Grâce à Google Summer of Code, j'ai acquis une expérience pratique en programmation fonctionnelle, qui m'a non seulement aidé à obtenir un stage chez Jane Street l'été suivant (je ne suis pas sûr de la renommée de cet endroit même parmi le public averti de Habr, mais c'est l'un des rares endroits où l'on peut faire de la programmation fonctionnelle l'été), mais m'a également introduit dans un monde étonnant d'applications pratiques de ce paradigme, très différent de mon expérience avec les langages traditionnels.
Source : habr.com
