覆盖数据结构？

Question

我有一个嵌套的,相互递归的数据结构,并希望将计算昂贵的值与某些节点相关联.实际上,我想暂时将Pandoc文档中的Blocks链接到该块中出现的单词列表.

我想避免的不吸引人的选择:

• 扩展Block数据类型,使其包含单词列表,归结为创建一个带有大量(易碎)样板代码的新扩展Pandoc数据类型

• 将块映射到单词列表; 由于块太复杂而无法有效地用作密钥,因此这是次优的

我正在寻求解决方案的方向是某种覆盖数据结构,其中包括扩展块,但底层数据类型未受影响,因此我仍然可以使用广泛的Pandoc库.但也许这不是哈斯克尔的思维方式......

后脚本2011-06-12:

正如评论所示,我可能高估了Map方法的成本,部分原因是基于错误的假设.确实:"没有什么比明显的事实更具欺骗性了".

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

谢谢

Answer 1

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

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

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)