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

Question

Il ya un grand nombre de textes sur les structures de données et de bibliothèques de structures de données de code. Je comprends que purement fonctionnelle de la structure de données est plus facile de raisonner sur. Cependant j'ai du mal à comprendre le monde réel avantage de l'utilisation purement fonctionnelle de la structure de données dans la pragmatique de code (à l'aide de langage de programmation fonctionnel ou pas) sur l'impératif de contrepartie. Quelqu'un peut-il fournir quelques vrais cas où purement fonctionnelle de la structure de données a un avantage et pourquoi?

Exemples le long de la ligne comme je l'ai utiliser data_structure_name dans programming_language de faire application parce qu'il peut faire certain_thing.

Merci.

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

Answer 1

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

• vous n'avez jamais à les bloquer, ce qui est extrêmement améliore la simultanéité.
• ils peuvent partager de la structure, ce qui réduit l'utilisation de la mémoire. Par exemple, examiner la liste [1, 2, 3, 4] en Haskell et certains impératif de langues comme Java. Pour produire une nouvelle liste en Haskell, vous n'avez qu'à créer de nouveaux cons (la paire de valeur et de référence-à-côté-de l'élément) et le connecter à la liste précédente. En Java, vous devez créer complètement nouvelle liste à ne pas endommager la précédente.
• vous pouvez faire persistante des structures de données paresseux.
• aussi, si vous utilisez le style fonctionnel, vous pouvez éviter de penser le temps et la séquence des opérations, et rendre vos programmes plus déclaratif.
• fait, que la structure de données est immuable, qui permet de faire un peu plus d'hypothèses et donc d'étendre les fonctionnalités de la langue. Par exemple, Clojure utilise le fait de l'immuabilité correctement à fournir des implémentations de hashCode() la méthode sur chaque objet, de sorte que tout objet peut être utilisé comme une clé dans une carte.
• avec des données immuables et fonctionnelle de style, vous pouvez également utiliser librement memoization.

Il y a beaucoup plus d'avantages, en général, c'est une autre façon de modéliser le monde réel. Ce et certains autres chapitres de SICP va vous donner la vision plus précise de la programmation avec immuables, de structures, de ses avantages et inconvénients.

Answer 2

En plus de la mémoire partagée de la sécurité la plupart purement fonction des structures de données vous donnent aussi la persistance, et pratiquement gratuitement. Par exemple, disons que j'ai un set en OCaml, et je tiens à ajouter quelques nouvelles valeurs à elle 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
...

a reste non modifiée après l'ajout de nouveaux personnages (il ne contient que a-d), tandis que l' b contient un-h, et elles partagent la même mémoire (avec un set c'est le genre de difficile de dire quelle quantité de mémoire est partagée puisque c'est un arbre AVL et la forme de l'arbre de changements). Je peux continuer à faire cela, garder la trace de toutes les modifications que j'ai apportées à l'arbre de me permettre de revenir à un état précédent.

Voici un grand diagramme à partir de l' article de Wikipédia sur le plan Purement Fonctionnel , qui montre les résultats d'insérer le caractère " e " dans l'arbre binaire xs:

Answer 3

Les programmes Erlang utilisent presque exclusivement des structures de données purement fonctionnelles et tirent des avantages substantiels en évoluant de manière presque transparente vers plusieurs cœurs. Les données partagées (principalement les fichiers binaires et les chaînes de bits) n'étant jamais modifiées, il n'est jamais nécessaire de verrouiller ces données.

Answer 4

Prenez ce petit extrait de F #:

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

Vous pouvez dire avec une certitude à 100% qu'il s'agit d'une liste immuable d'entiers de 1 à 5. Vous pouvez transmettre une référence à cette liste sans avoir à vous inquiéter du fait que cette liste a peut-être été modifiée. C'est une raison suffisante pour moi de l'utiliser.

Answer 5

Purement fonctionnelle des structures de données ont les avantages suivants:

• La persistance: les anciennes versions peuvent être réutilisés en toute sécurité en sachant qu'ils ne peuvent pas avoir été modifié.

• Partage: de nombreuses versions d'une structure de données peut être gardés simultanément avec très peu de mémoire.

• Fil de sécurité: toute mutation est caché à l'intérieur du paresseux thunks (le cas échéant) et, par conséquent, gérées par le langage de mise en œuvre.

• Simplicité: ne pas avoir à garder une trace des modifications de l'état de fait purement fonctionnelle des structures de données plus simple à utiliser, en particulier dans le contexte de la concurrence.

• L'apport différentiel: purement fonctionnelle des structures de données est composée de nombreuses petites pièces, ce qui les rend idéal pour incrémentale à une diminution de la latence.

Notez que je n'ai pas répertorié parallélisme comme un avantage purement fonctionnelle des structures de données parce que je ne crois pas que cela soit le cas. Efficace multicœur parallélisme exige prévisible de la localité, afin de tirer parti des caches et éviter de devenir un goulot d'étranglement sur le partage de l'accès à la mémoire principale et purement fonctionnelle des structures de données ont, au mieux, de l'inconnu caractéristiques à cet égard. Par conséquent, de nombreux programmes qui utilisent purement fonctionnelle des structures de données ne sont pas à l'échelle lorsque parallélisé sur un multicœur, car ils consacrent tout leur temps dans le cache, la lutte pour la mémoire partagée des voies.

Ce que je veux dire par purement fonctionnelle de la structure de données n'est pas la même que persistante de la structure de données.

Il y a une confusion ici. Dans le contexte d'une approche purement fonctionnelle des structures de données, la persévérance est un terme utilisé pour se référer à la capacité de se référer à des versions précédentes de la structure des données en toute sécurité en sachant qu'ils sont toujours valides. C'est un résultat naturel de l'être purement fonctionnel et, par conséquent, la persévérance est une caractéristique inhérente à tous purement fonctionnelle des structures de données.