data-structures - 覆盖数据结构？

Question

我有一个嵌套的、相互递归的 data structure ，并希望将计算昂贵的值与某些节点相关联。实际上，我想暂时链接 Pandoc 中的 block 文档到该 block 中出现的单词列表。

我想避免的没有吸引力的选择:

扩展 Block 数据类型，使其包含单词列表，这归结为创建一个新的扩展 Pandoc 数据类型，其中包含许多(脆弱的)样板代码

将 block 映射到单词列表；这是次优的，因为 block 太复杂而无法有效地用作键

我寻求解决方案的方向是某种覆盖数据结构，其中包括扩展 block ，但底层数据类型不受影响，因此我仍然可以使用广泛的 Pandoc 库。但也许这不是 Haskell 的思维方式……

发布脚本 2011-06-12 :

正如评论所示，我可能高估了 Map 方法的成本，部分原因是错误的假设。确实:“没有什么比一个明显的事实更具欺骗性了”。

无论如何，我接受 hammar 的答案，因为它说明了如何创建可扩展的数据类型。

谢谢

Answer 1

当现有数据类型的设计不是可扩展时，您无法向其添加内容，因此您将不得不依赖一些外部结构，例如 Map将单词列表与每个 block 相关联。

但是，如果您可以更改数据类型，则可以通过概括数据类型中的递归来使其可扩展。假设您有这样的递归数据类型:

data Tree = Leaf | Fork String Tree Tree

我们可以为 Tree的递归使用添加一个参数:

data GenTree t = Leaf | Fork String t t

现在，为了得到一棵像原始树一样的普通树，我们采用这种类型的不动点:

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

现在，您可以在每个递归站点使用附加数据扩展该类型。以下是为标记树创建类型的方法:

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)