Quel est l'avantage de la structure de données purement fonctionnelle?

Question

Il y a un grand nombre de textes sur les structures de données, et les bibliothèques de code structures de données. Je comprends que la structure de données purement fonctionnelle est plus facile de raisonner sur. Cependant, j'ai du mal à comprendre le réel avantage mondial d'utiliser la structure de données purement fonctionnelle dans le code pragmatique (en utilisant le langage de programmation fonctionnelle ou non) sur la contrepartie impératif. Quelqu'un peut-il fournir des cas réels où purement structure de données fonctionnelle a l'avantage et pourquoi?

Exemples le long de la ligne comme j'utilise data_structure_name programming_language pour faire application parce qu'il peut faire certain_thing .

Merci.

PS: Qu'est-ce que je veux dire par la structure de données purement fonctionnelle n'est pas la même que la structure de données persistantes. structure de données persistante est une structure de données qui ne change pas ?? Sur un autre côté purement structure de données fonctionnelle est une structure de données qui fonctionne uniquement.

Answer 1

Purement structures de données fonctionnelles (aka persistante ou immuable) vous donne plusieurs avantages:

• vous ne devez jamais les bloquer, ce qui améliore très concurrency .
• ils peuvent partager structure, réduit l'utilisation de la mémoire . Par exemple, considérez la liste [1, 2, 3, 4] dans Haskell et un langage impératif comme Java. Pour produire une nouvelle liste Haskell vous suffit de créer un nouveau cons (paire de valeur et de référence à la prochaine élément) et connectez-vous à la liste précédente. En Java, vous devez créer complètement nouvelle liste à ne pas endommager le précédent.
• vous pouvez faire des structures de données persistantes paresseux .
• aussi, si vous utilisez un style fonctionnel, vous pouvez éviter de penser de temps et la séquence des opérations , et ainsi, rendre vos programmes plus déclarative .
• fait que la structure de données est immuable, vous permet de faire des hypothèses plus et si de la langue d'étendre les fonctionnalités . Par exemple, Clojure utilise le fait de l'immuabilité correctement fournir des implémentations de méthode hashCode () sur chaque objet, de sorte que tout objet peut être utilisé comme une clé dans une carte.
• avec des données immuables et fonctionnel, vous pouvez également utiliser librement memoization .

Il y a beaucoup plus d'avantages, en général, il est une autre façon de modéliser le monde réel. Cette et quelques autres chapitres de SICP vous donnera vue plus précise de la programmation avec des structures immuables, ses avantages et ses inconvénients.

Answer 2

En plus de structures de sécurité de mémoire partagée plus de données purement fonction vous donnent également persistance , et pratiquement gratuitement. Par exemple, disons que j'ai un set en OCaml, et je veux ajouter quelques nouvelles valeurs à ce que je peux faire ceci:

module CharSet = Set.Make(Char)
let a = List.fold_right CharSet.add ['a';'b';'c';'d'] CharSet.empty in
let b = List.fold_right CharSet.add ['e';'f';'g';'h'] a in
...

reste de a non modifiée après avoir ajouté les nouveaux personnages (il ne contient que ad), tandis que b contient ah, et ils partagent une partie de la même mémoire (avec un set il est un peu difficile de dire combien la mémoire est partagée car il est un arbre AVL et la forme des changements d'arbres). Je peux continuer à faire cela, garder une trace de tous les changements que j'ai fait à l'arbre qui me permet de revenir à un état précédent.

Voici un diagramme de la Purement fonctionnel qui présente les résultats d'insertion du caractère 'e' dans le xs arbre binaire:

Answer 3

programmes Erlang utilisent des structures de données purement fonctionnelles presque exclusivement, et ils retirent des avantages substantiels en escaladant de façon presque transparente à plusieurs noyaux. Étant donné que les données partagées (principalement les binaires et les chaînes de bits) est jamais modifié, il n'y a jamais besoin de verrouiller ces données.

Answer 4

Prenez ce petit bout de F #:

let numbers = [1; 2; 3; 4; 5]

Vous pouvez dire avec certitude à 100% que c'est une liste immuable des entiers de 1 à 5. Vous pouvez passer autour d'une référence à cette liste et ne jamais avoir à craindre que la liste ait été modifiée. C'est une raison suffisante pour moi de l'utiliser.

Answer 5

structures de données fonctionnelles ont Purement les avantages suivants:

• La persistance:. Anciennes versions peuvent être réutilisées en sachant qu'ils ne peuvent pas avoir été modifiés

• Partage:. De nombreuses versions d'une structure de données peuvent être conservées en même temps que les exigences de mémoire modestes

• Sécurité du fil:. Une mutation est cachée à l'intérieur des thunks paresseux (le cas échéant) et, par conséquent, géré par la mise en œuvre de la langue

• Simplicité:. Ne pas avoir à garder une trace des changements d'état fait des structures de données purement fonctionnelles plus simples à utiliser, en particulier dans le contexte de la concurrence

• Incrémentalité. Structures de données purement fonctionnelles sont composées de nombreuses pièces minuscules, ce qui les rend idéales pour la collecte des ordures supplémentaires conduisant à réduire les latences

Notez que je n'ai pas le parallélisme répertorié comme un avantage des structures de données purement fonctionnelles, parce que je ne crois pas que ce soit le cas. parallélisme efficace multicoeur nécessite localité prévisible pour les caches de levier et éviter de se goulot d'étranglement sur l'accès partagé à la mémoire principale et les structures de données purement fonctionnelles ont, au mieux, des caractéristiques inconnues à cet égard. Par conséquent, de nombreux programmes qui utilisent des structures de données purement fonctionnelles n'échelle pas bien quand parallélisé sur un multi-cœurs parce qu'ils passent tout leur temps à cache misses, se disputant les voies de mémoire partagée.

  

Qu'est-ce que je veux dire par la structure de données purement fonctionnelle n'est pas la même que la structure de données persistantes.

Il y a une certaine confusion. Dans le cadre des structures de données purement fonctionnelles, la persistance est un terme utilisé pour désigner la possibilité de se référer aux versions précédentes d'un coffre-fort de la structure de données en sachant qu'ils sont toujours valables. Ceci est le résultat naturel de l'être purement fonctionnelle et, par conséquent, la persistance est une caractéristique inhérente de toutes les structures de données purement fonctionnelles.