Thanks to the FSharpx team I had the opportunity to add double-ended queues to FSharpx.Core. Think of double-ended queues, or deques (Okasaki’s spelling, which I like), as lists that work in both directions. They have mirror image values to the familiar
init, and a value doing the mirror image operation of
cons spelled backwards). Imagine the possibilities of
list when you can also add and remove elements on the end. For instance use pattern matching on
match q with
| Cons(hd, Snoc(mid, lst)) -> hd, mid, lst //first, middle, and last
| _ -> ...
Which deque is right for you?
The four deques available in FSharpx.Core implement the following signature
Cons : 'a -> IDeque<'a>
Head : unit -> 'a
Init : unit -> IDeque<'a>
IsEmpty : unit -> bool
Last : unit -> 'a
Length : unit -> int
Snoc : 'a -> IDeque<'a>
Tail : unit -> IDeque<'a>
Uncons : unit -> 'a * IDeque<'a>
Unsnoc : unit -> IDeque<'a> * 'a
They also all have a module level value of
OfCatLists which concatenates two lists to create a deque. Deques internally implement two lists (or lazy lists) with the second list reversed. That’s basically all there is to allowing concatenations at both ends. (For in depth discussion of double-ended queues see either Okasaki’s thesis or his book.) This makes the
OfCatLists operation a very fast way to concatenate two lists. Across all four deque implementations the operation is competitive with the FSharpx data structure
DList (Difference List) which implements an
append value that is truly O(1).
OfCatLists is not truly O(1), but two of the deque structures,
BatchedDeque, actually out-perform
DList right through a scale of concatenating 10,000 element lists with
DList only barely out-performing them at 100,000. (To be sure we are talking time scales of less than 0.3 milliseconds on a 64-bit system.)
RealTimeDeque implement additional values
Lookup : int -> BankersDeque<'a>
Remove : int -> BankersDeque<'a>
TryRemove : int -> BankersDeque<'a> option
Rev : unit -> BankersDeque<'a>
Update : int -> 'a -> BankersDeque<'a> option
TryUpdate : int -> 'a -> BankersDeque<'a> option
Rev is always O(1), a nice feature of deques.
Although nowhere near as adept at the
update operation as the
AltBinaryRandomAccessList data structure (specifically designed for update), deques exhibit good across the board performance in the index enabled operations
Update. They have a theoretical worst case time complexity of ~O(n/2) on index operations because the elements are partitioned in two lists.
But watch out! The actual time complexity on index operations is O(d), where “d” is the displacement into the internal list containing the indexed element. The relative sizes of the internal lists can vary.
RealTimeDeque require a “front-back stream ratio constant” in their construction. I’ve implemented a default value of 2 where this is required, but you can also specify a higher value. Essentially it insures neither list is ever larger than a constant times the size of the other list.
BatchedDeque does nothing with the relative sizes until you request a
Init, then it brings the lists into a relation of neither being more than twice the size of the other. And finally
Deque is a naive implementation that does not regulate the relative sizes at all.
They all implement
IEnumerable and have available all the
Seq module values, but be sure to always use the native
Lookup and not
Seq.nth. This is one of those cases where straight-up comparisons of time complexity (~O(n/4) versus O(n) over many random iterations) does not tell the whole performance story. Actual
Seq.nth performance is much worse than the time complexity would suggest.
So, which deque is right for your purposes? As is always the case with complexity that makes reasoning about performance hard, do your own profiling!