Overlay data structure?

Question

I have a nested, mutual recursive data structure, and want to associate computational expensive values to some of the nodes. Actually, I want to temporarily link the Blocks in a Pandoc document to the list of words occuring in that block.

Unattractive options I want to avoid:

• extending the Block data type such that it includes the word list, which boils down to creating a new extended Pandoc datatype with lots of (fragile) boiler plate code

• mapping blocks to word lists; which is suboptimal as the blocks are too complex to serve efficiently as keys

The direction I am seeking a solution is some kind of overlay data structure that includes the extended Blocks, but with the underlying data types untouched, so that I can still use the extensive Pandoc libraries. But perhaps this is not the Haskell Way of Thinking...

Post scriptum 2011-06-12:

As the comments show, I probably overestimated the cost of the Map approach, partly based on wrong assumptions. Indeed: "there is nothing more deceptive than an obvious fact".

Anyway, I accept the answer of hammar, because it illustrates how to create an extensible data type.

Thanks

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)