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]

Flags

Manual Flags

NameDescriptionDefault
semigroupoids

Build with semigroupoids dependency

Enabled

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

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.20), deepseq (>=1.3 && <1.6), dlist (>=1.0 && <1.1), foldable1-classes-compat (>=0.1 && <0.2), semigroupoids (>=5.1 && <6.1), 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 1 made by phadej at 2023-10-26T10:36:18Z
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 2023-04-12T14:22:19Z
Distributions LTSHaskell:0.1.3, NixOS:0.1.3, Stackage:0.1.3
Reverse Dependencies 2 direct, 0 indirect [details]
Downloads 2572 total (19 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for dlist-nonempty-0.1.3

[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 right-append/List
time                 13.63 ms   (13.36 ms .. 14.04 ms)
                     0.997 R²   (0.994 R² .. 0.999 R²)
mean                 13.60 ms   (13.49 ms .. 13.76 ms)
std dev              332.4 μs   (240.8 μs .. 409.5 μs)

benchmarking right-append/NonEmpty
time                 31.87 ms   (25.83 ms .. 35.97 ms)
                     0.927 R²   (0.890 R² .. 0.969 R²)
mean                 23.76 ms   (21.98 ms .. 26.23 ms)
std dev              4.648 ms   (3.053 ms .. 5.538 ms)
variance introduced by outliers: 78% (severely inflated)

benchmarking right-append/DList
time                 38.18 μs   (38.09 μs .. 38.32 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 38.18 μs   (38.03 μs .. 38.46 μs)
std dev              667.8 ns   (325.0 ns .. 1.164 μs)
variance introduced by outliers: 13% (moderately inflated)

benchmarking right-append/NonEmptyDList
time                 33.58 μs   (33.30 μs .. 33.89 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 33.86 μs   (33.67 μs .. 34.14 μs)
std dev              801.9 ns   (616.6 ns .. 1.240 μs)
variance introduced by outliers: 22% (moderately inflated)

benchmarking right-append/DNonEmpty
time                 79.79 μs   (79.60 μs .. 80.10 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 80.52 μs   (80.23 μs .. 80.92 μs)
std dev              1.162 μs   (757.0 ns .. 1.795 μs)