skew-list: 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.

Modules

[Index] [Quick Jump]

Downloads

• skew-list-0.1.tar.gz [browse] (Cabal source package)
• Package description (revised from the package)

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

• phadej

For package maintainers and hackage trustees

• edit package information

Candidates

• No Candidates