I find I have need for a data structure with a specific set of requirements:
- It represents an immutable sequence of values (fixed sized integers if this matters)
- Appending a new value to the end (and returning a new sequence) needs to be extremely fast and memory efficient. Ideally amortised O(1) and sharing the entire prefix, but there's no specific hard complexity requirement and O(log(n)) would probably be OK too.
- Getting the length of a sequence needs to be cheap (obviously I can add this in after the fact with a wrapper if necessary)
- I need to be able to efficiently iterate the sequence in the forward direction
- I need to be able to lexicographically compare two sequences of the same length in the forward direction efficiently (this follows from the previous property, but might have simpler implementations and has fairly specific iteration patterns)
- Sharing of prefixes is very common in the expected workloads, so solutions like vlists or copy-on-append aren't practical because the workload will essentially always trigger a full copy.
- (practical rather than theoretical constraint but...) The simpler the design the better, because I'm almost certainly going to have to implement this from scratch in a couple of different languages, including C (with reference counting)
- Although the data structure itself has to represent immutable sequences, I don't mind a certain amount of mutation of the values if it's invisible (it would be nice to avoid)
- I certainly don't mind depending on e.g. some source of randomness
- It's OK if the forward iteration depends on some sort of external data structure with extra space requirements
Obviously the ideal would be to just have a length prefixed cons list, but the forward iteration requirement makes that sub-optimal.
The following are the two things I've considered so far:
- Just use a cons-list anyway and reverse it in an external buffer prior to iteration. Downsides: Forward iteration becomes fairly expensive, particularly for cases where I'm likely to stop the iteration after only one or two elements (which is a common case because of lexicographic comparison being a major use case here).
- A tree of bounded balance - it stores the size efficiently, has relatively cheap append and iteration. Downsides: Kinda fiddly to implement correctly, unclear whether the relatively high constant factors and the logarithmic complexity make it a win in practice.
- A skip list. Downsides: Same as the upsides really - it's about halfway between the previous two in terms of complexity and performance. Requires more book-keeping for iteration than the others, but it's probably tolerable.
So of the three the skip list looks like it might be the best option and "just use a cons list and optimise later" looks like the one I'm most likely to start with, but I'm not exactly well versed in the purely functional data structure literature, so I was hoping there were a better option I was overlooking. Any suggestions?