Comment puis-je implémenter des graphes et des algorithmes graphiques dans un langage de programmation fonctionnel?

Fondamentalement, je sais créer des structures de données graphiques et utiliser l’algorithme de Dijkstra dans des langages de programmation où les effets secondaires sont autorisés. Généralement, les algorithmes graphiques utilisent une structure pour marquer certains nœuds comme étant «visités», mais cela a des effets secondaires, que j’essaie d’éviter.

Je peux imaginer un moyen de mettre en œuvre cela dans un langage fonctionnel, mais cela nécessite essentiellement de transférer de grandes quantités d’état à différentes fonctions, et je me demande s’il existe une solution plus efficace.

Vous pouvez vérifier comment la bibliothèque de graphes fonctionnels Haskell de Martin Erwig fait les choses. Par exemple, ses fonctions de plus court chemin sont toutes pures et vous pouvez voir le code source de la manière dont il a été implémenté.

Une autre option, comme celle mentionnée ci-dessus , est d’utiliser une abstraction qui vous permet d’implémenter des fonctions pures en termes d’état. Il mentionne la monade State (disponible à la fois dans les variétés paresseuses et ssortingctes ). Une autre option, si vous travaillez dans le compilateur / interpréteur Haskell de GHC (ou, je pense, dans toute implémentation Haskell prenant en charge les types rank-2), une autre option est le monade ST , qui vous permet d’écrire des fonctions pures variables internes.

Si vous utilisiez le haskell, le seul langage fonctionnel avec lequel je suis familier, je vous recommande d’utiliser la monade d’état . La monade d’état est une abstraction pour une fonction qui prend un état et renvoie une valeur intermédiaire et une nouvelle valeur d’état. Ceci est considéré comme un haskell idiomatique dans les situations où il est nécessaire de maintenir un état élevé.

C’est une alternative bien meilleure à l’état de retour “naïf comme résultat de fonction et passe-le en tant que paramètre” qui est souligné dans les didacticiels de functional programming pour débutants. J’imagine que la plupart des langages de programmation fonctionnels ont une construction similaire.

Je garde juste l’ensemble visité et le passe en paramètre. Il existe des implémentations log-temps efficaces d’ensembles de tout type ordonné et d’ensembles d’entiers extrêmement efficaces.

Pour représenter un graphique, j’utilise des listes de contiguïté ou j’utiliserai une carte finie qui mappe chaque nœud à une liste de ses successeurs. Cela dépend de ce que je veux faire.

Plutôt qu’Abelson et Sussman, je recommande les structures de données purement fonctionnelles de Chris Okasaki. Je suis lié à la thèse de Chris, mais si vous avez l’argent, il l’a étendu à un excellent livre .


Juste pour les sourires, voici une recherche légèrement effrayante en profondeur post-ordre de profondeur effectuée en Haskell. Ceci est tout droit sorti de la bibliothèque d’optimisation Hoopl :

postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e) => LabelMap (block CC) -> e -> LabelSet -> [block CC] postorder_dfs_from_except blocks b visited = vchildren (get_children b) (\acc _visited -> acc) [] visited where vnode :: block CC -> ([block CC] -> LabelSet -> a) -> ([block CC] -> LabelSet -> a) vnode block cont acc visited = if setMember id visited then cont acc visited else let cont' acc visited = cont (block:acc) visited in vchildren (get_children block) cont' acc (setInsert id visited) where id = entryLabel block vchildren bs cont acc visited = next bs acc visited where next children acc visited = case children of [] -> cont acc visited (b:bs) -> vnode b (next bs) acc visited get_children block = foldr add_id [] $ targetLabels bloc add_id id rst = case lookupFact id blocks of Just b -> b : rst Nothing -> rst 

J’aimerais beaucoup entendre parler d’une technique vraiment intelligente, mais je pense qu’il y a deux approches fondamentales:

  1. Modifier un object d’état global. c.-à-d. effets secondaires
  2. Transmettez le graphique en argument à vos fonctions, la valeur de retour étant le graphique modifié. Je suppose que c’est votre approche de “faire circuler de grandes quantités d’état”

C’est ce qui se fait dans la functional programming. Si le compilateur / interpréteur est utile, il vous aidera à gérer la mémoire. En particulier, vous devez vous assurer que vous utilisez la récursion de la queue, si vous vous trouvez dans l’une de vos fonctions.

Voici un exemple Swift. Vous pourriez trouver cela un peu plus lisible. Les variables sont en fait nommées de manière descriptive, contrairement aux exemples Haskell super cryptiques.

https://github.com/gistya/Functional-Swift-Graph

La plupart des langages fonctionnels prennent en charge les fonctions internes. Vous pouvez donc simplement créer votre représentation graphique dans la couche la plus externe et la référencer à partir de la fonction interne.

Ce livre le couvre très largement -1 & pf_rd_t = 201 & pf_rd_i = 0262011530 & pf_rd_m = ATVPDKIKX0DER & pf_rd_r = 114DJE8K5BG75B86E1QS