Random access lists: skew binary.
This package provides ordinary random access list, SkewList implemented using skew binary approach.
It's worth comparing to ordinary lists, binary random access list (as in ral package) and vectors (vector package) across two operations: indexing and consing.
| Consing | Indexing | |
Ordinary list, [a] | O(1) | O(n) |
Binary list, RAList a | O(log n) | O(log n) |
Vector, Vector | O(n) | O(1) |
Sequence, Seq | O(1) | O(log n) |
Skew binary list, SkewList | O(1) | O(log n) |
SkewList improves upon ordinary list, the cons operation is still constant time (though with higher constant factor), but indexing can be done in a logarithmic time.
Binary list cons is slower, as it might need to walk over whole log n sized structure.
Vector is the other end of trade-off spectrum: indexing is constant time operation, but consing a new element will need to copy whole spine.
Seq from Data.Sequence has similar (but amortized) complexity bounds for cons and index as SkewList. However (it seems) that indexing is quicker for SkewList in practice. Also SkewList has strict spine. On the other hand, Seq has quick append if you need that.
If you need both: fast consing and index, consider using SkewList.