haskell - Haskell中的O(1)循环缓冲区？

Question

我正在 Haskell 中进行一个需要循环缓冲区的小型概念项目。我已经设法使用具有 O(1) 旋转的数组创建了一个缓冲区，但当然需要 O(N) 进行插入/删除。我找到了一个使用列表的实现，它似乎需要 O(1) 来进行插入和删除，但由于它维护一个左右列表，因此在旋转时越过某个边界需要 O(N) 时间。在命令式语言中，我可以实现一个具有 O(1) 插入、删除和旋转的双向链接循环缓冲区。我认为这在像 Haskell 这样的纯函数式语言中是不可能的，但我很想知道我是否错了。

Answer 1

如果您可以处理摊销 O(1) 操作，您可能可以使用 Data.Sequence来自容器包，或 Data.Dequeue从出队包。前者使用finger trees ，而后者使用冈崎 Purely Functional Data Structures 中的“银行家出队” (之前的在线版本 here )。