RList's merge operation is O(n)

[mfp]

The choice of 'a list as the exposed data type imposes slow O(n) patch application.
It'd be nice to have another module using another list-like data type (something similar to Okasaki's random access lists or such) which would allow for more efficient merging. Getting an 'a list back (which should be a rare event) would likely be O(n log n), but any operation (but taking the head) on the list would be O(n), so that's OK -- plus there wouldn't be hidden costs.

Alternatively, it could make sense not to update the current value eagerly, and to apply the patches lazily on request of the value (e.g. Tyxml_js works directly with the patch event, so there's no need to compute the actual list value in that case).

[vasilisp]

I agree that it would be a good idea to use another data structure.

The Tyxml_js use case is a bit tricky: while it listens to events, that fold only makes sense because of an initial Set (!(s.current)) pseudo-message. So values do come into the picture. Since we don't know when fold will be called, there must be a mutable list or some alternative, e.g., a list signal, or even an accumulator of messages that can be used for lazily reconstructing the list.

[vasilisp]

In fact, the merge operation takes O(n * k), where k is the patch length. The k is not necessarily small. It is the merge_p operation that takes O(n). We should at least constrain the patch format (by enforcing increasing indices) to allow for O(n) merging.

[joprice]

Would https://github.com/dbuenzli/pvec be a candidate for a more fitting data structure than list?