问题标签 [finger-tree]

fmap我需要for Seqfrom Data.Sequencepackage的并行（但懒惰）版本。但是包不导出任何Seq数据构造函数。所以我不能直接把它包装进去newtype并Functor直接为newtype.

我可以在不重写整个包的情况下做到这一点吗？

单调优先级队列是否有可能：

1. O(1) 用于查找和删除具有最高优先级的项目，
2. O(1) 用于插入项目，假设给定的优先级低于所有其他项目，
3. O(log n) 用于在没有假设的情况下插入和删除项目？

我确实知道通过使用链表是否允许插入和删除是 O(n)。我也在考虑跳过列表。但是，在最坏的情况下，插入和删除项目是 O(n)。

不需要减少键。

给定一个可以随时间演变其版本和分支的实体（例如文件或库/包），寻找优化的数据结构，让我可以通过版本导航到实体的特定实例。

例如（有点做作的例子）给定条目，例如：

我怀疑已经存在类似的东西（因为包管理或源代码管理利用类似于上述访问语义）。

我一直在寻找具有良好最新/最早访问时间以及下降插入/删除速度的上述内存数据结构。

在残酷的强制方法中，我认为可以 为每个可以有版本的分支使用Min Max heap来实现上述内容。

但是，可能已经有更好的东西了。我还检查了我通常的这些类型的东西的来源，Redisson——但没有看到是否有上述数据结构的显式实现

上面的 DSL 是我自己构建的，可能也有一些漏洞，所以如果有更好的 DSL/API 用于这种数据访问——也想学习。

我想按照Hinze的 (Haskell) 论文中的描述使用 2-3 个手指树（另请参阅此博客）。

现在我无法让viewl函数工作，它抱怨类型不匹配：

期待一个 FingerTree<'a> 但给定一个 FingerTree>。

当统一 ''a' 和 'Node<'a>' FingerTree 时，生成的类型将是无限的。

我之前遇到过这个错误，prepend但能够通过在函数上添加完整的类型信息来解决它。

因为viewl这似乎还不够，所以我也尝试在函数中间添加类型（查找注释）。它没有用。

我有点理解错误以及它的来源。谁能告诉我如何让这个工作？恕我直言，这应该是可能的，因为否则prepend也不会编译。也许这样的技巧有帮助？（虽然不明白）。

PS：我还将代码放在FsSnip上，以便在浏览器中播放。

我刚刚第二次阅读Apfelmus 对手指树的精彩介绍，并开始怀疑他对 head 的实现：

由于相互实现功能是重用代码的一种非常好的方式，因此我开始思考以下实现是否与他的原始实现一样高效（复杂性）：

惰性评估是否与原始实现一样有效？

该Applicative实例Data.Sequence通常表现得非常好。几乎所有的方法在时间和空间上都是渐进渐近最优的。也就是说，给定完全强制/实现的输入，可以在渐近最优时间和内存驻留中访问结果的任何部分。还有一个例外：(<*). 我只知道两种实现它的方法：

1. 默认实现

   这种实现需要O(|xs| * |ys|)时间和空间来完全实现结果，但只能O(log(min(k, |xs|*|ys|-k)))访问k结果的第 th 元素。

2. “一元”实现

   这只需要O(|xs| * log |ys|)时间和空间，但不是增量的；访问结果的任意元素需要O(|xs| * log |ys|)时间和空间。

长期以来，我一直认为应该可以拥有我们的蛋糕并吃掉它，但我从来没有能够很好地在脑海中处理这些碎片以到达那里。这样做似乎需要结合 和 的实现中的想法（但不是实际代码liftA2）replicate。如何才能做到这一点？

注意：肯定没有必要加入rigidify类似liftA2. 类似replicate的部分肯定只产生我们rigidify用来从用户提供的树中获取的那种“刚性”结构。

更新（2020 年 4 月 6 日）

任务完成！我设法找到了办法。不幸的是，这对我来说有点太复杂了，无法理解正在发生的一切，而且代码......相当不透明。我会赞成并接受对我所写内容的一个很好的解释，并且也会很高兴地接受关于提高清晰度的建议和在 GitHub 上的评论。

更新 2

非常感谢 Li-Yao Xia 和 Bertram Felgenhauer 帮助清理和记录我的代码草案。现在它的理解难度大大降低，并将出现在containers. 得到一个答案来结束这个问题仍然会很好。