struttura dei dati di overlay

Question

Ho un nidificato, ricorsiva reciproca struttura di dati , e vogliono associare i valori costosi computazionali ad alcuni dei nodi. In realtà, io voglio collegare temporaneamente i blocchi in un href="http://johnmacfarlane.net/pandoc/" rel="nofollow" title="Pandoc"> Pandoc documento

opzioni poco attraente voglio evitare:

• estendere il tipo di dati di blocco in modo tale che esso include l'elenco di parole, che si riduce a creare un nuovo tipo di dati Pandoc esteso con un sacco di (fragili) Codice piastra della caldaia

• blocchi di mappatura per liste di parole; che è subottimale i blocchi sono troppo complesse per servire in modo efficiente come tasti

La direzione che sto cercando una soluzione è una sorta di struttura di dati di sovrapposizione che include i blocchi estesi, ma con i tipi di dati sottostanti intatta, in modo che io possa ancora utilizzare le ampie librerie Pandoc. Ma forse questo non è il modo di pensare ... Haskell

Post scriptum 2011-06-12 :

Per quanto i commenti che dimostrano, probabilmente sopravvalutato il costo dell'approccio Map, in parte basata su presupposti errati. Infatti: "non c'è niente di più ingannevole di un fatto ovvio"

Comunque, accetto la risposta di Hammar, perché illustra come creare un tipo di dati estendibile.

Grazie

Answer 1

You can't add stuff to an existing data type when it was not designed to be extensible, so you're going to have to rely on some external structure such as a Map to associate the word lists to each block.

If you could change the datatype however, you could make it extensible by generalizing the recursion in the data type. Let's say you have a recursive data type like this:

data Tree = Leaf | Fork String Tree Tree

We can add a parameter for the recursive usage of Tree:

data GenTree t = Leaf | Fork String t t

Now, to have a plain tree like the original, we take the fixed point of this type:

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

Now, you can extend the type with additional data at each recursive site. Here's how to make a type for labelled trees:

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)