dlist: Difference 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]

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]

Properties

Versions0.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.6, 0.8.0.7
Change logChangeLog.md
Dependenciesbase (==4.*), deepseq (>=1.1 && <2) [details]
LicenseBSD-3-Clause
Copyright2006-2009 Don Stewart, 2013-2016 Sean Leather
AuthorDon Stewart
MaintainerSean Leather <sean.leather@gmail.com>
CategoryData
Home pagehttps://github.com/spl/dlist
Bug trackerhttps://github.com/spl/dlist/issues
Source repositoryhead: git clone git://github.com/spl/dlist.git
UploadedFri Mar 29 13:25:40 UTC 2019 by SeanLeather

Modules

[Index]

Downloads

Maintainers' corner

For package maintainers and hackage trustees


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.