dlist: 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.


[Skip to Readme]

Modules

[Index] [Quick Jump]

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

Versions [RSS] 0.2, 0.3, 0.3.1, 0.3.2, 0.4, 0.4.1, 0.5, 0.6, 0.6.0.1, 0.7, 0.7.0.1, 0.7.1, 0.7.1.1, 0.7.1.2, 0.8, 0.8.0.1, 0.8.0.2, 0.8.0.3, 0.8.0.4, 0.8.0.5, 0.8.0.6, 0.8.0.7, 0.8.0.8, 1.0
Change log ChangeLog.md
Dependencies base (>=4 && <4.13), deepseq (>=1.1 && <2) [details]
License BSD-3-Clause
Copyright 2006-2009 Don Stewart, 2013-2016 Sean Leather
Author Don Stewart
Maintainer Sean Leather <sean.leather@gmail.com>
Revised Revision 1 made by phadej at 2019-05-10T19:10:24Z
Category Data
Home page https://github.com/spl/dlist
Bug tracker https://github.com/spl/dlist/issues
Source repo head: git clone git://github.com/spl/dlist.git
Uploaded by SeanLeather at 2019-03-29T13:30:41Z
Distributions Arch:1.0, Debian:0.8.0.8, Fedora:1.0, FreeBSD:0.7.1.1, LTSHaskell:1.0, NixOS:1.0, Stackage:1.0, openSUSE:1.0
Reverse Dependencies 228 direct, 14411 indirect [details]
Downloads 413152 total (302 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2019-03-29 [all 1 reports]

Readme for dlist-0.8.0.6

[back to package description]

Difference Lists in Haskell

Hackage Hackage dependencies Travis CI

Summary

The Haskell dlist package defines a list-like type supporting O(1) append and snoc operations.

See ChangeLog.md for recent changes.

References

Research

  1. A novel representation of lists and its application to the function “reverse.” John Hughes. Information Processing Letters. Volume 22, Issue 3. 1986-03. Pages 141-144. [PDF]

    This is the original source for a representation of lists as first-class functions.

Basic Introduction

  1. Difference list. Wikipedia.

  2. Difference lists. Haskell.org Wiki.

  3. What is a DList?. Stack Overflow.

Blogs and Discussion

  1. Using Difference Lists. Douglas M. Auclair. 2008-08-13.

  2. A Sort of Difference. Edward Kmett. 2008-09-18.

  3. Reference for technique wanted. Richard O'Keefe, et al. 2010-10-31.

  4. 24 Days of Hackage: dlist. Oliver Charles. 2012-12-14.

  5. Constructing a list in a Monad. Joachim Breitner. 2013-11-13.

  6. Demystifying DList. (On Reddit). Tom Ellis. 2014-01-24.

  7. keepEquals with Difference Lists, Douglas M. Auclair. 2014-06-21.

Books

  1. Chapter 13. Data Structures. Real World Haskell. 2008-12-05.