structure de recouvrement de données?

Question

J'ai un récursive imbriquée, mutuelle structure de données et veulent associer les valeurs de calcul coûteuses à certains des nœuds. En fait, je veux lier temporairement les blocs dans un document Pandoc à la liste des mots se produisant dans ce bloc.

Options inesthétiques Je veux éviter:

• l'extension du type de données blocs tel qu 'il comprend la liste de mots, ce qui revient à créer un nouveau type de données Pandoc étendu avec beaucoup de code de plaque de la chaudière (fragile)

• blocs de mappage à des listes de mots; qui est suboptimale que les blocs sont trop complexes pour servir efficacement les touches

Le sens que je suis à la recherche d'une solution est une sorte de structure de recouvrement de données qui comprend les blocs étendus, mais avec les types de données sous-jacentes intacte, de sorte que je peux encore utiliser les vastes bibliothèques pandoc. Mais peut-être ce n'est pas la voie de la pensée Haskell ...

Post Scriptum 2011-06-12 :

Comme les commentaires montrent, je probablement surestimé le coût de l'approche carte, en partie fondées sur des hypothèses erronées. En effet:. « Il n'y a rien de plus trompeur qu'un fait évident »

Quoi qu'il en soit, j'accepte la réponse de Hammar, car il illustre comment créer un type de données extensible.

Merci

Answer 1

Vous ne pouvez pas ajouter des choses à un type de données existantes quand il n'a pas été conçu pour être extensible, de sorte que vous allez devoir compter sur une structure externe, comme un Map associer les listes de mots à chaque bloc.

Si vous pouviez changer le type de données cependant, vous pouvez le rendre extensible en généralisant la récursion dans le type de données. Disons que vous avez un type de données récursif comme ceci:

data Tree = Leaf | Fork String Tree Tree

Nous pouvons ajouter un paramètre pour l'utilisation récursive de Tree:

data GenTree t = Leaf | Fork String t t

Maintenant, d'avoir un arbre plaine comme l'original, nous prenons le point fixe de ce type:

data Fix a = Fix (a (Fix a))
type Tree = Fix GenTree

Maintenant, vous pouvez étendre le type avec des données supplémentaires sur chaque site récursive. Voici comment faire un type pour les arbres marqués:

data Labelled t = Labelled Int (GenTree t)
type LabelledTree = Fix Labelled

strLength :: GenTree t -> Int
strLength Leaf = 0
strLength (Fork str _ _) = length str

label :: Tree -> LabelledTree
label (Fix tree) = Fix $ Labelled (strLength tree) (fmap label tree)

instance Functor GenTree where
    fmap f Leaf = Leaf
    fmap f (Fork s l r) = Fork s (f l) (f r)