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

Question

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

Answer 1

如果您可以处理摊销的 O(1)操作,您可以使用Data.Sequence容器包或Data.Dequeuedequeue包.前者使用指树,而后者使用Okasaki的Purely Functional Data Structures的"Banker's Dequeue" (这里是在线的先前版本).

Answer 2

monadST允许在 Haskell 中描述和执行命令式算法。您可以使用STRefs作为双向链表的可变指针。

使用 描述的自包含算法ST是使用 执行的runST。不同的runST执行可能不共享ST数据结构（STRef, STArray, ..）。

如果算法不是“自包含的”并且需要在使用之间执行 IO 操作来维护数据结构，则可以使用monadstToIO来访问它IO。

关于这是否纯粹是功能性的 - 我想不是吗？