O(1) circular buffer in haskell?

Question

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.

Claudeclaudel

If "crossing a certain border" when rotating takes O(N) time, what is the cost when it does not cross the border? If it's O(1) and you have only a 1/N probability of crossing the border, then rotating takes O(1) time on average. – Soupandfish

Right, but doing a sequential operation you are guaranteed that you will cross it at some point, and the time complexity is important for each rotation, since this will probably end up being a soft-realtime application. – Claudeclaudel

I've never used a circular buffer; is it easy to give a brief description of what your buffer is doing? In your application should it "overwrite" elements? – Kobe

forgot to add: have you considered whether you could exploit laziness to make a circular buffer structure unnecessary? – Kobe

I'm actually working with audio, and the idea is to iterate over a buffer of samples and transform them each time, as well as producing the current sample as output. I'm not sure how to exploit laziness for that process. – Claudeclaudel

Specifically, I need to be able to pass a buffer with the focus on a certain sample, mutate that sample, rotate the focus left in O(1), and rotate the focus right in O(1), all as individual operations. – Claudeclaudel

Answer 1

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?

Acknowledge

Answer 2

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).

Lovesick

Answer 3

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'

Kobe

See comment on original question for more specific functionality. – Claudeclaudel

Updated my answer, which I think gives you what you're looking for in a purely functional solution – Kobe

Incidentally, amortized O(1) is perfectly sensible--it just means that expensive operations may occur, but with a frequency inversely proportional to their cost. For instance, an operation might be O(1) most of the time and O(N) occasionally, but as long as the latter is no more common than once out of every N operations, the amortized complexity is still O(1). This is great for most purposes, but not so much for soft-realtime as per the comments on the question here... – Lovesick