haskell - 为什么 FingerTrees 的使用不足以实现稳定的实现？

Question

前段时间，我遇到了an article on FingerTrees (另见 an accompanying Stack Overflow Question )并将这个想法归档。我终于找到了使用它们的理由。

我的问题是 Data.FingerTree package似乎边缘有点腐烂。此外，Data.Sequence在使用数据结构 re-implements 的 Containers 包中一个(可能更好的)版本，但不导出它。

尽管这种结构在理论上看起来很有用，但它似乎并没有得到很多实际使用或关注。有没有人发现FingerTrees作为一个实际的东西没有用，或者这是一个不够重视的案例？

进一步解释 :

我有兴趣构建一个包含具有良好连接属性的文本的数据结构。考虑从各种片段构建 HTML 文档。大多数预构建的解决方案都使用字节串，但我真的想要一些能正确处理 Unicode 文本的东西。我目前的计划是将 Data.Text 片段分层到 FingerTree 中。

我还想借用 Data.Vector 的技巧，即在不使用 (offset,length) 操作进行复制的情况下获取切片。 Data.Text.Text 已将此内置到数据类型中，但仅将其用于有效的 uncons 和 unsnoc 操作。在 FingerTree 中，此信息很容易变成 v或树的注释。

Answer 1

要特别回答您关于手指树的问题，我认为问题在于它们与数组相比具有相对较高的恒定成本，并且比实现有效连接的其他方法更复杂。一个 Builder 有一个更有效的界面来附加 block ，它们通常很容易获得(参见@informatikr 答案中的链接)。假设 Data.Text.Lazy用 block 的链表实现，你正在创建一个 Data.Text.Lazy来自建筑商。除非您有很多 block (可能超过 50 个)，或者重复访问列表末尾附近的数据，否则手指树的高固定成本可能不值得。
Data.Sequence出于性能原因，实现是专门的，不如fingertree 提供的完整接口(interface)通用。包裹。这就是它不被导出的原因；除了 Sequence 之外，它实际上不可能用于任何其他用途。 .

我还怀疑许多程序员对于如何实际使用 monoidal 注释不知所措，因为它存在相当大的抽象障碍。很多人不会使用它，因为他们看不到它与其他数据类型相比有何用处。

直到我在 word numbers 上阅读了 Chung-jieh Shan 的博客系列时才真正明白。 (part2、part3、part4)。这证明了这个想法绝对可以在实际代码中使用。

在您的情况下，如果您需要检查部分结果并进行有效的附加，则使用手指树可能比构建器更好。根据构建器的实现，您最终可能会在转换为 Text 时进行大量重复工作。 ，向构建器添加更多内容，转换为 Text再等等。不过，这取决于您的使用模式。

您可能对我的 splaytree 感兴趣包，它提供了带有单曲面注释的展开树，并在它们之上构建了几种不同的结构。除了展开树本身，Set和 RangeSet模块具有或多或少完整的 API，Sequence模块主要是我用于测试的骨架。它不是您正在寻找的“包含电池”的解决方案(同样，@informatikr 的答案提供了这些)，但如果您想尝试使用单曲面注释，它可能比 Data.FingerTree 更有用.请注意，如果您按顺序遍历所有元素(或连续 snoc 到末尾或类似)，则展开树可能会变得不平衡，但如果追加和查找交错，则性能可能会非常好。