20

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

4

3 回答 3

11

如果您可以处理分期O(1) 操作，您可能可以使用Data.Sequence容器包或Data.Dequeue出队包。前者使用手指树，而后者使用 Okasaki 的Purely Functional Data Structures中的“Banker's Dequeue”（这里是在线的早期版本）。

于 2010-02-08T16:52:40.127 回答
6

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

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

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

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

于 2010-02-08T16:30:54.473 回答
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'
于 2010-02-10T02:42:22.843 回答