Purely functional (persistent) ring buffer

Question

I would like to implement a ring buffer using purely functional data structure with the following operations

• Efficient random access by index
• Add to front
• Remove from back

The reason for using persistent data structure is because I have one writer thread and several reader thread and I want to avoid the readers blocking the writer.

This can be done easily by having readers thread only hold the lock while taking a snapshot and then using the snapshot for processing.

What are the existing available data structure that support those operation?

• Doubly-linked list can't do index lookup efficiently and are O(n)
• Clojure PersistentVector based on Phil Bagwell Ideal Hash Tree, support access by index in log32N and subvec can be used to remove element from the start.
• Hash array mapped trie could also be used by storing integer as key but might not be super efficient.

Which other purely functional data structure could be used in this case?

Answer 1

The finger tree (in the standard library as Data.Sequence) is the go-to for persistent random-access sequences. I think it satisfies your criteria––random access indexing is O(log n) (more specifically, the log of the index's distance from the edge), the others are O(1). I'm not aware of any persistent data structures that do better than that.