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'