Quel dictionnaire arborescent est le plus facile à implémenter fonctionnellement?

Question

Je suis à la recherche d'une structure de dictionnaire de données arborescente qui est facile à mettre en œuvre Haskell. Avez-vous de l'expérience dans la mise en œuvre d'arborescences AVL ou d'arborescences RB? Je pense aussi aux arbres splay, mais je ne vois pas comment ils pourraient être implémentés en utilisant des données immuables.

Answer 1

Les arborescences rouge-noir sont très faciles à implémenter dans un langage fonctionnel, car vous n'avez pas besoin de faire des efforts pour rogner quelques affectations, et the usual description of algorithms correspond très bien à la correspondance de modèle. Voir Okasaki, Red-Black Trees in a Functional Setting. En fait, son book, qui est la version révisée et étendue de son thesis, est une excellente référence pour de nombreuses structures de données purement fonctionnelles.