Voici une explication possible.
Petit résumé rapide, un graphe c'est soit :
Un graphe vide
Un nœud v et les arêtes de v vers un graphe
Cette définition est bien inductive et représentable avec des types récursifs. Elle possède certains avantages : on peut faire des inductions structurelles dessus. Par exemple, faire un parcours en largeur/profondeur ne nécessite plus de marquer des nœuds. Extraire des sous-graphes est naturel, on peut insérer des nœuds en O(1). Après, il est vrai que le parcours sans destruction est assez peu efficace ... Avec un peu d'effort on peut la rendre moins inefficace qu'elle n'en a l'air.
[^] # Re: Map-Reduce
Posté par Aluminium95 . En réponse au journal Données vs Code. Évalué à 3.
Voici une explication possible.
Petit résumé rapide, un graphe c'est soit :
vet les arêtes devvers un grapheCette définition est bien inductive et représentable avec des types récursifs. Elle possède certains avantages : on peut faire des inductions structurelles dessus. Par exemple, faire un parcours en largeur/profondeur ne nécessite plus de marquer des nœuds. Extraire des sous-graphes est naturel, on peut insérer des nœuds en O(1). Après, il est vrai que le parcours sans destruction est assez peu efficace ... Avec un peu d'effort on peut la rendre moins inefficace qu'elle n'en a l'air.