The dlist-nonempty package

[ Tags: benchmark, bsd3, data, library ] [ Propose Tags ]

Difference lists are a list-like type supporting O(1) append. This is particularly useful for efficient logging and pretty printing (e.g. with the Writer monad), where list append quickly becomes too expensive.

DList a         ≅ [a] -> [a]
NonEmptyDList a ≅ [a] -> NonEmpty a

For empty variant, DList, see dlist package.


[Skip to Readme]

Properties

Versions 0.1, 0.1.1
Change log CHANGELOG.md
Dependencies base (>=4.5 && <4.11), base-compat (>=0.9.1 && <0.10), deepseq (>=1.1 && <2), dlist (==0.8.*), semigroupoids (>=5.1 && <5.3), semigroups (>=0.18.2 && <0.19) [details]
License BSD3
Copyright 2006-2009 Don Stewart, 2013-2016 Sean Leather, 2017 Oleg Grenrus
Author Don Stewart, Oleg Grenrus
Maintainer Oleg Grenrus <oleg.grenrus@iki.fi>
Category Data
Home page https://github.com/phadej/dlist-nonempty
Bug tracker https://github.com/phadej/dlist-nonempty/issues
Source repository head: git clone git://github.com/phadej/dlist-nonempty.git
Uploaded Mon Jul 31 09:47:58 UTC 2017 by phadej
Distributions LTSHaskell:0.1.1, NixOS:0.1.1, Stackage:0.1.1
Downloads 111 total (4 in the last 30 days)
Rating 0.0 (0 ratings) [clear rating]
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2017-07-31 [all 1 reports]
Hackage Matrix CI

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for dlist-nonempty-0.1.1

[back to package description]

Difference Lists in Haskell

The NonEmpty version of difference lists: list-like type supporting O(1) append ans snoc operations.

This is a fork of a dlist package.

benchmarking append 1000/List
time                 27.66 ms   (27.30 ms .. 28.01 ms)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 28.39 ms   (28.21 ms .. 28.58 ms)
std dev              391.5 μs   (311.7 μs .. 510.3 μs)

benchmarking append 1000/NonEmpty
time                 33.67 ms   (33.01 ms .. 34.27 ms)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 34.07 ms   (33.90 ms .. 34.29 ms)
std dev              419.3 μs   (308.9 μs .. 549.3 μs)

benchmarking append 1000/DList
time                 57.46 μs   (56.95 μs .. 58.12 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 57.98 μs   (57.61 μs .. 58.41 μs)
std dev              1.398 μs   (1.115 μs .. 1.871 μs)
variance introduced by outliers: 22% (moderately inflated)

benchmarking append 1000/NonEmptyDList
time                 90.37 μs   (89.09 μs .. 91.44 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 89.31 μs   (88.61 μs .. 89.96 μs)
std dev              2.244 μs   (1.763 μs .. 2.988 μs)
variance introduced by outliers: 22% (moderately inflated)