覆盖数据结构？

Question

覆盖数据结构？

data-structureshaskellpandoc

8

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

我不想使用的不良选项：

- 扩展块数据类型，使其包括单词列表，这意味着创建一个带有大量（脆弱的）样板代码的新扩展 Pandoc 数据类型。 - 将块映射到单词列表；由于块太复杂而无法有效地用作键，这是次优选择。

我正在寻求的解决方案方向是某种覆盖数据结构，其中包括扩展块，但底层数据类型保持不变，以便我仍然可以使用广泛的 Pandoc 库。但也许这不是 Haskell 的思考方式...

后记 2011-06-12：

正如评论所示，我可能高估了Map方法的成本，部分是基于错误的假设。确实：“没有比显而易见的事实更具欺骗性的了”。

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

谢谢

- sleepyMonad

@Don Stewart：你是指从块到WordList的Data.Map吗？是的，但我担心将块作为键会使数据结构过于复杂。通常它代表整个段落及其格式，可能包括其他块。 - sleepyMonad

2

在存储为键之前对块进行哈希处理？ - luqui

1

或者直接使用 HashMap（来自 unordered-containers 库）。 - Thomas M. DuBuisson

1

在驳回将块作为关键因素的想法之前，或许你应该尝试一下。 - augustss

@sleepyMonad 错误的假设。Data.Map 不会在后台进行哈希操作。它只是使用 Ord 实例，在树中比较键值对（用于插入）。我建议使用的包，unordered-containers（模块 Data.HashMap.{Strict,Lazy}），将对键进行哈希处理。 - Thomas M. DuBuisson

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hammar · Accepted Answer

如果现有的数据类型没有被设计成可扩展的，那么您无法向其中添加内容，因此您需要依赖于一些外部结构，例如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)