O(1) circular buffer in haskell?

user_135888 0
Viewed 2729

I'm working on a small concept project in Haskell which requires a circular buffer. I've managed to create a buffer using arrays which has O(1) rotation, but of course requires O(N) for insertion/deletion. I've found an implementation using lists which appears to take O(1) for insertion and deletion, but since it maintains a left and right list, crossing a certain border when rotating will take O(N) time. In an imperative language, I could implement a doubly linked circular buffer with O(1) insertion, deletion, and rotation. I'm thinking this isn't possible in a purely functional language like Haskell, but I'd love to know if I'm wrong.

circular-buffer functional-programming haskell
3 Answers

If you can deal with amortized O(1) operations, you could probably use either Data.Sequence from the containers package, or Data.Dequeue from the dequeue package. The former uses finger trees, while the latter uses the "Banker's Dequeue" from Okasaki's Purely Functional Data Structures (a prior version online here).

user_1573600

The ST monad allows to describe and execute imperative algorithms in Haskell. You can use STRefs for the mutable pointers of your doubly linked list.

Self-contained algorithms described using ST are executed using runST. Different runST executions may not share ST data structures (STRef, STArray, ..).

If the algorithm is not "self contained" and the data structure is required to be maintained with IO operations performed in between its uses, you can use stToIO to access it in the IO monad.

Regarding whether this is purely functional or not - I guess it's not?

user_409160

It sounds like you might need something a bit more complicated than this (since you mentioned doubly-linked lists), but maybe this will help. This function acts like map over a mutable cyclic list:

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

Use like:

*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...]

And here's one that acts like mapAccumL:

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

Anyway, if you care to elaborate even more on what exactly your data structure needs to be able to "do" I would be really interested in hearing about it.

EDIT: as camccann mentioned, you can use Data.Sequence for this, which according to the docs should give you O1 time complexity (is there such a thing as O1 amortized time?) for viewing or adding elements both to the left and right sides of the sequence, as well as modifying the ends along the way. Whether this will have the performance you need, I'm not sure.

You can treat the "current location" as the left end of the Sequence. Here we shuttle back and forth along a sequence, producing an infinite list of values. Sorry if it doesn't compile, I don't have GHC at the moment:

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'
user_1768410
Related