Solution de contournement pour la mise en œuvre d'opérations sur des structures de données doublement liées ou circulaires dans des langues avec des données immuables

11

Je voudrais apprendre à créer des graphiques et à effectuer des opérations locales sur eux dans Haskell, mais la question n'est pas spécifique à Haskell, et au lieu de graphiques, nous pouvons envisager des listes doublement liées.

Question: Quelle serait une manière idiomatique ou recommandée d'implémenter une liste doublement liée (ou une autre structure de données doublement liée ou circulaire) et des opérations sur celle-ci dans un langage qui soutient et préconise principalement des structures de données immuables (Haskell, Clojure, etc.) ? En particulier, comment utiliser les mises à jour sur place, qui sont formellement interdites par la langue?

Je peux facilement imaginer que si une opération locale est effectuée sur une liste doublement liée (si un élément est inséré, par exemple), il peut ne pas être nécessaire de copier la liste entière immédiatement en raison de la paresse de la langue. Cependant, étant donné que la liste est doublement liée, si elle est modifiée à un endroit, aucun des anciens nœuds ne peut être utilisé dans la nouvelle version de la liste, et ils devraient être marqués, copiés, récupérés tôt ou tard. . Évidemment, ce sont des opérations redondantes si seule la copie mise à jour de la liste doit être utilisée, mais elles ajouteraient une "surcharge" proportionnelle à la taille de la liste.

Cela signifie-t-il que pour de telles tâches, les données immuables sont tout simplement inappropriées et que les langages déclaratifs fonctionnels sans prise en charge "native" des données mutables ne sont pas aussi bons que les langages impératifs? Ou, y a-t-il une solution de contournement délicate?

PS J'ai trouvé quelques articles et présentations sur ce sujet sur Internet mais j'ai eu du mal à les suivre, alors que je pense que la réponse à cette question ne devrait pas prendre plus d'un paragraphe et peut-être un schéma ... Je veux dire, s'il y a pas de solution "fonctionnelle" à ce problème, la réponse est probablement "utiliser C". S'il y en a un, dans quelle mesure cela peut-il être compliqué?


Questions connexes


Citations pertinentes

Les langages de programmation purement fonctionnels permettent à de nombreux algorithmes d'être exprimés de manière très concise, mais il existe quelques algorithmes dans lesquels l'état de mise à jour sur place semble jouer un rôle crucial. Pour ces algorithmes, les langages purement fonctionnels, qui n'ont pas d'état pouvant être mis à jour, semblent intrinsèquement inefficaces ( [Ponder, McGeer et Ng, 1988] ).

- John Launchbury et Simon Peyton Jones, Lazy Functional State Threads (1994), ainsi que John Launchbury et Simon Peyton Jones, State in Haskell (1995). Ces articles présentent le STconstructeur de type monadique à Haskell.

Alexey
la source
4
Recommandé: Okasaki
Robert Harvey
2
Merci pour la référence. J'ai trouvé sa thèse .
Alexey
Cet article semble prometteur: algorithmes de recherche en profondeur paresseux et de graphes linéaires dans Haskell (1994), par David King et John Launchbury.
Alexey
Il semble qu'un problème similaire avec les tableaux soit résolu par le package diffarray qui implémente le DiffArraytype. En regardant la source du paquet diffarray , je vois 91 occurrences de unsafePerformIO. Il semble que la réponse à ma question soit "oui, non, les langages purement fonctionnels avec des données immuables ne sont pas appropriés pour implémenter des algorithmes qui reposent normalement sur des mises à jour sur place".
Alexey
Ma solution actuelle (en Haskell) est d'utiliser un dictionnaire ( Map, IntMapou HashMap) en tant que stockage et de faire des nœuds contiennent des ID des noeuds liés. "Tous les problèmes en informatique peuvent être résolus par un autre niveau d'indirection."
Alexey

Réponses:

6

Il pourrait y avoir d'autres structures de données immuables efficaces qui correspondent à votre tâche particulière, mais ne sont pas aussi générales qu'une liste à double lien (qui est malheureusement sujette à des bogues de modification simultanés en raison de sa mutabilité). Si vous spécifiez votre problème de manière plus précise, une telle structure peut probablement être trouvée.

La réponse générale pour la traversée (relativement) économique de structures immuables est les lentilles. L'idée est que vous pouvez conserver juste assez d'informations pour reconstruire une structure immuable modifiée à partir de ses parties non modifiées et de la pièce actuellement modifiée, et naviguer dessus jusqu'à un nœud voisin.

Une autre structure utile est une fermeture éclair . (La partie amusante est que la signature de type pour une fermeture éclair d' objectif est un dérivé mathématique de l'école d'une signature de type de la structure.)

Voici quelques liens.

9000
la source
1
en fonction de ce qui est nécessaire, une fermeture éclair peut également être utile
jk.
Pour spécifier plus précisément mon problème, supposons que je veuille programmer un système de réécriture de graphes, par exemple un évaluateur de calcul lambda basé sur la réécriture de graphes.
Alexey
1
@Alexey: Connaissez-vous le travail des Clean People sur la réécriture de graphiques? wiki.clean.cs.ru.nl/…
Giorgio
1
@Alexey: Pas que je sache: Clean est un cousin de Haskell qui a été développé seul. Il a également un mécanisme différent pour traiter les effets secondaires (AFAIK, il est appelé types uniques). D'un autre côté, les développeurs ont beaucoup travaillé avec la réécriture de graphes. Ils pourraient donc être parmi les meilleurs qui connaissent à la fois la réécriture de graphes et la programmation fonctionnelle.
Giorgio
1
Je suis d'accord qu'une fermeture à glissière semble résoudre le problème avec une liste doublement liée ou un arbre si je veux y naviguer et la modifier à l'endroit où je suis actuellement, mais il n'est pas clair que faire si je veux me concentrer sur plusieurs endroits simultanément et, par exemple, échanger deux éléments à deux endroits très éloignés. Il est encore moins clair s'il peut être utilisé avec des structures "circulaires".
Alexey
2

Haskell n'empêche pas l'utilisation de structures de données mutables. Ils sont fortement découragés et rendus plus difficiles à utiliser car les parties de code qui les utilisent doivent éventuellement renvoyer une action IO (qui doit finalement être liée à l'action IO renvoyée par la fonction principale), mais cela ne le fait pas. rendre impossible l'utilisation de telles structures si vous en avez vraiment besoin.

Je suggérerais d'étudier l'utilisation de la mémoire transactionnelle logicielle comme voie à suivre. En plus de fournir un moyen efficace de mettre en œuvre des structures mutables, il fournit également des garanties très utiles pour la sécurité des threads. Voir la description du module sur https://hackage.haskell.org/package/stm et la présentation du wiki sur https://wiki.haskell.org/Software_transactional_memory .

Jules
la source
Merci, je vais essayer d'en savoir plus sur la STM. On dirait qu'il ya plus de méthodes Haskell d'avoir mutabilité et de l' état (je l' ai tombe sur MVar, State, ST), donc je vais avoir besoin de comprendre leurs différences et utilisations prévues.
Alexey
@Alexey: Bon point concernant ST, OMI, il convient de le mentionner dans la réponse car il permet d'exécuter un calcul avec état, puis de jeter l'état et d'extraire le résultat en tant que valeur pure.
Giorgio
@Giorgio, est-il possible d'utiliser Haskell STavec STM pour avoir à la fois un accès simultané et un état jetable?
Alexey
Encore une suggestion terminologique: l'action d'E / S principale composée n'est pas " renvoyée par la fonction principale" mais est affectée à une mainvariable. :) ( mainn'a même pas de fonction.)
Alexey
Je vois votre point, mais "variable" a toujours une connotation dans l'esprit de la plupart des gens comme une valeur simple, plutôt que comme un processus qui produit une valeur, et principal est clairement mieux considéré comme ce dernier plutôt que le premier. Le changement que vous proposez, bien que clairement correct sur le plan technique, a le potentiel de confondre ceux qui ne connaissent pas le sujet.
Jules