skew-list: Random access lists: skew binary

[ bsd3, data, library ] [ Propose Tags ]

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.

Downloads

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

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1
Change log ChangeLog.md
Dependencies base (>=4.12.0.0 && <4.21), deepseq (>=1.4.4.0 && <1.6), hashable (>=1.4.1.0 && <1.5), indexed-traversable (>=0.1.1 && <0.2), QuickCheck (>=2.14.2 && <2.16), strict (>=0.4.0.1 && <0.6) [details]
License BSD-3-Clause
Copyright (c) 2022 Oleg Grenrus
Author Oleg Grenrus <oleg.grenrus@iki.fi>
Maintainer Oleg.Grenrus <oleg.grenrus@iki.fi>
Revised Revision 3 made by phadej at 2024-06-15T13:27:26Z
Category Data
Home page https://github.com/phadej/skew-list
Bug tracker https://github.com/phadej/skew-list/issues
Source repo head: git clone https://github.com/phadej/skew-list.git
Uploaded by phadej at 2023-01-03T14:58:07Z
Distributions NixOS:0.1
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 78 total (11 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2023-01-03 [all 1 reports]