为什么Data.Sequence.reverse O(n)？

Question

文件说Data.Sequence.reverse是O(n).通过设置标志,有限序列类型不能"反转"吗？(实际上,从"开始计算"结束.)

Answer 1

如果只有一个标志，就会遇到问题。假设我想要

xs <> reverse xs

我该如何计算呢？如果只有一个标志，我必须在附加之前执行昂贵的反向操作。要真正做到这一点，您需要更多的旗帜，分布在树周围。都在树的周围。树中的每个节点都需要携带反转信息。这绝对是可能的，但是有点贵。更糟糕的是，每个操作的每一步都必须适当地管理反转标志，这对于必须编写和维护代码的人来说有点噩梦。这个想法已经在某处的一篇论文中得到了解决（我不记得是哪一篇），但在实践中它并不有趣。

如果您有一个基本上依赖于反转的算法，那么您应该使用带有大量标志的自定义序列类型，并仅包含您需要的操作（如果您的类型基于Data.Sequence，您可能应该从每个大小中窃取一位场地）。但我不认为这样的算法非常常见。