Algorithme de l'arbre bottom up fonctionnel pur

Question

Dire que je voulais écrire un algorithme travaillant sur une structure de données arborescente immuable qui a une liste de feuilles comme son entrée. Il a besoin de retourner un nouvel arbre avec les changements faits au vieil arbre allant vers le haut à partir de ces feuilles.

Mon problème est qu'il semble y avoir aucun moyen de faire cela purement fonctionnel sans reconstruire l'arbre entier vérifiant aux feuilles si elles sont dans la liste, parce que vous devez toujours retourner un nouvel arbre complet à la suite d'une opération et vous ne pouvez pas muter l'arbre existant.

Est-ce un problème fondamental dans la programmation fonctionnelle qui peut seulement être évité en utilisant un algorithme mieux adapté ou est-ce que je manque quelque chose?

Éditer: Je ne veux pas seulement éviter de recréer l'arbre entier mais aussi l'algorithme fonctionnel devrait avoir la même complexité de temps que la variante de mutation.

Answer 1

Le plus prometteur que je l'ai vu jusqu'à présent (ce qui est très longue, certes ...) est le Zipper data structure: Il conserve essentiellement une structure distincte, un chemin inverse du nœud à la racine et effectue des modifications locales sur cette structure séparée.

Il peut effectuer plusieurs modifications locales, dont la plupart sont à temps constant, et les réécrire dans l'arborescence (en reconstruisant le chemin d'accès à la racine, qui sont les seuls nœuds à modifier) ​​en une seule fois. La fermeture à glissière est une standard library in Clojure (voir la rubrique Fermetures à glissière - Édition de l'arborescence fonctionnelle).

Et il y a the original paper by Huet avec une implémentation dans OCaml. Disclaimer: Je programme depuis longtemps, mais j'ai seulement commencé la programmation fonctionnelle il y a quelques semaines, et je n'avais même jamais entendu parler du problème de l'édition fonctionnelle des arbres jusqu'à la semaine dernière, donc il peut très bien y avoir d'autres des solutions que je ne connais pas.

Pourtant, il semble que la Zipper fait la plupart de ce que l'on peut souhaiter. S'il y a d'autres alternatives à O (log n) ou moins, j'aimerais les entendre.

Answer 2

Cela dépend de votre langage de programmation fonctionnel. Par exemple, dans Haskell, qui est un langage de programmation fonctionnel Lazy, les résultats sont calculés au dernier moment; quand ils sont nécessaires. Dans votre exemple, l'hypothèse est la suivante: comme votre fonction crée une nouvelle arborescence, l'intégralité de l'arborescence doit être traitée, alors qu'en réalité, la fonction est simplement transmise à la fonction suivante et exécutée uniquement si nécessaire.

Un bon exemple d'évaluation paresseuse est le sieve of erastothenes dans Haskell, qui crée les nombres premiers en éliminant les multiples du nombre actuel dans la liste des nombres. Notez que la liste des nombres est infinie. Tiré de here

primes :: [Integer] 
primes = sieve [2..] 
    where 
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0] 

Answer 3

Vous pouvez profiter de la lecture

http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!248.entry