Pourquoi la programmation fonctionnelle n'a-t-elle pas recherché les arbres dynamiques?

19

Les arbres dynamiques jouent un rôle important dans la résolution de problèmes tels que les flux de réseau, les graphiques dynamiques, les problèmes combinatoires ("Dynamic Trees in Practice" par Tarjan et Werneck) et la fusion récente de dictionnaires ("A Simple Mergeable Dictionary" par Adam Karczmarz),

Par arbres dynamiques, je me réfère à la définition énoncée dans l'article de Sleator & Tarjan "Une structure de données pour les arbres dynamiques" en 1983. Peu d'efforts ont été publiés dans le domaine de la recherche en programmation fonctionnelle depuis.

  1. Edward Kmett a implémenté une version des arbres ST principalement comme une traduction de l'homologue C ++, voir Arbres coupés de liens .
  2. Chris Okasaki a écrit une implémentation limitée des arbres Splay dans son célèbre livre "Structures de données purement fonctionnelles".
  3. Ralf Hinze et Ross Paterson ont introduit une structure de données fonctionnelle appelée 2-3 arbres à doigts mais avec un objectif quelque peu différent de celui de la définition originale des arbres dynamiques.

La mise en œuvre (et peut-être les performances) des arbres dynamiques est divisée selon trois approches:

  1. Linéarisation, où les arbres ET (tour Euler) jouent un grand rôle. Pas trouvé une étude purement fonctionnelle.
  2. La décomposition de chemin, où les arbres ST sont le produit phare, vient de trouver la version de Kmett.
  3. La contraction des arbres, où les arbres supérieurs, les arbres de topologie et les arbres RC sont les joueurs. Pas trouvé une étude purement fonctionnelle.

L'analyse et l'implémentation purement fonctionnelles peuvent être trouvées sur Splay, AVL, arbre rouge-noir, mais ce ne sont PAS des arbres dynamiques. Les premiers sont considérés comme la structure de données fantôme (également appelée virtuelle ou auxiliaire) des seconds.

Donc, ma question est:

Quelles sont les raisons (inconvénients, faiblesses) pour la communauté de recherche Programmation fonctionnelle de ne pas participer à la structure de données des arbres dynamiques?

data-structures trees functional-programming Richard Chambers
la source
14
Je ne comprends pas comment on peut y répondre sans former un comité communautaire de programmation fonctionnelle faisant autorité pour formuler des avis officiels. Ne pouvons-nous pas reformuler la question afin qu'il y ait quelque chose à laquelle on puisse répondre ici? Pour autant que je sache, le PO devrait simplement aller implémenter ses arbres dynamiques à Haskell ou autre chose, puis revenir ici pour signaler que cela a été fait après tout.
Andrej Bauer
Mise à jour de @AndrejBauer: l'OP est parti et a implémenté ses arbres dynamiques dans Haskell: arxiv.org/abs/1908.11105
jbapple

Réponses:

-1

"En informatique, la programmation fonctionnelle est un paradigme de programmation. Un style de construction de la structure et des éléments des programmes informatiques qui traite le calcul comme l'évaluation des fonctions mathématiques et évite de changer l'état et les données mutables." - Wikipédia

"changement d'état et données mutables" en d'autres termes "dynamique".

Votre question revient donc un peu à demander pourquoi la gauche n'est pas la bonne.

Anthony Bachler
la source
1
Les programmes fonctionnels peuvent représenter des données dynamiques avec des structures de données persistantes. Cette question demande pourquoi le développement de structures de données persistantes pour un certain problème n'a pas été étudié. La question a du sens.
Rétablir Monica le