An implementation of purely functional double-ended queues

Hi everyone.

I have some code that might be useful to others here. I had the idea of a new purely functional implementation for double ended queues, and I implemented it (GitHub - hummy123/bro-deque)[here].

The idea is pretty simple, and it proves to be quite fast in benchmarks.

The idea is to have a record containing:

  • A head array representing the start of the queue, with a limit on the number of elements it can have.
  • A tail array representing the end of the queue, also with a limit on the number of elements it can have.
  • A balanced binary tree based on the rope data structure. (The internal nodes pointing to other nodes contain integer metadata indicating the number of elements on the left and right subtrees, and leaf nodes contain an array of elements.)

When trying to insert into either the head or tail array when the array is at max capacity, the array is either appended or prepended to the tree and the array/element we wanted to insert is now either the head or tail.

I was looking for some way to test the performance and adapted (this code)[Ocaml speed : recursive function optimization - #3 by sanette] to use it, and it’s pretty fast - only about 4x slower than the standard library’s mutable queue. (Although this was really implemented in mind aiming for fast access time rather than fast insertion/removal time.)

It has some non-standard functions for double ended queues too, like O(log n) insert/removal/indexing at any arbitrary location (with a constant that makes this faster than on a typical binary tree - a typical binary tree contains on element per node, increasing height, but this contains arrays of elements at the leaves so more data is packed and the height is shorter).

Some other people might find it useful, so here it is for others to copy-and-paste. I don’t know if it’s worth putting on opam (I don’t have a use for this myself in any of my projects but curiosity led me to implement it.)