L'été dernier, j'ai participé à - un programme pour les étudiants de Google. Chaque année, les organisateurs sélectionnent plusieurs projets Open Source, notamment issus d'organisations aussi connues que и . Google invite des étudiants du monde entier à travailler sur ces projets.
En tant que participant au Google Summer of Code 2019, j'ai réalisé un projet au sein de la bibliothèque avec l'organisation , qui développe le langage Haskell, l'un des langages de programmation fonctionnels les plus connus. Alga est une bibliothèque qui représente représentation des graphiques en Haskell. Il est utilisé par exemple dans — une bibliothèque Github qui construit des arbres sémantiques, des graphiques d'appels et de dépendances basés sur le code et peut les comparer. Mon projet consistait à ajouter une représentation de type sécurisé pour les graphiques bipartis et des algorithmes pour cette représentation.
Dans cet article, je parlerai de mon implémentation d'un algorithme pour vérifier la bipartité d'un graphe dans Haskell. Même si l’algorithme est l’un des plus basiques, son implémentation magnifique dans un style fonctionnel m’a pris plusieurs itérations et a demandé beaucoup de travail. En conséquence, j'ai opté pour une implémentation avec des transformateurs monades.
À propos de moi
Je m'appelle Vasily Alferov, je suis étudiant en quatrième année au HSE de Saint-Pétersbourg. Plus tôt dans le blog que j'ai écrit и . En ce moment, je suis en stage chez en Norvège, où je travaille sur des approches du problème . Mes intérêts incluent les algorithmes paramétrés et la programmation fonctionnelle.
À propos de la mise en œuvre de l'algorithme
Avant-propos
Les étudiants participant au programme sont fortement encouragés à bloguer. Ils m'ont fourni une plateforme pour le blog . Cet article est une traduction , écrit par moi là-bas en juillet en anglais, avec une courte préface.
La Pull Request avec le code en question peut être trouvée .
Vous pouvez lire les résultats de mon travail (en anglais) .
Cet article a pour but de familiariser le lecteur avec les concepts de base de la programmation fonctionnelle, même si j'essaierai de rappeler tous les termes utilisés le moment venu.
Vérification de la bipartité des graphiques
Un algorithme permettant de vérifier la bipartité d'un graphe est généralement présenté dans un cours sur les algorithmes comme l'un des algorithmes de graphe les plus simples. Son idée est simple : d'abord, nous plaçons d'une manière ou d'une autre les sommets dans la part gauche ou droite, et lorsqu'une arête conflictuelle est trouvée, nous affirmons que le graphe n'est pas biparti.
Un peu plus de détails : nous mettons d'abord un sommet dans le partage de gauche. Évidemment, tous les voisins de ce sommet doivent se trouver dans le lobe droit. De plus, tous les voisins des voisins de ce sommet doivent se trouver dans le lobe gauche, et ainsi de suite. Nous continuons à attribuer des parts aux sommets tant qu'il y a encore des sommets dans la composante connexe du sommet avec lequel nous avons commencé et auxquels nous n'avons pas attribué de voisins. Nous répétons ensuite cette action pour tous les composants connectés.
S'il existe une arête entre les sommets qui appartiennent à la même partition, il n'est pas difficile de trouver un cycle impair dans le graphe, ce qui est bien connu (et bien évidemment) impossible dans un graphe biparti. Sinon, nous avons une partition correcte, ce qui signifie que le graphe est biparti.
Généralement, cet algorithme est implémenté en utilisant ou . Dans les langages impératifs, la recherche en profondeur est généralement utilisée car elle 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 car elle est plus traditionnelle.
Ainsi, nous sommes arrivés au schéma suivant. Nous parcourons les sommets du graphique en utilisant la recherche en profondeur d'abord et leur attribuons des parts, en modifiant le numéro de la part à mesure que nous nous déplaçons le long du bord. Si nous essayons d’attribuer une part à un sommet auquel une part est déjà attribuée, nous pouvons affirmer sans risque que le graphe n’est pas biparti. Au moment où tous les sommets se voient attribuer un partage et que nous avons examiné toutes les arêtes, nous avons une bonne partition.
Pureté des calculs
En Haskell, nous supposons que tous les calculs sont faire le ménage. Cependant, si tel était réellement le cas, nous n’aurions aucun moyen d’imprimer quoi que ce soit à l’écran. Du tout, nettoyer les calculs sont tellement paresseux qu'il n'y en a pas un propre raisons de calculer quelque chose. Tous les calculs effectués dans le programme sont forcés d'une manière ou d'une autre "impur" monade IO.
Les monades sont un moyen de représenter des calculs avec effets à Haskell. Expliquer comment ils fonctionnent dépasse le cadre de cet article. Une description bonne et claire peut être lue en anglais .
Ici, je tiens à souligner que si certaines monades, telles que IO, sont implémentées grâce à la magie du compilateur, presque toutes les autres sont implémentées dans un logiciel et tous les calculs qu'elles contiennent sont purs.
Il y a beaucoup d'effets et chacun a sa propre monade. C’est une théorie très forte et très belle : toutes les monades implémentent la même interface. Nous parlerons des trois monades suivantes :
- Soit ea est un calcul qui renvoie une valeur de type a, soit lève une exception de type e. Le comportement de cette monade est très similaire à la gestion des exceptions dans les langages impératifs : les erreurs peuvent être détectées ou transmises. La principale différence est que la monade est implémentée de manière tout à fait logique dans la bibliothèque standard de Haskell, tandis que les langages impératifs utilisent généralement les mécanismes du système d'exploitation.
- L'état sa est un calcul qui renvoie une valeur de type a et a accès à un état mutable de type s.
- Peut-être un. La monade Maybe exprime un calcul qui peut être interrompu à tout moment en renvoyant Nothing. Cependant, nous parlerons de l'implémentation de la classe MonadPlus pour le type Maybe, qui exprime l'effet inverse : c'est un calcul qui peut être interrompu à tout moment en renvoyant une valeur spécifique.
Implémentation de l'algorithme
Nous avons deux types de données, Graph a et Bigraph ab, dont le premier représente des graphiques avec des sommets étiquetés avec des valeurs de type a, et le second représente des graphes bipartis avec des sommets de gauche étiquetés avec des valeurs de type a et droit. -sommets latéraux étiquetés avec des 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 les types comme celui-ci pour plus de clarté.
Nous aurons également besoin de fonctions d'assistance avec les signatures suivantes :
-- Список соседей данной вершины.
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)Il est facile de voir que si, au cours de la recherche en profondeur, nous trouvons une arête conflictuelle, le cycle impair se situe au sommet de la pile de récursion. Ainsi, pour le restaurer, il faut tout couper depuis la pile de récursion jusqu'à la première occurrence du dernier sommet.
Nous implémentons une recherche en profondeur en maintenant un tableau associatif de numéros de partage pour chaque sommet. La pile de récursion sera automatiquement maintenue grâce à l'implémentation de la classe Functor de la monade que nous avons choisie : il nous suffira de mettre tous les sommets du chemin dans le résultat renvoyé par la fonction récursive.
Ma première idée a été d'utiliser la monade Soit, qui semble implémenter exactement les effets dont nous avons besoin. La première implémentation que j'ai écrite était très proche de cette option. En fait, j’ai eu cinq implémentations différentes à un moment donné et j’ai finalement opté pour une autre.
Premièrement, nous devons maintenir un tableau associatif d’identifiants de partage – c’est une question d’État. Deuxièmement, nous devons pouvoir nous arrêter lorsqu’un conflit est détecté. Il peut s'agir de Monad pour l'un ou l'autre ou de MonadPlus pour Maybe. La principale différence est que l'un ou l'autre peut renvoyer une valeur si le calcul n'a pas été arrêté, et l'autre peut renvoyer uniquement des informations à ce sujet dans ce cas. Puisque nous n'avons pas besoin d'une valeur distincte pour réussir (elle est déjà stockée dans State), nous choisissons Peut-être. Et au moment où il faut combiner les effets de deux monades, elles sortent , qui combinent précisément ces effets.
Pourquoi ai-je choisi un type aussi complexe ? Deux raisons. Premièrement, la mise en œuvre s’avère très similaire à l’impératif. Deuxièmement, nous devons manipuler la valeur de retour en cas de conflit lors du retour de la récursion pour restaurer la boucle impaire, ce qui est beaucoup plus facile à faire dans la monade Maybe.
Nous obtenons ainsi cette 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 <- 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)
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 partage au sommet et exécutons onEdge sur tous les voisins. C'est également là que nous restaurons la pile d'appels : si msum renvoie une valeur, nous y plaçons le sommet v.
- onEdge est la partie où nous visitons le bord. Il est appelé deux fois pour chaque arête. Ici, nous vérifions si le sommet de l'autre côté a été visité, et le visitons sinon. En cas de visite, nous vérifions si le bord est en conflit. Si tel est le cas, nous renvoyons la valeur - tout en haut de la pile de récursion, où tous les autres sommets seront ensuite placés au retour.
- processVertex vérifie pour chaque sommet s'il a été visité et s'exécute inVertex dessus sinon.
- dfs exécute processVertex sur tous les sommets.
Voilà tout.
Histoire du mot INLINE
Le mot INLINE ne figurait pas dans la première implémentation de l'algorithme ; il est apparu plus tard. Lorsque j'ai essayé de trouver une meilleure implémentation, j'ai constaté que la version non-INLINE était sensiblement plus lente sur certains graphiques. Considérant 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 version différente 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 avec une ligne d'INLINE explicite. À un moment donné entre GHC 8.4.4 et GHC 8.6.5, l'optimiseur a cessé de le faire de lui-même.
Je ne m'attendais pas à rencontrer une telle saleté dans la programmation Haskell. Cependant, même aujourd’hui, les optimiseurs font parfois des erreurs, et c’est notre rôle de leur donner des indices. Par exemple, nous savons ici que la fonction doit être inline car elle est inline dans la version impérative, et c'est une raison pour donner un indice au compilateur.
Qu'est-ce qui s'est passé ensuite?
Ensuite, j'ai implémenté l'algorithme Hopcroft-Karp avec d'autres monades, et ce fut la fin du programme.
Grâce au Google Summer of Code, j'ai acquis une expérience pratique en programmation fonctionnelle, ce qui m'a non seulement aidé à obtenir un stage chez Jane Street l'été suivant (je ne suis pas sûr de la notoriété de cet endroit, même parmi le public averti de Habr, mais c'est un des rares où vous pouvez passer l'été à vous lancer dans la programmation fonctionnelle), mais m'a également fait découvrir le monde merveilleux de l'application pratique de ce paradigme, très différent de mon expérience dans les langages traditionnels.
Source: habr.com