dlist-nonempty: Non-empty difference lists

[ 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]

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, 0.1.1, 0.1.2, 0.1.3
Change log CHANGELOG.md
Dependencies base (>=4.5 && <4.18), base-compat (>=0.9.1 && <0.13), deepseq (>=1.1 && <2), dlist (>=0.8 && <1.1), semigroupoids (>=5.1 && <5.4), semigroups (>=0.18.2 && <0.21) [details]
License BSD-3-Clause
Copyright 2006-2009 Don Stewart, 2013-2016 Sean Leather, 2017 Oleg Grenrus
Author Don Stewart, Oleg Grenrus
Maintainer Oleg Grenrus <oleg.grenrus@iki.fi>
Revised Revision 13 made by phadej at 2022-08-23T14:25:09Z
Category Data
Home page https://github.com/phadej/dlist-nonempty
Bug tracker https://github.com/phadej/dlist-nonempty/issues
Source repo head: git clone git://github.com/phadej/dlist-nonempty.git
Uploaded by phadej at 2017-07-31T09:47:58Z
Distributions LTSHaskell:0.1.3, NixOS:0.1.3, Stackage:0.1.3
Reverse Dependencies 2 direct, 0 indirect [details]
Downloads 2590 total (20 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2017-07-31 [all 1 reports]

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)