Structures de données complexes dans Haskell - comment fonctionnent-elles?

Comme je l'ai découvert, les variables dans Haskell sont immuables (donc, ce ne sont pas vraiment des `variables ').Structures de données complexes dans Haskell - comment fonctionnent-elles?

Dans ce cas, si nous avons une structure de données complexe et volumineuse, comme un arbre rouge-noir, comment sommes-nous supposés implémenter des opérations qui changent réellement la structure de données?

Créer une copie de l'arborescence à chaque fois qu'un élément est inséré ou supprimé?

Source

2011-01-04 Anonymous

+10

"Ainsi, ils ne sont pas vraiment \' variables '"- Bien sûr qu'ils le sont. Par exemple, quand un mathématicien dit "Soit * G * le groupe (* S *, \ *), où ...", le * G * est une variable, même si ça ne va jamais changer. C'est le même principe chez Haskell. –

vous soulignez certainement un point intéressant, en effet la structure change un peu pour s'adapter à l'immuabilité sans sacrifier la performance. Pensez à votre structure comme un graphe orienté (où une arête de A à B signifie que A contient une référence/index à B), alors si vous souhaitez changer B, tout sommet à partir duquel B était accessible doit être copié et sa référence mise à jour . Je n'ai toujours pas trouvé comment représenter une liste de raccourcis dans Haskell par exemple :) –

Oui, la solution consiste à renvoyer une nouvelle structure de données représentant la valeur modifiée, mais il n'est pas nécessaire de copier la structure entière pour votre exemple (arbres rouge-noir) car vous pouvez simplement copier les nœuds sur le chemin de la racine au noeud inséré. Cela permet à l'opération d'insertion d'avoir la même complexité que la version impérative.

Chris Okasaki Purely functional data structures contient un certain nombre de mises en œuvre de structures de données immuables - ce livre est une version modifiée de sa thèse que vous pouvez trouver here

Source

2011-01-04 19:08:33 Lee

Et pour aller au-delà du livre d'Okasaki: [Quoi de neuf dans les structures de données purement fonctionnelles depuis Okasaki?] (Http://cstheory.stackexchange.com/questions/ 1539/whats-new-in-pure-functional-data-structures-since-okasaki) – Gilles

La thèse de doctorat est un lien mort. – fuz

@FUZxxl: il semble que citeseerx.ist.psu.edu soit en panne pour quelques raisons, espérons que ça va revenir. –

Votre intuition sur la copie est exactement la bonne direction, vous devriez penser. Cependant, la 'copie' est implémentée intelligemment par le runtime Haskell. Par exemple, étant donné

data Tree = Empty | Branch Tree Integer Tree

Vous pouvez implémenter une fonction pour remplacer la branche gauche:

replaceLeft :: Tree -> Tree -> Tree 
replaceLeft (Branch _ i r) newLeft = Branch newLeft i r

Le résultat est pas que vous créez une copie entière du nouvel arbre, comme ce n'est pas nécessaire. La valeur i et les arbres r et newLeft sont inchangés, nous n'avons donc pas besoin de copier leur contenu dans une nouvelle mémoire.

Le nouveau Branch est créé (il s'agit de la seule allocation réelle dans cet exemple: la création de la structure pour contenir les arbres gauche/droit sur le Integer) fait toujours référence aux mêmes valeurs de l'ancienne branche, pas de copie nécessaire!

Étant donné que les structures de données sont immuables, il n'y a pas de mal à le faire.

Source

2011-01-04 19:19:16 ScottWest

J'aime l'attention à l'immuabilité: c'est précisément l'immutabilité qui nous permet d'atteindre ce partage. – luqui

Structures de données complexes dans Haskell - comment fonctionnent-elles?

Répondre

Questions connexes