¿Estructura de datos de superposición?

Question

Tengo un recursivo anidado y mutuo estructura de datos, y quiere asociar valores caros computacionales a algunos de los nodos. En realidad, quiero vincular temporalmente los bloques en un Pándoc Documente a la lista de palabras que ocurren en ese bloque.

Opciones poco atractivas que quiero evitar:

• Extender el tipo de datos de bloque de tal manera que incluya la lista de palabras, que se reduce a crear un nuevo tipo de datos PANDOC extendido con mucho código de placa de caldera (frágil)

• Mapeo de bloques a listas de palabras; que es subóptimo ya que los bloques son demasiado complejos para servir de manera eficiente como claves

La dirección en la que estoy buscando una solución es algún tipo de estructura de datos de superposición que incluya los bloques extendidos, pero con los tipos de datos subyacentes intactos, para que aún pueda usar las extensas bibliotecas pandoc. Pero quizás esta no es la forma de pensar haskell ...

Post Scriptum 2011-06-12:

Como muestran los comentarios, probablemente sobreestimé el costo del enfoque del mapa, en parte basado en suposiciones incorrectas. De hecho: "No hay nada más engañoso que un hecho obvio".

De todos modos, acepto la respuesta de Hammar, porque ilustra cómo crear un tipo de datos extensible.

Gracias

Answer 1

No puede agregar cosas a un tipo de datos existente cuando no fue diseñado para ser extensible, por lo que tendrá que confiar en alguna estructura externa, como un Map para asociar las listas de palabras a cada bloque.

Sin embargo, si pudiera cambiar el tipo de datos, podría hacerlo extensible generalizando la recursión en el tipo de datos. Supongamos que tiene un tipo de datos recursivos como este:

data Tree = Leaf | Fork String Tree Tree

Podemos agregar un parámetro para el uso recursivo de Tree:

data GenTree t = Leaf | Fork String t t

Ahora, para tener un árbol simple como el original, tomamos el punto fijo de este tipo:

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

Ahora, puede extender el tipo con datos adicionales en cada sitio recursivo. Aquí le mostramos cómo hacer un tipo para árboles etiquetados:

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)