O（1）haskell中的循环缓冲区？

Question

我正在研究一个需要循环缓冲区的Haskell中的一个小概念项目。我已经设法使用具有O（1）旋转的数组创建缓冲区，但是当然需要O（N）来插入/删除。我发现了一个使用列表的实现，它看起来需要O（1）来插入和删除，但由于它保持了左右列表，所以在旋转时会跨越一定的边界需要O（N）时间。在命令式语言中，我可以实现带有O（1）插入，删除和旋转的双向循环缓冲区。我认为这不可能像Haskell这样的纯粹功能语言，但我很想知道我是否错了。

Answer 1

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

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

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

关于这是纯粹的功能与否 - 我猜这不是？

Answer 2

如果你能处理摊销 O（1）操作，你很可能要么Data.Sequence从容器包装，或Data.Dequeue从出队包。前者使用finger trees，而后者使用来自Okasaki的Purely Functional Data Structures（先前版本在线here）的“Banker's Dequeue”。

Answer 3

这听起来像你可能需要一些比这更复杂的东西（因为你提到了双链表），但也许这会有所帮助。这个功能就像map在一个可变循环列表：

mapOnCycling f = concat . tail . iterate (map f) 

使用，如：

*Main> (+1) `mapOnCycling` [3,2,1] 

[4,3,2,5,4,3,6,5,4,7,6,5,8,7,6,9,8,7,10,9...] 

这里还有一个就像mapAccumL：

mapAccumLOnCycling f acc xs = 
    let (acc', xs') = mapAccumL f acc xs 
    in xs' ++ mapAccumLOnCycling f acc' xs' 

无论如何，如果你愿意细说甚至更重要的是你的数据结构需要能够“做什么”，我真的很有兴趣听到它。

编辑：如camccann提到的，你可以使用Data.Sequence用于此目的，根据文档应该给你O1的时间复杂度（出现这样的事，作为O1摊销时间？）观看或添加元素同时向序列的左侧和右侧，以及沿途修改末端。这是否会有你需要的表现，我不确定。

您可以将“当前位置”视为序列的左端。在这里，我们沿着一个序列来回穿梭，产生无限的价值清单。很抱歉，如果它不能编译，我没有GHC的时刻：

shuttle (viewl-> a <: as) = a : shuttle $ rotate (a+1 <| as) 
    where rotate | even a = rotateForward 
       | otherwise = rotateBack 
      rotateBack (viewr-> as' :> a') = a' <| as' 
      rotateForward (viewl-> a' <: as') = as' |> a'