@hackage skew-list0.1
Random access lists: skew binary
Categories
License
BSD-3-Clause
Maintainer
Oleg.Grenrus <oleg.grenrus@iki.fi>
Links
Versions
- 0.1 Fri, 2 May 2025
Installation
Tested Compilers
Dependencies (6)
- QuickCheck ^>=2.14.2 || ^>=2.15
- base >=4.12.0.0 && <4.22
- deepseq >=1.4.4.0 && <1.6
- hashable ^>=1.4.1.0 || ^>=1.5.0.0
- indexed-traversable ^>=0.1.1
- strict ^>=0.4.0.1 || ^>=0.5 Show all…
Dependents (2)
@hackage/debruijn, @hackage/data-debruijn
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.