8

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

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

  • 扩展 Block 数据类型，使其包含单词列表，这归结为创建具有大量（脆弱）样板代码的新扩展 Pandoc 数据类型

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

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

发布脚本 2011-06-12：

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

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

谢谢

4

1 回答 1

4

当现有数据类型的设计不是可扩展的时，您无法向其添加内容，因此您将不得不依赖一些外部结构，例如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)
于 2011-06-11T15:09:43.030 回答