skip-list: An implementation of pure skip lists

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

Skip lists provide efficient amortized indexing deep into lists by building an index that, essentially, converts the list into a balance binary tree. See the wikipedia entry on skip lists for more information.

[Skip to Readme]

Properties

Versions	0.1.0.0, 0.1.0.0, 0.1.0.1
Change log	CHANGES.md
Dependencies	base (>=4.7 && <5) [details]
License	MIT
Copyright	2017 Gregory Malecha
Author	Gregory Malecha
Maintainer	gmalecha@gmail.com
Category	Data
Home page	https://github.com/gmalecha/skip-list#readme
Source repo	head: git clone https://github.com/gmalecha/skip-list
Uploaded	by gmalecha at 2017-07-22T20:45:08Z

Modules

[Index]

Data
- Data.SkipList

Downloads

skip-list-0.1.0.0.tar.gz [browse] (Cabal source package)
Package description (as included in the package)

Maintainer's Corner

Package maintainers

gmalecha

For package maintainers and hackage trustees

edit package information

Readme for skip-list-0.1.0.0

[back to package description]

skip-list

Skip lists provide efficient amortized indexing deep into lists by building an index that, essentially, converts the list into a balance binary tree. See the wikipedia entry on skip lists for more information.

Performance

You can run the benchmarks using stack bench. The benchmark is the following:

let big = [0..1000] in
big == get (make big) <$> big

For lists (get = !! and make = id)

benchmarking all/!!
time                 864.6 μs   (858.1 μs .. 873.0 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 859.3 μs   (855.5 μs .. 864.3 μs)
std dev              14.76 μs   (11.86 μs .. 21.57 μs)

For SkipList (get = SL.lookup and make = SL.toSkipList 32)

benchmarking Quantities/SkipList<32>
time                 134.9 μs   (134.0 μs .. 135.7 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 134.0 μs   (133.6 μs .. 134.5 μs)
std dev              1.559 μs   (1.317 μs .. 1.958 μs)