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

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

Versions 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, 0.8.0.8, 1.0
Change log ChangeLog.md
Dependencies base (>=4 && <5), deepseq (>=1.1 && <1.5) [details]
License BSD-3-Clause
Copyright 2006-2009 Don Stewart, 2013-2019 Sean Leather
Author Don Stewart
Maintainer Sean Leather <sean.leather@gmail.com>
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 2020-04-02T03:34:54Z

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Readme for dlist-0.8.0.8

[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 list. 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.