Purely(ish) functional data structure with fast append and forward iteration 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)


Non-constraints:


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?
You're quite right that the "queue = two lists" approaches don't give you the running time you want when you have the ability to re-use earlier versions.  To get O(1) running time (amortized or worst case), you need a way to reverse the rear list and append it to the front list incrementally.  Instead of doing the reverse&amp;append all at once, taking O(N) time, you need to be able to do just a few steps of the reverse&amp;append every time you add a new element or remove/traverse through an element.

Hood and Melville showed one way to do this back in 1980.  For your purposes, their approach would be straightforward to adapt to C (with reference counting).  

In the early to mid 90's, I showed several ways to do this, some in O(1) worst-case time and some in O(1) amortized time. Most of these ways depended on lazy evaluation, which initially might seem hard to do in C, but in fact, there are only a very small of "shapes" needed for the lazy evaluation, each of which would be easy to represent using an ordinary node in C.

For example, a "Rotate" node has pointers to three sublists: L, R, and A.  Doing one step of the rotation replaces the "Rotate" node with an ordinary list node containing the head of L, and a pointer to a new Rotate node containing the tail of L, the tail of R, and the result of adding the head of R to the front of A.  Making this translation into explicit Rotate nodes instead of using generic lazy evaluation also means that you get O(1) worst-case bounds instead of O(1) amortized bounds.