Monadoc
The latest version of skew-list is 0.1-3.

skew-list

Version 0.1 revision 2 uploaded by phadej.

Package meta

Synopsis
Random access lists: skew binary
Description

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.

ConsingIndexing
Ordinary list, [a]O(1)O(n)
Binary list, RAList aO(log n)O(log n)
Vector, VectorO(n)O(1)
Sequence, SeqO(1)O(log n)
Skew binary list, SkewListO(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.

Author
Oleg Grenrus <oleg.grenrus@iki.fi>
Bug reports
https://github.com/phadej/skew-list/issues
Category
Data
Copyright
(c) 2022 Oleg Grenrus
Homepage
https://github.com/phadej/skew-list
Maintainer
Oleg.Grenrus <oleg.grenrus@iki.fi>
Package URL
n/a
Stability
n/a

Components