Add docs for containers package.
authorMatt Renaud <matt@m-renaud.com>
Fri, 29 Dec 2017 02:19:26 +0000 (18:19 -0800)
committerDavid Feuer <David.Feuer@gmail.com>
Tue, 9 Jan 2018 05:03:46 +0000 (00:03 -0500)
- Configuration for ReadTheDocs
- Introduction to the containers package
- API and usage docs for Set, IntSat, Map, IntMap, and Sequence

[ci skip]

15 files changed:
CONTRIBUTING.md
README.md
containers.cabal
docs/.gitignore [new file with mode: 0644]
docs/Makefile [new file with mode: 0644]
docs/_extensions/HaddockAutolinker.py [new file with mode: 0644]
docs/_extensions/haddock-autolink.py [new file with mode: 0644]
docs/_static/images/haskell-logo-black.svg [new file with mode: 0644]
docs/conf.py [new file with mode: 0644]
docs/index.rst [new file with mode: 0644]
docs/intro.rst [new file with mode: 0644]
docs/make.bat [new file with mode: 0644]
docs/map.rst [new file with mode: 0644]
docs/sequence.rst [new file with mode: 0644]
docs/set.rst [new file with mode: 0644]

index 77fc257..16d74d9 100644 (file)
@@ -72,3 +72,13 @@ When you send a pull request, please:
 - Update the change log for non-trivial changes.
 
 - Let us know how you wish to be credited in the changelog.
+
+## Docs
+
+The internal docs are generated using Haddock which can be invoked with `cabal
+haddock` or `stack haddock`.
+
+The external docs are served by ReadTheDocs at
+https://haskell-containers.readthedocs.io and live in the `docs/` directory. To
+build the docs locally run `pip install sphinx sphinx-autobuild` to install the
+dependencies and then `cd docs/ && make html`.
\ No newline at end of file
index 67bb0ce..afcb993 100644 (file)
--- a/README.md
+++ b/README.md
@@ -1,7 +1,11 @@
 The `containers` Package [![Build Status](https://travis-ci.org/haskell/containers.svg?branch=master)](https://travis-ci.org/haskell/containers)
 ========================
 
-See [`containers` on Hackage](http://hackage.haskell.org/package/containers) for more information.
+For a walkthrough of what this package provides with examples of common
+operations see the [containers introduction](https://haskell-containers.readthedocs.io).
+
+See [`containers` on Hackage](http://hackage.haskell.org/package/containers) for
+full API documentation.
 
 
 Contributing
index 19e670f..1cb3d29 100644 (file)
@@ -7,10 +7,18 @@ bug-reports: https://github.com/haskell/containers/issues
 synopsis: Assorted concrete container types
 category: Data Structures
 description:
+    .
     This package contains efficient general-purpose implementations
-    of various basic immutable container types.  The declared cost of
-    each operation is either worst-case or amortized, but remains
-    valid even if structures are shared.
+    of various immutable container types including sets, maps, sequences,
+    trees, and graphs.
+    .
+    For a walkthrough of what this package provides with examples of common
+    operations see the [containers
+    introduction](https://haskell-containers.readthedocs.io).
+    .
+    The declared cost of each operation is either worst-case or amortized, but
+    remains valid even if structures are shared.
+
 build-type: Simple
 cabal-version:  >=1.8
 extra-source-files:
diff --git a/docs/.gitignore b/docs/.gitignore
new file mode 100644 (file)
index 0000000..ddac952
--- /dev/null
@@ -0,0 +1,2 @@
+_build/*
+_extensions/*.pyc
diff --git a/docs/Makefile b/docs/Makefile
new file mode 100644 (file)
index 0000000..c96474a
--- /dev/null
@@ -0,0 +1,20 @@
+# Minimal makefile for Sphinx documentation
+#
+
+# You can set these variables from the command line.
+SPHINXOPTS    = -a -E
+SPHINXBUILD   = sphinx-build
+SPHINXPROJ    = containers
+SOURCEDIR     = .
+BUILDDIR      = _build
+
+# Put it first so that "make" without argument is like "make help".
+help:
+       @$(SPHINXBUILD) -M help "$(SOURCEDIR)" "$(BUILDDIR)" $(SPHINXOPTS) $(O)
+
+.PHONY: help Makefile
+
+# Catch-all target: route all unknown targets to Sphinx using the new
+# "make mode" option.  $(O) is meant as a shortcut for $(SPHINXOPTS).
+%: Makefile
+       @$(SPHINXBUILD) -M $@ "$(SOURCEDIR)" "$(BUILDDIR)" $(SPHINXOPTS) $(O)
diff --git a/docs/_extensions/HaddockAutolinker.py b/docs/_extensions/HaddockAutolinker.py
new file mode 100644 (file)
index 0000000..91f3b65
--- /dev/null
@@ -0,0 +1,211 @@
+from docutils import nodes
+import itertools
+import string
+
+### Utility functions.
+
+def get_project(inliner):
+    """
+    Returns the project name associated with the file being processed.
+    """
+    return inliner.document.settings.env.app.config.project
+
+
+def convert_special_chars_to_ascii(func_name):
+    """
+    If func_name is an operator, convert it to its ascii representation.
+
+    This is how Haddock generates links for operators.
+
+    '!?' => '-33--63-'
+    """
+    if func_name == None:
+        return None
+
+    escaped_func_name = [ c if c not in string.punctuation else '-' + str(ord(c)) + '-'
+                          for c in func_name ]
+
+    return ''.join(escaped_func_name)
+
+
+def parse_haddock_ref_text(text):
+    """
+    Parses text of the form pkg-name/Module.Path#func_name into the tuple
+    (package, module, function_name).
+
+    The module and function name are optional, if they are omitted then 'None'
+    will be returned in the corresponding tuple element.
+
+    TODO(m-renaud): Clean this up, there's probably a python parsing library.
+    """
+
+    # If there's no '/' then this is either a reference to a package or a local
+    # reference.
+    if '/' not in text:
+        if '#' not in text:
+            return (text, None, None)
+        else:
+            module,func_name = text.split('#')
+            return (None, module, func_name)
+
+    pkg_name,rest = text.split('/')
+
+    func_name = None
+    module = None
+    if '#' in rest:
+        module,func_name = rest.split('#')
+    else:
+        module = rest
+
+    return (pkg_name, module, func_name)
+
+
+
+### Link generation functions.
+
+def pkg_root_ref(haddock_host, haddock_root, pkg):
+    """
+    Returns the URI for the root of pkg's Haddocks.
+
+    Note: Hackage uses a different URI scheme than stackage and local.
+
+    URI enclosed in {} corresponds to 'haddock_root'.
+
+    Hackage: {hackage.haskell.org/package/}<pkg_name>
+    Stackage: {www.stackage.org/haddock/<resolver>/}<pkg_name>/index.html
+    Local: {file:///path/to/html/}<pkg_name>/index.html
+    """
+
+    if haddock_host == 'hackage':
+        return haddock_root + pkg
+
+    if haddock_host == 'stackage':
+        return haddock_root + pkg + '/index.html'
+
+    if haddock_host == 'local':
+        return haddock_root + pkg + '/index.html'
+
+
+def module_ref(haddock_host, haddock_root, pkg, module, func_name):
+    """
+    Returns the URI referring to pkg/module#func_name.
+
+    Note: Hackage uses a different URI scheme than stackage and local.
+
+    URI enclosed in {} corresponds to 'haddock_root'.
+
+    Hackage: {hackage.haskell.org/package/}<pkg_name>/docs/<module>.html#v:<func_name>
+    Stackage: {www.stackage.org/haddock/<resolver>/}<pkg_name>/<module>.html#t:<func_name>
+    Local: {file:///path/to/html/}<pkg_name>/<module>.html#t:<func_name>
+    """
+
+    if module != None:
+        module = module.replace('.', '-')
+
+    if haddock_host == 'hackage':
+        ref = haddock_root + pkg + '/docs/' + module + '.html'
+
+    if haddock_host == 'stackage':
+        ref = haddock_root + pkg + '/' + module + '.html'
+
+    if haddock_host == 'local':
+        ref = haddock_root + pkg + '/' + module + '.html'
+
+    # If a function name was provided, link to it.
+    if func_name != None:
+        # Select the correct anchor, types use #t, functions use #v.
+        if func_name[0].isupper():
+            anchor_type = '#t:'
+        else:
+            anchor_type = '#v:'
+        ref = ref + anchor_type + func_name
+
+    return ref
+
+
+def haddock_ref(haddock_host, haddock_root, pkg, module, func_name):
+    """
+    Return a reference link to Haddocks for pkg/module#func_name.
+    """
+
+    if module == None and func_name == None:
+        return pkg_root_ref(haddock_host, haddock_root, pkg)
+    else:
+        func_name = convert_special_chars_to_ascii(func_name)
+        return module_ref(haddock_host, haddock_root, pkg, module, func_name)
+
+
+
+#############################################
+# -- Custom roles for linking to Hackage docs
+#############################################
+
+# Support building docs with link to hackage, stackage, or locally build haddocks.
+# Valid options:
+#   hackage - link to hackage.haskell.org
+#   stackage - link to www.stackage.org (must also pass STACKAGE_RESOLVER)
+#   local - any path to local docs (must also set HADDOCK_DIR)
+#
+# Note: Defaults to hackage if none specified.
+#
+# Note: We need to do some custom URL rewriting for stackage because it uses a different
+# format from what the haddock tool builds
+#
+# TODO(m-renaud): Improve this and publish as sphinx extension.
+
+### URI scheme examples for Hackage, Stackage, and local docs.
+## Packages
+# Hackage: hackage.haskell.org/package/containers
+# Stackage: www.stackage.org/haddock/lts-10.0/containers/index.html
+# Local: file:///local/path/html/containers/index.html
+
+## Module (and function) references
+# Hackage: hackage.haskell.org/package/containers/docs/Data.Set.html#v:empty
+# Stackage: www.stackage.org/haddock/lts-10.0/containers/Data.Set.html#t:empty
+# Local: file:///path/to/html/containers/Data.Set.html#t:empty
+
+class HaddockAutolinker:
+
+    def __init__(self, app, haddock_host, haddock_root):
+        self.haddock_host = haddock_host
+        self.haddock_root = haddock_root
+
+
+    def haddock_role(self, display_name_only=False):
+        def haddock_role_impl(name, rawtext, text, lineno, inliner, options={}, content=[]):
+            """
+            Role handler for :haddock:.
+            """
+
+            (pkg, module, func_name) = parse_haddock_ref_text(text)
+
+            # If the pkg isn't set then this is a reference to a function in the current
+            # package.
+            if pkg == None:
+                pkg = get_project(inliner)
+            ref = haddock_ref(self.haddock_host, self.haddock_root, pkg, module, func_name)
+
+            if ref == None:
+                FAIL = '\033[91m'
+                ENDC = '\033[0m'
+                print FAIL
+                print 'ERROR: invalid argument to :' + name + ':'
+                print 'Markup: ' + str(rawtext)
+                print 'Line: ' + str(lineno)
+                print ENDC
+                raise Exception('Invalid Haddock link, see ERROR above.')
+
+            if module == None:
+                link_text = pkg
+            else:
+                if func_name == None:
+                    link_text = module
+                else:
+                    if display_name_only:
+                        link_text = func_name
+                    else:
+                        link_text = module + '#' + func_name
+
+            node = nodes.reference(rawtext, link_text, refuri=ref, **options)
+            return [node], []
+        return haddock_role_impl
diff --git a/docs/_extensions/haddock-autolink.py b/docs/_extensions/haddock-autolink.py
new file mode 100644 (file)
index 0000000..1a5d710
--- /dev/null
@@ -0,0 +1,50 @@
+from docutils import nodes
+from HaddockAutolinker import (HaddockAutolinker, haddock_ref)
+import os
+
+
+def setup(app):
+    haddock_host = os.getenv('HADDOCK_HOST', 'hackage')
+
+    # Hackage hosting
+    if haddock_host == 'hackage':
+        haddock_root = 'https://hackage.haskell.org/package/'
+
+    # Stackage hosting
+    elif haddock_host == 'stackage':
+        stackage_resolver = os.getenv('STACKAGE_RESOLVER', None)
+        if stackage_resolver != None:
+            haddock_root = 'https://www.stackage.org/haddock/' + stackage_resolver + '/'
+        else:
+            raise Exception("Must specify STACKAGE_RESOLVER when setting HADDOCK_HOST=stackage")
+
+    # Local hosting
+    elif haddock_host == 'local':
+        haddock_dir = os.getenv('HADDOCK_DIR', None)
+        if haddock_dir != None:
+            haddock_root = haddock_dir
+        else:
+            raise Exception("Must specify HADDOCK_DIR when setting HADDOCK_HOST=local")
+
+    else:
+        raise Exception("HADDOCK_HOST not recognized, valid options: hackage, stackage, local")
+
+    # These custom roles allow you to easily link to Haddock documentation using
+    # :role_name:`function_name`.
+    #
+    # For example:
+    #   :set:`insert` will create a link to
+    #   https://hackage.haskell.org/package/containers-0.5.10.2/docs/Data-Set.html#v:insert
+    autolinker = HaddockAutolinker(app, haddock_host, haddock_root)
+
+    app.add_role('haddock', autolinker.haddock_role())
+    app.add_role('haddock_short', autolinker.haddock_role(True))
+
+
+    print '\nHaddock host information'
+    print '  haddoc_host: ' + haddock_host
+    print '  haddock_root: ' + haddock_root
+    print
+    print '  Links to docs will be of the form: ' + \
+        haddock_ref(haddock_host, haddock_root, 'pkg-name', 'Module-Name', 'funcName')
+
diff --git a/docs/_static/images/haskell-logo-black.svg b/docs/_static/images/haskell-logo-black.svg
new file mode 100644 (file)
index 0000000..f65315f
--- /dev/null
@@ -0,0 +1,17 @@
+<svg width="520" height="400" xmlns="http://www.w3.org/2000/svg" preserveAspectRatio="xMidYMid meet">
+ <metadata>Created by potrace 1.15, written by Peter Selinger 2001-2017</metadata>
+
+ <g>
+  <title>background</title>
+  <rect fill="none" id="canvas_background" height="402" width="522" y="-1" x="-1"/>
+ </g>
+ <g>
+  <title>Layer 1</title>
+  <g id="svg_1" fill="#000000" transform="translate(0,512) scale(0.10000000149011612,-0.10000000149011612) ">
+   <path id="svg_2" d="m10,4896.689087c0,-5 269,-412 599,-906l598,-898l-598,-897c-330,-493 -599,-901 -599,-907c0,-7 158,-9 458,-7l459,2l602,904l603,904l-604,905l-603,906l-457,1c-252,0 -458,-3 -458,-7z"/>
+   <path id="svg_3" d="m1210,4898.689087c0,-4 270,-411 600,-905l600,-900l-600,-900c-330,-495 -600,-902 -600,-905c0,-3 207,-5 460,-5l459,0l367,550c201,303 369,552 374,555c4,2 173,-245 376,-550l369,-554l458,-1c251,0 457,3 457,7c0,5 -541,819 -1202,1810l-1201,1803l-459,0c-252,0 -458,-2 -458,-5z"/>
+   <path id="svg_4" d="m3127,3822.689087c11,-16 103,-155 204,-309l184,-279l808,0l807,-1l0,310l0,310l-1011,0l-1011,0l19,-31z"/>
+   <path id="svg_5" d="m3722,2938.689087c2,-8 91,-147 198,-309l195,-295l508,0l507,-1l0,310l0,310l-706,0c-621,0 -705,-2 -702,-15z"/>
+  </g>
+ </g>
+</svg>
diff --git a/docs/conf.py b/docs/conf.py
new file mode 100644 (file)
index 0000000..53001fa
--- /dev/null
@@ -0,0 +1,99 @@
+# -*- coding: utf-8 -*-
+#
+
+from docutils.parsers.rst import roles
+from docutils import nodes
+import itertools
+import string
+import os
+import sphinx_rtd_theme
+import sys
+
+
+# -- General configuration ------------------------------------------------
+
+# Add the _extenions dir to the search path.
+sys.path.insert(0, os.path.abspath('.') + '/_extensions')
+
+extensions = ['sphinx.ext.intersphinx',
+              'sphinx.ext.ifconfig',
+              'haddock-autolink']
+
+templates_path = ['_templates']
+
+source_suffix = '.rst'
+
+master_doc = 'index'
+
+# General information about the project.
+project = u'containers'
+copyright = u'2017, Matt Renaud'
+author = u'Matt Renaud'
+
+# The short X.Y version.
+version = u'0.5.10'
+# The full version, including alpha/beta/rc tags.
+release = u'0.5.10.2'
+
+# The language for content autogenerated by Sphinx. Refer to documentation
+# for a list of supported languages.
+language = None
+
+# List of patterns, relative to source directory, that match files and
+# directories to ignore when looking for source files.
+# This patterns also effect to html_static_path and html_extra_path
+exclude_patterns = ['_build', 'Thumbs.db', '.DS_Store']
+
+# The name of the Pygments (syntax highlighting) style to use.
+pygments_style = 'sphinx'
+
+# If true, `todo` and `todoList` produce output, else they produce nothing.
+todo_include_todos = False
+
+
+# -- Options for HTML output ----------------------------------------------
+
+# on_rtd is whether we are on readthedocs.org, this line of code grabbed from docs.readthedocs.org
+on_rtd = os.environ.get('READTHEDOCS', None) == 'True'
+
+# The theme to use for HTML and HTML Help pages.  See the documentation for
+# a list of builtin themes.
+#
+if not on_rtd:  # only import and set the theme if we're building docs locally
+    import sphinx_rtd_theme
+    html_theme = 'sphinx_rtd_theme'
+    html_theme_path = [sphinx_rtd_theme.get_html_theme_path()]
+
+# Theme options are theme-specific and customize the look and feel of a theme
+# further.  For a list of options available for each theme, see the
+# documentation.
+#
+# html_theme_options = {}
+
+# Add any paths that contain custom static files (such as style sheets) here,
+# relative to this directory. They are copied after the builtin static files,
+# so a file named "default.css" will overwrite the builtin "default.css".
+html_logo = '_static/images/haskell-logo-black.svg'
+html_static_path = ['_static']
+html_context = {
+    'source_url_prefix': "https://github.com/haskell/containers/tree/master/docs/",
+    "display_github": True,
+    "github_host": "github.com",
+    "github_user": "haskell",
+    "github_repo": 'containers',
+    "github_version": "master/",
+    "conf_py_path": "docs/",
+    "source_suffix": '.rst',
+}
+
+# Custom sidebar templates, must be a dictionary that maps document names
+# to template names.
+#
+# This is required for the alabaster theme
+# refs: http://alabaster.readthedocs.io/en/latest/installation.html#sidebars
+html_sidebars = {
+    '**': [
+        'relations.html',  # needs 'show_related': True theme option to display
+        'searchbox.html',
+    ]
+}
diff --git a/docs/index.rst b/docs/index.rst
new file mode 100644 (file)
index 0000000..8595bf7
--- /dev/null
@@ -0,0 +1,12 @@
+Haskell ``containers`` package
+==============================
+
+For full API documentation see the :haddock:`containers` Haddocks.
+
+.. toctree::
+   :maxdepth: 2
+
+   intro
+   set
+   map
+   sequence
diff --git a/docs/intro.rst b/docs/intro.rst
new file mode 100644 (file)
index 0000000..32ae191
--- /dev/null
@@ -0,0 +1,111 @@
+Introduction
+============
+
+The ``containers`` package provides implementations of various immutable data
+structures.
+
+Some of the data structures provided by this package have a very large API
+surface (for better or worse). The docs here focus on the most common functions
+which should be more than enough to get you started. Once you know the basics,
+or if you're looking for a specific function, you can head over to the
+:haddock:`containers` Haddocks to check out the full API documentation!
+
+Provided Data Structures
+------------------------
+
+- :doc:`set`: ordered, non-duplicated elements
+- :doc:`map`: ordered maps from keys to values (aka. dictionaries)
+- :doc:`sequence`: finite sequence of elements, an efficient alternative to list
+
+.. NOTE::
+   You'll need ``containers >= 0.5.9`` for a few of the examples. See
+   `Version Requirements`_ for info on how to check which version you have and
+   how to upgrade.
+
+
+Related Packages
+----------------
+
+- :haddock:`unordered-containers` - containers using hashing instead of
+  ordering.
+
+- :haddock:`array` - mutable and immutable arrays.
+
+- :haddock:`vector` - efficient ``Int``-indexed arrays (boxed and unboxed).
+
+- :haddock:`bytestring` - compact, immutable bytestrings, useful for binary and
+  8-bit character data.
+
+- :haddock:`dlist` - difference lists with *O(1)* append, useful for efficient
+  logging and pretty printing.
+
+- :haddock:`hashtables` - mutable hash tables in the ST monad.
+
+
+Looking for more resources?
+---------------------------
+
+If you've worked your way through the documentation here and you're looking for
+more examples or tutorials you should check out:
+
+- `haskell-lang.org's containers tutorial
+  <https://haskell-lang.org/library/containers>`_
+- `Learn You a Haskell "Modules" chapter <http://learnyouahaskell.com/modules>`_
+
+.. _installing:
+
+Installing and using the ``containers`` package
+-----------------------------------------------
+
+Version Requirements
+^^^^^^^^^^^^^^^^^^^^
+
+For some of the examples you'll need ``containers >= 0.5.9`` which ships with
+``GHC >= 8.2``. You can check to see which version you have installed with:
+
+::
+
+    ghc --version
+    > The Glorious Glasgow Haskell Compilation System, version 8.2.2
+
+If you have an older version, don't worry about it, the majority of the code
+works with older versions of the package. If you want, you can get a recent
+version by `from haskell.org <https://www.haskell.org/downloads>`_, or with
+`Stack <https://www.haskellstack.org>`_ using ``stack --resolver lts-10.2
+ghci``.
+
+
+Importing modules
+^^^^^^^^^^^^^^^^^
+
+All of the modules in ``containers`` should be imported ``qualified`` since they
+use names that conflict with the standard Prelude.
+
+::
+
+    import qualified Data.Set as Set
+    import qualified Data.Map.Strict as Map
+    import qualified Data.Sequence as Seq
+
+
+In GHCi
+^^^^^^^
+
+Start the GHCi `REPL
+<https://en.wikipedia.org/wiki/Read%E2%80%93eval%E2%80%93print_loop>`_ with
+``ghci`` or ``stack ghci``. Once the REPL is loaded import the modules you want
+to use and you're good to go!
+
+
+In a `Cabal <https://cabal.readthedocs.io>`_ or `Stack <https://www.haskellstack.org>`_ project
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Add ``containers`` to the ``build-depends:`` stanza for your library,
+executable, or test-suite::
+
+    library
+        build-depends:
+           base >= 4.3 && < 5,
+           containers >= 0.5.7 && < 0.6
+
+and ``import`` any modules you need in your Haskell source files.
diff --git a/docs/make.bat b/docs/make.bat
new file mode 100644 (file)
index 0000000..b73e839
--- /dev/null
@@ -0,0 +1,36 @@
+@ECHO OFF\r
+\r
+pushd %~dp0\r
+\r
+REM Command file for Sphinx documentation\r
+\r
+if "%SPHINXBUILD%" == "" (\r
+       set SPHINXBUILD=sphinx-build\r
+)\r
+set SOURCEDIR=.\r
+set BUILDDIR=_build\r
+set SPHINXPROJ=containers\r
+\r
+if "%1" == "" goto help\r
+\r
+%SPHINXBUILD% >NUL 2>NUL\r
+if errorlevel 9009 (\r
+       echo.\r
+       echo.The 'sphinx-build' command was not found. Make sure you have Sphinx\r
+       echo.installed, then set the SPHINXBUILD environment variable to point\r
+       echo.to the full path of the 'sphinx-build' executable. Alternatively you\r
+       echo.may add the Sphinx directory to PATH.\r
+       echo.\r
+       echo.If you don't have Sphinx installed, grab it from\r
+       echo.http://sphinx-doc.org/\r
+       exit /b 1\r
+)\r
+\r
+%SPHINXBUILD% -M %1 %SOURCEDIR% %BUILDDIR% %SPHINXOPTS%\r
+goto end\r
+\r
+:help\r
+%SPHINXBUILD% -M help %SOURCEDIR% %BUILDDIR% %SPHINXOPTS%\r
+\r
+:end\r
+popd\r
diff --git a/docs/map.rst b/docs/map.rst
new file mode 100644 (file)
index 0000000..dc8e024
--- /dev/null
@@ -0,0 +1,650 @@
+Maps
+====
+
+.. highlight:: haskell
+
+Maps (sometimes referred to as dictionaries in other languages) allow you to
+store associations between *unique keys* and *values*. There are three
+implementations provided by the ``containers`` package:
+:haddock:`containers/Data.Map.Strict`, :haddock:`containers/Data.Map.Lazy`, and
+:haddock:`containers/Data.IntMap`. You almost never want the lazy version so use
+``Data.Map.Strict``, or if your keys are ``Int`` use ``Data.IntMap``.
+
+::
+
+    data Map k v = ...
+
+    data IntMap v = ...
+
+.. IMPORTANT::
+   ``Map`` relies on the key type ``k`` having instances of the ``Eq`` and
+   ``Ord`` typeclass for its internal representation. These are already defined
+   for builtin types, and if you are using your own data type you can use the
+   `deriving
+   <https://en.wikibooks.org/wiki/Haskell/Classes_and_types#Deriving>`_
+   mechanism.
+
+All of these implementations are *immutable* which means that any update
+functions do not modify the map that you passed in, they creates a new map. In
+order to keep the changes you need to assign it to a new variable. For example::
+
+    let m1 = Map.fromList [("a", 1), ("b", 2)]
+    let m2 = Map.delete "a" m1
+    print m1
+    > fromList [("a",1),("b",2)]
+    print m2
+    > fromList [("b",2)]
+
+
+Short Example
+-------------
+
+The following GHCi session shows some of the basic map functionality::
+
+    import qualified Data.Map.Strict as Map
+
+    let nums = Map.fromList [(1,"one"), (2,"two"), (3,"three")]
+
+    -- Get the English word for the number 3 and 4.
+    Map.lookup 3 nums
+    > Just "three"
+
+    Map.lookup 4 nums
+    > Nothing
+
+
+    -- Add (4, "four") to our original map.
+    let moreNums = Map.insert 4 "four" nums
+
+    Map.member moreNums 4
+    > True
+
+
+    -- Remove the entry for 1 from our original map.
+    let fewerNums = Map.delete 1 nums
+
+    Map.toAscList fewerNums
+    > [(2,"two"),(3,"three")]
+
+
+    -- Create a new map and combine it with our original map.
+    -- fromList is right-biased: if a key is repeated the rightmost value is taken.
+    let newNums = Map.fromList [(3,"new three"), (4,"new four"), (4,"newer four")]
+
+    -- union is left-biased: if a key occurs more than once the value from the
+    -- left map is taken.
+    Map.union newNums nums
+    > fromList [(1,"one"),(2,"two"),(3,"new three"),(4,"newer four")]
+
+.. TIP:: You can use the `OverloadedLists
+        <https://ghc.haskell.org/trac/ghc/wiki/OverloadedLists>`_ extension so
+        you don't need to write ``fromList [1, 2, 3]`` everywhere; instead you
+        can just write ``[1, 2, 3]`` and if the function is expecting a map it
+        will be converted automatically! The code here will continue to use
+        ``fromList`` for clarity though.
+
+
+Importing Map and IntMap
+------------------------
+
+When using ``Map`` or ``IntMap`` in a Haskell source file you should always use
+a ``qualified`` import because these modules export names that clash with the
+standard Prelude (you can import the type constructor on its own though!). You
+should also import ``Prelude`` and hide ``lookup`` because if you accidentally
+leave off the ``Map.`` qualifier you'll get confusing type errors. You can
+always import any specific identifiers you want unqualified. Most of the time,
+that will include the type constructor (``Map``).
+
+::
+
+    import Prelude hiding (lookup)
+
+    import Data.Map.Strict (Map)
+    import qualified Data.Map.Strict as Map
+
+    import Data.IntMap (IntMap)
+    import qualified Data.IntMap.Strict as IntMap
+
+
+Common API Functions
+--------------------
+
+.. TIP::
+   All of these functions that work for ``Map`` will also work for ``IntMap``,
+   which has the key type ``k`` specialized to ``Int``. Anywhere that you
+   see ``Map Int v`` you can replace it with ``IntMap v``. This will speed up
+   most operations tremendously (see `Performance`_) with the exception of
+   ``size`` which is O(1) for ``Map`` and O(n) for ``IntMap``.
+
+.. NOTE::
+   A ``Map`` is printed as an association list preceeded by ``fromList``. For
+   example, it might look like ``fromList [(Key1,True),(Key2,False)]``.
+
+
+Construction and Conversion
+^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Create an empty map
+"""""""""""""""""""
+
+::
+
+    Map.empty :: Map k v
+    Map.empty = ...
+
+:haddock_short:`Data.Map.Strict#empty` creates a map without any entries.
+
+::
+
+    Map.empty
+    > fromList []
+
+Create a map with one entry (singleton)
+"""""""""""""""""""""""""""""""""""""""
+
+::
+
+    Map.singleton :: k -> v -> Map k v
+    Map.singleton key value = ...
+
+:haddock_short:`Data.Map.Strict#singleton` creates a map with a single
+``(key,value)`` entry in it.
+
+::
+
+    Map.singleton 1 "one"
+    > fromList [(1,"one")]
+
+    Map.singleton "containers" ["base"]
+    > fromList [("containers",["base"])]
+
+Create a map from a list
+""""""""""""""""""""""""
+
+::
+
+    Map.fromList :: Ord k => [(k, v)] -> Map k v
+    Map.fromList xs = ...
+
+:haddock_short:`Data.Map.Strict#fromList` creates a map containing the entries
+of the list ``xs`` where the keys comes from the first entries of the pairs and
+the values from the second. If the same key appears more than once then the last
+value is taken.
+
+::
+
+    Map.fromList []
+    > fromList []
+
+    Map.fromList [(1,"uno"), (1,"one"), (2,"two"), (3,"three")]
+    > fromList [(1,"one"),(2,"two"),(3,"three")]
+
+There's another incredibly useful function for constructing a map from a list::
+
+    Map.fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map.Map k a
+    Map.fromListWith f xs = ...
+
+:haddock_short:`Data.Map.Strict#fromListWith` allows you to build a map from a
+list ``xs`` with repeated keys, where ``f`` is used to "combine" (or "choose")
+values with the same key.
+
+::
+
+    -- Build a map from a list, but only keep the largest value for each key.
+    Map.fromListWith max [("a", 2), ("a", 1), ("b", 2)]
+    > fromList [("a",2),("b",2)]
+
+    -- Build a histogram from a list of elements.
+    Map.fromListWith (+) (map (\x -> (x, 1)) ["a", "a", "b", "c", "c", "c"])
+    > fromList [("a",2),("b",1),("c",3)]
+
+    -- Build a map from a list, combining the string values for the same key.
+    Map.fromListWith (++) [(1, "a"), (1, "b"), (2, "x"), (2, "y")]
+    > fromList [(1,"ba"),(2,"yx")]
+
+
+
+Create a list from a map
+""""""""""""""""""""""""
+
+::
+
+    Map.toAscList, Map.toList, Map.assocs :: Map k v -> [(k, v)]
+    Map.toAscList m = ...
+
+.. NOTE::
+   These all do the same thing; use ``toAscList`` because its name indicates
+   the ordering.
+
+.. NOTE::
+   ``Map.toList`` is **not** the same as ``Foldable.toList``; the latter is
+   equivalent to ``elems``, although is rarely useful for maps. In general, use
+   ``toAscList``.
+
+:haddock_short:`Data.Map.Strict#toAscList`,
+:haddock_short:`Data.Map.Strict#toList`, and
+:haddock_short:`Data.Map.Strict#assocs` returns a list containing the (key,
+value) pairs in the map ``m`` in *ascending* key order.
+
+::
+
+    Map.toDescList :: Map k v -> [(k, v)]
+    Map.toDescList m = ...
+
+:haddock_short:`Data.Map.Strict#toDescList` returns a list containing the (key,
+value) pairs in the map ``m`` in *descending* key order.
+
+::
+
+    Map.toAscList (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
+    > [(1,"one"),(2,"two"),(3,"three")]
+
+    Map.toDescList (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
+    > [(3,"three"),(2,"two"),(1,"one")]
+
+
+Querying
+^^^^^^^^
+
+Lookup an entry in the map (lookup)
+"""""""""""""""""""""""""""""""""""
+
+::
+
+    Map.lookup :: Ord k => k -> Map k v -> Maybe v
+    Map.lookup key m = ...
+
+    Map.!? :: Ord k => Map k v -> k -> Maybe v
+    Map.!? m key = ...
+
+:haddock_short:`Data.Map.Strict#lookup` the value corresponding to the given
+``key``, returns ``Nothing`` if the key is not present; the ``!?`` operator
+(*since 0.5.10*) is a flipped version of ``lookup`` and can often be imported
+unqualified.
+
+
+If you want to provide a default value if the key doesn't exist you can do:
+
+::
+
+    import Data.Maybe (fromMaybe)
+
+    -- fromMaybe :: a -> Maybe a -> a
+    fromMaybe defaultValue (lookup k m)
+
+For example::
+
+    import Data.Map.Strict ((!?))
+    import Data.Maybe (fromMaybe)
+
+    Map.lookup 1 Map.empty
+    > Nothing
+
+    Map.lookup 1 (Map.fromList [(1,"one"),(2,"two"),(3,"three")])
+    > Just "one"
+
+    > (Map.fromList [(1,"one"),(2,"two"),(3,"three")]) !? 1
+    > Just "one"
+
+    fromMaybe "?" (Map.empty !? 1)
+    > "?"
+
+    fromMaybe "?" (Map.fromList [(1,"one"), (2,"two"), (3,"three")] !? 1)
+    > "one"
+
+.. WARNING::
+   **DO NOT** Use ``Map.!``. It is partial and throws a runtime error if the key
+   doesn't exist.
+
+Check if a map is empty
+"""""""""""""""""""""""
+
+::
+
+    Map.null :: Map k v -> Bool
+    Map.null m = ...
+
+:haddock_short:`Data.Map.Strict#null` returns ``True`` if the map ``m`` is
+empty and ``False`` otherwise.
+
+::
+
+    Map.null Map.empty
+    > True
+
+    Map.null (Map.fromList [(1,"one")])
+    > False
+
+The number of entries in a map
+""""""""""""""""""""""""""""""
+
+::
+
+    Map.size :: Map k v -> Int
+    Map.size m = ...
+
+:haddock_short:`Data.Map.Strict#size` returns the number of entries in the map
+``m``.
+
+::
+
+    Map.size Map.empty
+    > 0
+
+    Map.size (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
+    > 3
+
+Find the minimum/maximum
+""""""""""""""""""""""""
+
+*Since version 0.5.9*
+
+::
+
+    Map.lookupMin, Map.lookupMax :: Map k v -> Maybe (k, v)
+    Map.lookupMin m = ...
+    Map.lookupMax m = ...
+
+:haddock_short:`Data.Map.Strict#lookupMin` and
+:haddock_short:`Data.Map.Strict#lookupMax` respectively return the
+minimum or maximum element of the map ``m``, or ``Nothing`` if the map is empty.
+
+::
+
+    Map.lookupMin Map.empty
+    > Nothing
+
+    Map.lookupMin (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
+    > Just (1,"one")
+
+    Map.lookupMax (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
+    > Just (3,"three")
+
+.. WARNING::
+   **DO NOT** use ``Map.findMin`` or ``Map.findMax``. They are partial and throw
+   a runtime error if the map is empty.
+
+Modification
+^^^^^^^^^^^^
+
+Adding a new entry to a map
+"""""""""""""""""""""""""""
+
+::
+
+    Map.insert :: Ord k => k -> v -> Map k v -> Map k v
+    Map.insert key value m = ...
+
+:haddock_short:`Data.Map.Strict#insert` adds the ``value`` into the map ``m``
+with the given ``key``, replacing the existing value if the key already exists.
+
+::
+
+    Map.insert 1 "one" Map.empty
+    > Map.fromList [(1,"one")]
+
+    Map.insert 4 "four" (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
+    > fromList [(1,"one"),(2,"two"),(3,"three"),(4,"four")]
+
+    Map.insert 1 "uno" (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
+    > fromList [(1,"uno"),(2,"two"),(3,"three")]
+
+
+Removing an entry from a map
+""""""""""""""""""""""""""""
+
+::
+
+    Map.delete :: Ord k => k -> Map k v -> Map k v
+    Map.delete key m = ...
+
+:haddock_short:`Data.Map.Strict#delete` removes the entry with the specified
+``key`` from the map ``m``.  If the key doesn't exist it leaves the map
+unchanged.
+
+::
+
+    Map.delete 1 Map.empty
+    > Map.empty
+
+    Map.delete 1 (Map.fromList [(1,"one"),(2,"two"),(3,"three")])
+    > fromList [(2,"two"),(3,"three")]
+
+Filtering map entries
+"""""""""""""""""""""
+
+::
+
+    Map.filterWithKey :: (k -> v -> Bool) -> Map k v -> Map k v
+    Map.filterWithKey predicate m = ...
+
+:haddock_short:`Data.Map.Strict#filterWithKey` produces a map consisting of all
+entries of ``m`` for which the ``predicate`` returns ``True``.
+
+::
+
+    let f key value = key == 2 || value == "one"
+    Map.filterWithKey f (Map.fromList [(1,"one"), (2,"two"), (3,"three")])
+    > fromList [(1,"one"),(2,"two"]
+
+
+Modifying a map entry
+"""""""""""""""""""""
+
+::
+
+    Map.adjust :: Ord k => (v -> v) -> k -> Map k v -> Map k v
+    Map.adjust f key m = ...
+
+:haddock_short:`Data.Map.Strict#abjust` applies the value transformation
+function ``f`` to the entry with given ``key``. If no entry for that key exists
+then the map is left unchanged.
+
+::
+
+    Map.alter :: Ord k => (Maybe v -> Maybe v) -> k -> Map k v -> Map k v
+    Map.alter f key m = ...
+
+Apply the value transformation function ``f`` to the entry with given ``key``,
+if no entry for that key exists then the function is passed ``Nothing``. If the
+function returns ``Nothing`` then the entry is deleted, if the function returns
+``Just v2`` then the value for the ``key`` is updated to ``v2``. In other words,
+alter can be used to insert, update, or delete a value.
+
+::
+
+    import Data.Maybe (isJust)
+    let addValueIfMissing mv = if isJust mv then mv else (Just 1)
+    Map.alter addValueIfMissing "key" (Map.fromList [("key", 0)])
+    > fromList [("key",0)]
+
+    let addValueIfMissing mv = if isJust mv then mv else (Just 1)
+    Map.alter addValueIfMissing "new_key" (Map.fromList [("key", 0)])
+    > fromList [("key",0),("new_key",1)]
+
+The function ``doubleIfPositivie`` below will need to be placed in a Haskell
+source file.
+
+::
+
+    doubleIfPositive :: Maybe Int -> Maybe Int
+    doubleIfPositive mv = case mv of
+      -- Do nothing if the key doesn't exist.
+      Nothing -> Nothing
+
+      -- If the key does exist, double the value if it is positive.
+      Just v -> if v > 0 then (Just v*2) else (Just v)
+
+    -- In GHCi
+    Map.alter doubleIfPositive "a" (Map.fromList [("a", 1), ("b", -1)])
+    > Map.fromList [("a",2), ("b",-1)]
+
+    Map.alter doubleIfPositive "b" (Map.fromList [("a", 1), ("b", -1)])
+    > Map.fromList [("a", 1), ("b",-1)]
+
+Modifying all map entries (mapping and traversing)
+""""""""""""""""""""""""""""""""""""""""""""""""""
+
+::
+
+    Map.map :: (a -> b) -> Map k a -> Map k v
+    Map.map f m = ...
+
+    Map.mapWithKey :: (k -> a -> b) -> Map.Map k a -> Map.Map k b
+    Map.mapWithKey g m = ...
+
+
+:haddock_short:`Data.Map.Strict#map` creates a new map by applying the
+transformation function ``f`` to each entries value. This is how `Functor
+<https://wiki.haskell.org/Typeclassopedia#Functor>`_ is defined for maps.
+
+:haddock_short:`Data.Map.Strict#mapWithKey` does the same as ``map`` but gives
+you access to the key in the transformation function ``g``.
+
+::
+
+    Map.map (*10) (Map.fromList [("haskell", 45), ("idris", 15)])
+    > fromList [("haskell",450),("idris",150)]
+
+    -- Use the Functor instance for Map.
+    (*10) <$> Map.fromList [("haskell", 45), ("idris", 15)]
+    > fromList [("haskell",450),("idris",150)]
+
+    let g key value = if key == "haskell" then (value * 1000) else value
+    Map.mapWithKey g (Map.fromList [("haskell", 45), ("idris", 15)])
+    > fromList [("haskell",45000),("idris",15)]
+
+
+You can also apply a function which performs *actions* (such as printing) to
+each entry in the map.
+
+::
+
+    Map.traverseWithKey :: Applicative t => (k -> a -> t b) -> Map.Map k a -> t (Map.Map k b)
+    Map.traverseWithKey f m = ...
+
+:haddock_short:`Data.Map.Strict#traverseWithKey` maps each element of the map
+``m`` to an *action* that produces a result of type ``b``. The actions are
+performed and the values of the map are replaced with the results from the
+function. You can think of this as a ``map`` with affects.
+
+::
+
+    -- | Ask the user how they want to schedule a bunch of tasks
+    -- that the boss has assigned certain priorities.
+    makeSchedule :: Map Task Priority -> IO (Map Task DateTime)
+    makeSchedule = traverseWithKey $ \task priority ->
+      do
+        putStrLn $ "The boss thinks " ++ show task ++
+                    " has priority " ++ show priority ++
+                     ". When do you want to do it?"
+        readLn
+
+
+
+Set-like Operations
+^^^^^^^^^^^^^^^^^^^
+
+.. _union:
+
+Union
+"""""
+
+::
+
+    Map.unionWith :: Ord k => (v -> v -> v) -> Map k v -> Map k v -> Map k v
+    Map.unionWith f l r = ...
+
+:haddock_short:`Data.Map.Strict#union` returns a map containing all entries that
+are keyed in either of the two maps. If the same key appears in both maps, the
+value is determined by calling ``f`` passing in the left and right value (`set
+union <https://en.wikipedia.org/wiki/Union_(set_theory)>`_).
+
+::
+
+
+    Map.unionWith (++) Map.empty (Map.fromList [(1,"x"),(2,"y")])
+    > fromList [(1,"x"),(2,"y")]
+
+    let f lv rv = lv
+    Map.unionWith f (Map.fromList [(1, "a")]) (Map.fromList [(1,"x"),(2,"y")])
+    > fromList [(1,"a"),(2,"y")]
+
+    Map.unionWith (++) (Map.fromList [(1, "a")]) (Map.fromList [(1,"x"),(2,"y")])
+    > fromList [(1,"ax"),(2,"y")]
+
+
+Intersection
+""""""""""""
+
+::
+
+    Map.intersectionWith :: Ord k => (v -> v -> v) -> Map k v -> Map k v -> Map k v
+    Map.intersectionWith f l r = ...
+
+:haddock_short:`Data.Map.Strict#intersection` returns a map containing all
+entries that have a key in both maps ``l`` and ``r``. The value in the returned
+map is determined by calling ``f`` on the values from the left and right map
+(`set intersection <https://en.wikipedia.org/wiki/Intersection_(set_theory)>`_).
+
+::
+
+    Map.intersectionWith (++) Map.empty (Map.fromList [(1,"x"), (2,"y")])
+    > fromList []
+
+    Map.intersectionWith (++) (Map.fromList [(1, "a")]) (Map.fromList [(1,"x"),(2,"y")])
+    > fromList [(1,"ax")]
+
+
+
+Difference
+""""""""""
+
+::
+
+    Map.difference :: Ord k => Map k v -> Map k v -> Map k v
+    Map.difference l r = ...
+
+:haddock_short:`Data.Map.Strict#difference` returns a map containing all entries
+that have a key in the ``l`` map but not the ``r`` map (`set difference/relative
+complement
+<https://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement>`_).
+
+::
+
+    Map.difference (Map.fromList [(1,"one"), (2,"two"), (3,"three")]) Map.empty
+    > fromList [(1,"uno"),(2,"two"),(3,"three")]
+
+    Map.difference (Map.fromList[(1,"one"), (2,"two")]) (Map.fromList [(1,"uno")])
+    > fromList [(2,"two")]
+
+
+Serialization
+-------------
+
+The best way to serialize and deserialize maps is to use one of the many
+libraries which already support serializing maps. :haddock:`binary`,
+:haddock:`cereal`, and :haddock:`store` are some common libraries that people
+use.
+
+.. TIP::
+   If you are writing custom serialization code use
+   :haddock_short:`Data.Map.Strict#fromDistinctAscList` (see
+   `#405 <https://github.com/haskell/containers/issues/405>`_ for more info).
+
+
+Performance
+-----------
+
+The API docs are annotated with the Big-*O* complexities of each of the map
+operations. For benchmarks see the `haskell-perf/dictionaries
+<https://github.com/haskell-perf/dictionaries>`_ page.
+
+
+Looking for more?
+-----------------
+
+Didn't find what you're looking for? This tutorial only covered the most common
+map functions, for a full list of functions see the
+:haddock_short:`Data.Map.Strict#Map` and
+:haddock_short:`Data.IntMap.Strict#IntMap` API documentation.
diff --git a/docs/sequence.rst b/docs/sequence.rst
new file mode 100644 (file)
index 0000000..cb0b83b
--- /dev/null
@@ -0,0 +1,636 @@
+Sequences
+=========
+
+.. highlight:: haskell
+
+Sequences allow you to store a finite number of sequential elements, providing
+fast access to both ends of the sequence as well as efficient concatenation. The
+``containers`` package provides the :haddock:`containers/Data.Sequence` module
+which defines the ``Seq`` data type.
+
+
+Short Example
+-------------
+
+The following GHCi session shows some of the basic sequence funcitonality::
+
+    -- Import the Seq type and operators for combining sequences unqualified.
+    -- Import the rest of the Sequence module qualified.
+    import Data.Sequence (Seq(..), (<|), (|>), (><))
+    import qualified Data.Sequence as Seq
+
+    let nums = Seq.fromList [1, 2, 3]
+
+
+    -- Put numbers on the front and back.
+    0 <| nums
+    > fromList [0,1,2,3]
+
+    nums |> 4
+    > fromList [1,2,3,4]
+
+
+    -- Reverse a sequence
+    Seq.reverse (Seq.fromList [0, 1, 2])
+    > fromList [2,1,0]
+
+
+    -- Put two sequences together.
+    (Seq.fromList [-2, -1]) >< nums
+    > fromList [-2,-1,0,1,2]
+
+
+    -- Check if a sequence is empty and check the length.
+    Seq.null nums
+    > False
+
+    Seq.length nums
+    > 3
+
+
+    -- Lookup an element at a certain index (since version 0.4.8).
+    Seq.lookup 2 nums
+    > Just 3
+
+    -- Or the unsafe version, you MUST check length beforehand.
+    Seq.index 2 nums
+    > 3
+
+
+    -- Map a function over a sequence (can use fmap or the infix function <$>).
+    fmap show nums
+    > fromList ["0","1","2"]
+
+    show <$> nums
+    > fromList ["0","1","2"]
+
+
+    -- Fold a sequence into a summary value.
+    foldr (+) 0 (Seq.fromList [0, 1, 2])
+    > 3
+
+.. TIP:: You can use the `OverloadedLists
+        <http://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#overloaded-lists>`_
+        extension so you don't need to write ``fromList [1, 2, 3]`` everywhere.
+        Instead you can just write ``[1, 2, 3]`` and if the function is
+        expecting a sequence it will be converted automatically! The code here
+        will continue to use ``fromList`` for clarity.
+
+
+Importing Sequence
+------------------
+
+When using ``Sequence`` in a Haskell source file you should always use a
+``qualified`` import becasue it exports names that clash with the standard
+Prelude (you can import the type constructor and some operators on their own
+though!).
+
+::
+
+    import Data.Sequence (Seq, (<|), (|>), (><))
+    import qualified Data.Sequence as Seq
+
+
+Common API Functions
+--------------------
+
+.. NOTE::
+   ``fromList [some,sequence,elements]`` is how a ``Seq`` is printed.
+
+Construction and Conversion
+^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Create an empty sequence
+""""""""""""""""""""""""
+
+::
+
+    Seq.empty :: Seq a
+    Seq.empty = ...
+
+:haddock_short:`Data.Sequence#empty` creates a sequence with zero elements.
+
+::
+
+    Seq.empty
+    > fromList []
+
+
+Create a sequence with one element (singleton)
+""""""""""""""""""""""""""""""""""""""""""""""
+
+::
+
+    Seq.singleton :: a -> Seq a
+    Seq.singleton x = ...
+
+:haddock_short:`Data.Sequence#singleton` creates a sequence with the single
+element ``x`` in it.
+
+::
+
+    Seq.singleton "containers"
+    > fromList ["containers"]
+
+    Seq.singleton 1
+    > fromList [1]
+
+Create a sequence with the same element repeated
+""""""""""""""""""""""""""""""""""""""""""""""""
+
+::
+
+    Seq.replicate :: Int -> a -> Seq a
+    Seq.replicate n x = ...
+
+:haddock_short:`Data.Sequence#replicate` creates a sequence with same element
+``x`` repeated ``n`` times.
+
+::
+
+    Seq.replicate 0 "hi"
+    > fromList []
+
+    Seq.replicate 3 "hi"
+    > fromList ["hi","hi","hi"]
+
+Create a sequence from a list
+"""""""""""""""""""""""""""""
+
+::
+
+    Seq.fromList :: [a] -> Seq a
+    Seq.FromList xs = ...
+
+:haddock_short:`Data.Sequence#fromList` creates a sequence containing the
+elements of the list ``xs``. Sequences allow duplicate so all elements will be
+included in the order given.
+
+::
+
+    Seq.fromList ["base", "containers", "QuickCheck"]
+    > fromList ["base","containers","QuickCheck"]
+
+    Seq.fromList [0, 1, 1, 2, 3, 1]
+    > fromList [0,1,1,2,3,1]
+
+Adding to an existing sequence
+""""""""""""""""""""""""""""""
+
+::
+
+    (<|) :: a -> Seq a -> Seq a
+    x <| xs = ...
+
+    (|>) :: Seq a -> a -> Seq a
+    xs |> x = ...
+
+    (><) :: Seq a -> Seq a -> Seq a
+    l >< r = ...
+
+- ``x <| xs`` places the element ``x`` at the beginning of the sequence ``xs``..
+
+- ``xs |> x`` places the element ``x`` at the end of the sequence ``xs``.
+
+- ``l >< r`` combines the two sequences ``l`` and ``r`` together.
+
+
+Create a list from a sequence
+"""""""""""""""""""""""""""""
+
+::
+
+    import qualified Data.Foldable as Foldable
+    Foldable.toList :: Seq a -> [a]
+
+
+There is no ``toList`` function in the Sequence module since it can be
+`easily implemented <https://wiki.haskell.org/Foldable_and_Traversable>`_ with a
+fold using ``Seq``'s `Foldable
+<https://wiki.haskell.org/Typeclassopedia#Foldable>`_ instance.
+
+::
+
+    import qualified Data.Foldable as Foldable
+    Foldable.toList (Seq.fromList ["base", "containers", "QuickCheck"])
+    > ["base","containers","QuickCheck"]
+
+
+Pattern Matching
+^^^^^^^^^^^^^^^^
+
+*Since 0.5.10*
+
+Just like you can pattern match (aka. destructure) a list ``[a]``, you can do
+the same with sequneces. Let's first look at how we do this with lists::
+
+    case [1, 2, 3] of
+      [] -> "empty list"
+      (x:xs) -> "first:" ++ show x ++ " rest:" ++ show xs
+    > "first:1 rest:[2,3]"
+
+
+Let's do the same thing with sequences!
+
+::
+
+    -- Imports the patterns to match on.
+    import Data.Sequence (Seq (Empty, (:<|), (:|>)))
+
+    case Seq.fromList [1, 2, 3] of
+      Empty -> "empty sequence"
+      x :<| xs -> "first:" ++ x ++ " rest:" ++ show xs
+    > "first:1 rest:fromList [2,3]"
+
+.. NOTE:: You can't copy/paste this into GHCi because it's multiple lines.
+
+You can also take an element off the end::
+
+    -- Imports the patterns to match on.
+    import Data.Sequence (Seq (Empty, (:<|), (:|>)))
+
+    case Seq.fromList [1, 2, 3] of
+      Empty -> "empty sequence"
+      xs :|> x -> "last element:" ++ show x
+    > "last element:3"
+
+Querying
+^^^^^^^^
+
+Check if a sequence is empty
+""""""""""""""""""""""""""""
+
+::
+
+    Seq.null :: Seq a -> Bool
+    Seq.null xs = ...
+
+:haddock_short:`Data.Sequence#null` returns ``True`` if the sequence ``xs`` is
+empty, and ``False`` otherwise.
+
+::
+
+    Seq.null Seq.empty
+    > True
+
+    Seq.null (Seq.fromList [1, 2, 3])
+    > False
+
+The length/size of a sequence
+"""""""""""""""""""""""""""""
+
+::
+
+    Seq.length :: Seq a -> Int
+    Seq.length xs = ...
+
+:haddock_short:`Data.Sequence#length` returns the length of the sequence ``xs``.
+
+::
+
+    Seq.length Seq.empty
+    > 0
+
+    Seq.length (Seq.fromList [1, 2, 3])
+    > 3
+
+The element at a given index
+""""""""""""""""""""""""""""
+
+::
+
+    Seq.lookup :: Int -> Seq a -> Maybe a
+    Seq.lookup n xs = ...
+
+    Seq.!? :: Seq a -> Int -> Maybe a
+    xs !? n = ...
+
+:haddock_short:`Data.Sequence#lookup` returns the element at the position ``n``,
+or ``Nothing`` if the index is out of bounds. :haddock_short:`Data.Sequence#!?`
+is simply a flipped version of ``lookup``.
+
+.. NOTE::
+   You may need to import ``!?`` qualified if you're using a ``Map``,
+   ``IntMap``, or ``Vector`` in the same file because they all export the
+   same operator.
+
+::
+
+    Seq.index :: Seq a -> Int -> a
+    Seq.index xs n = ...
+
+:haddock_short:`Data.Sequence#index` returns the element at the given
+position. It throws a runtime error if the index is out of bounds.
+
+.. TIP::
+   Use ``lookup``/``!?`` whenever you can and explicitly deal with the
+   ``Nothing`` case.
+
+::
+
+    (Seq.fromList ["base", "containers"]) Seq.!? 0
+    > Just "base"
+
+    Seq.index 0 (Seq.fromList ["base", "containers"])
+    > "base"
+
+    (Seq.fromList ["base", "containers"]) Seq.!? 2
+    > Nothing
+
+    Seq.index (Seq.fromList ["base", "containers"]) 2
+    > "*** Exception: index out of bounds
+
+When working with functions that return a ``Maybe v``, use a `case expression
+<https://en.wikibooks.org/wiki/Haskell/Control_structures#case_expressions>`_ to
+deal with the ``Just`` or ``Nothing`` value::
+
+   do
+     let firstDependency = Seq.fromList ["base", "containers"] !? 0
+     case firstDependency of
+       Nothing -> print "Whoops! No dependencies!"
+       Just dep -> print "The first dependency is " ++ dep
+
+
+Modification
+^^^^^^^^^^^^
+
+Inserting an element
+""""""""""""""""""""
+
+::
+
+    Seq.insertAt :: Int -> a -> Seq a -> Seq a
+    Seq.insertAt i x xs = ...
+
+:haddock_short:`Data.Sequence#insertAt` inserts ``x`` into ``xs`` at the index
+``i``, shifting the rest of the sequence over. If ``i`` is out of range then
+``x`` will be inserted at the beginning or the end of the sequence as
+appropriate.
+
+::
+
+    Seq.insertAt 0 "idris" (Seq.fromList ["haskell", "rust"])
+    > fromList ["idris","haskell","rust"]
+
+    Seq.insertAt (-10) "idris" (Seq.fromList ["haskell", "rust"])
+    > fromList ["idris","haskell","rust"]
+
+    Seq.insertAt 10 "idris" (Seq.fromList ["haskell", "rust"])
+    > fromList ["haskell","rust","idris"]
+
+See also `Adding to an existing sequence`_.
+
+Delete an element
+"""""""""""""""""
+
+::
+
+    Seq.deleteAt :: Int -> Seq a -> Seq a
+    Seq.deleteAt i xs = ...
+
+:haddock_short:`Data.Sequence#deleteAt` removes the element of the sequence at
+index ``i``. If the index is out of bounds then the original sequence is
+returned.
+
+::
+
+    Seq.deleteAt 0 (Seq.fromList [0, 1, 2])
+    > fromList [1,2]
+
+    Seq.deleteAt 10 (Seq.fromList [0, 1, 2])
+    > fromList [0,1,2]
+
+Replace an element
+""""""""""""""""""
+
+::
+
+    Seq.update :: Int -> a -> Seq a -> Seq a
+    Seq.update i x xs = ...
+
+:haddock_short:`Data.Sequence#update` replaces the element at position ``i`` in
+the sequence with ``x``. If the index is out of bounds then the original
+sequence is returned.
+
+::
+
+    Seq.update 0 "hello" (Seq.fromList ["hi", "world", "!"])
+    > fromList ["hello","world","!"]
+
+    Seq.update 3 "OUTOFBOUNDS" (Seq.fromList ["hi", "world", "!"])
+    > fromList ["hi","world","!"]
+
+Adjust/modify an element
+""""""""""""""""""""""""
+
+*Since version 0.5.8*
+
+::
+
+    adjust' :: forall a. (a -> a) -> Int -> Seq a -> Seq a
+    adjust' f i xs = ...
+
+:haddock_short:`Data.Sequence#adjust'` updates the element at position ``i`` in
+the sequence by applying the function ``f`` to the existing element. If the
+index is out of bounds then the original sequence is returned.
+
+::
+
+    Seq.adjust' (*10) 0 (Seq.fromList [1, 2, 3])
+    > fromList [10,2,3]
+
+    Seq.adjust' (*10) 3 (Seq.fromList [1, 2, 3])
+    > fromList [1,2,3]
+
+.. NOTE::
+   If you're using an older version of containers which only has ``adjust``, be
+   careful because it can lead to poor performance and space leaks (see
+   :haddock_short:`Data.Sequence#adjust` docs).
+
+Modifying all elements
+""""""""""""""""""""""
+
+::
+
+    fmap :: (a -> b) -> Seq a -> Seq b
+    fmap f xs = ...
+
+    Seq.mapWithIndex :: (Int -> a -> b) -> Seq a -> Seq b
+    Seq.mapWithIndex f xs = ...
+
+:haddock_short:`Data.Sequence#fmap` transform each element of the sequence with
+the function ``f``. ``fmap`` is provided by the `Functor
+<https://wiki.haskell.org/Typeclassopedia#Functor>`_ instance for sequences and
+can also be written infix using the ``<$>`` operator.
+
+:haddock_short:`Data.Sequence#mapWithIndex` allows you to do a similar
+transformation but gives you the index that each element is at.
+
+::
+
+    fmap (*10) (Seq.fromList [1, 2, 3])
+    -- = fromList [1*10, 2*10, 3*10]
+    > fromList [10,20,30]
+
+    (*10) <$> Seq.fromList [1, 2, 3]
+    -- = fromList [1*10, 2*10, 3*10]
+    > fromList [10,20,30]
+
+    let myMapFunc index val = index * val
+
+    Seq.mapWithIndex myMapFunc (Seq.fromList [1, 2, 3])
+    -- = fromList [0*1, 1*2, 2*3]
+    > fromList [0,2,6]
+
+
+Sorting
+^^^^^^^
+
+::
+
+    Seq.sort :: Ord a => Seq a -> Seq a
+    Seq.sort xs = ...
+
+:haddock_short:`Data.Sequence#sort` the sequence ``xs`` using the ``Ord``
+instance.
+
+::
+
+    Seq.sort (Seq.fromList ["x", "a", "c", "b"])
+    > fromList ["a","b","c","x"]
+
+
+Subsequences
+^^^^^^^^^^^^
+
+Take
+""""
+
+::
+
+    Seq.take :: Int -> Seq a -> Seq a
+    Seq.take n xs = ...
+
+:haddock_short:`Data.Sequence#take` returns the first ``n`` elements of the
+sequence ``xs``. If the length of ``xs`` is less than ``n`` then all elements
+are returned.
+
+::
+
+    Seq.take 0 (Seq.fromList [1, 2, 3])
+    > fromList []
+
+    Seq.take 2 (Seq.fromList [1, 2, 3])
+    > fromList [1,2]
+
+    Seq.take 5 (Seq.fromList [1, 2, 3])
+    > fromList [1,2,3]
+
+Drop
+""""
+
+::
+
+    Seq.drop :: Int -> Seq a -> Seq a
+    Seq.drop n xs = ...
+
+:haddock_short:`Data.Sequence#drop` the first ``n`` elements of the sequence
+``xs``. If the length of ``xs`` is less than ``n`` then an empty sequence is
+returned.
+
+::
+
+    Seq.drop 0 (Seq.fromList [1, 2, 3])
+    > fromList [1,2,3]
+
+    Seq.drop 2 (Seq.fromList [1, 2, 3])
+    > fromList [3]
+
+    Seq.drop 5 (Seq.fromList [1, 2, 3])
+    > fromList []
+
+Chunks
+""""""
+
+::
+
+    Seq.chunksOf :: Int -> Seq a -> Seq (Seq a)
+    Seq.chunksOf k xs = ...
+
+:haddock_short:`Data.Sequence#chunksOf` splits the sequence ``xs`` into chunks
+of size ``k``. If the length of the sequence is not evenly divisible by ``k``
+then the last chunk will have less than ``k`` elements.
+
+.. WARNING::
+   ``k`` can only be ``0`` when the sequence is empty, otherwise a runtime
+   error is thrown.
+
+::
+
+    -- A chunk size of 0 can ONLY be given for an empty sequence.
+    Seq.chunksOf 0 Seq.empty
+    > fromList []
+
+    Seq.chunksOf 1 (Seq.fromList [1, 2, 3])
+    > fromList [fromList [1],fromList [2],fromList [3]]
+
+    Seq.chunksOf 2 (Seq.fromList [1, 2, 3])
+    > fromList [fromList [1,2],fromList [3]]
+
+    Seq.chunksOf 5 (Seq.fromList [1, 2, 3])
+    > fromList [fromList [1,2,3]]
+
+
+Folding
+^^^^^^^
+
+::
+
+    foldr :: (a -> b -> b) -> b -> Seq a -> b
+    foldr f init xs = ...
+
+    Seq.foldrWithIndex :: (Int -> a -> b -> b) -> b -> Seq a -> b
+    Seq.foldrWithIndex f init xs = ...
+
+:haddock_short:`Data.Sequence#foldr` collapses the sequence into a summary value
+by repeatedly applying ``f``. ``foldr`` is provided by the `Foldable
+<https://wiki.haskell.org/Typeclassopedia#Foldable>`_ instance for
+sequences. :haddock_short:`Data.Sequence#foldWithIndex` gives you access to the
+position in the sequence when transforming each element.
+
+::
+
+    foldr (+) 0 (Seq.fromList [1, 2, 3])
+    -- = (1 + (2 + (3 + 0)))
+    > 6
+
+    let myFoldFunction index val accum = (index * val) + accum
+
+    Seq.foldrWithIndex myFoldFunction 0 (Seq.fromList [1, 2, 3])
+    -- = ((0*1) + ((1*2) + ((2*3) + 0)))
+    > 8
+
+
+Serialization
+-------------
+
+The best way to serialize and deserialize sequences is to use one of the many
+libraries which already support serializing sequences. :haddock:`binary`,
+:haddock:`cereal`, and :haddock:`store` are some common libraries that people
+use.
+
+
+Performance
+-----------
+
+The API docs are annotated with the Big-*O* complexities of each of the sequence
+operations. For benchmarks see the `haskell-perf/sequences
+<https://github.com/haskell-perf/sequences>`_ page.
+
+
+Looking for more?
+-----------------
+
+Didn't find what you're looking for? This tutorial only covered the most common
+sequence functions, for a full list of functions see the
+:haddock:`containers/Data.Sequence` API documentation.
diff --git a/docs/set.rst b/docs/set.rst
new file mode 100644 (file)
index 0000000..b168c7b
--- /dev/null
@@ -0,0 +1,478 @@
+Sets
+====
+
+Sets allow you to store *unique*, *ordered* elements, providing efficient
+insertion, lookups, deletions, and set operations. There are two implementations
+provided by the ``containers`` package: :haddock:`containers/Data.Set` and
+:haddock:`containers/Data.IntSet`. Use ``IntSet`` if you are storing,
+well... ``Int`` s.
+
+::
+
+    data Set element = ...
+
+    data IntSet = ...
+
+.. IMPORTANT::
+   ``Set`` relies on the `element` type having instances of the ``Eq`` and
+   ``Ord`` typeclass for its internal representation. These are already defined
+   for builtin types, and if you are using your own data type you can use the
+   `deriving
+   <https://en.wikibooks.org/wiki/Haskell/Classes_and_types#Deriving>`_
+   mechanism.
+
+
+All of these implementations are *immutable* which means that any update
+functions do not modify the set that you passed in, they creates a new set. In
+order to keep the changes you need to assign it to a new variable. For example::
+
+    let s1 = Set.fromList ["a", "b"]
+    let s2 = Set.delete "a" s1
+    print s2
+    > fromList ["a","b"]
+    print s2
+    > fromList ["b"]
+
+
+Short Example
+-------------
+
+The following GHCi session shows some of the basic set functionality::
+
+    import qualified Data.Set as Set
+
+    let dataStructures = Set.fromList ["Set", "Map", "Graph", "Sequence"]
+
+    -- Check if "Map" and "Trie" are in the set of data structures.
+    Set.member "Map" dataStructures
+    > True
+
+    Set.member "Trie" dataStructures
+    > False
+
+
+    -- Add "Trie" to our original set of data structures.
+    let moreDataStructures = Set.insert "Trie" dataStructures
+
+    Set.member "Trie" moreDataStructures
+    > True
+
+
+    -- Remove "Graph" froum our original set of data structures.
+    let fewerDataStructures = Set.delete "Graph" dataStructures
+
+    Set.toAscList fewerDataStructures
+    > ["Map","Sequence","Set"]
+
+
+    -- Create a new set and combine it with our original set.
+    let unorderedDataStructures = Set.fromList ["HashSet", "HashMap"]
+
+    Set.union dataStructures unorderedDataStructures
+    > fromList ["Graph","HashMap","HashSet","Map","Sequence","Set"]
+
+
+.. TIP:: You can use the `OverloadedLists
+        <https://ghc.haskell.org/trac/ghc/wiki/OverloadedLists>`_ extension so
+        you don't need to write ``fromList [1, 2, 3]`` everywhere. Instead you
+        can just write ``[1, 2, 3]`` and if the function is expecting a set it
+        will be converted automatically! The code here will continue to use
+        ``fromList`` for clarity though.
+
+
+Importing Set and IntSet
+------------------------
+
+When using ``Set`` or ``IntSet`` in a Haskell source file you should always use
+a ``qualified`` import because these modules export names that clash with the
+standard Prelude. You can import the type constructor and addional functions
+that you care about unqualified.
+
+::
+
+    import Data.Set (Set, lookupMin, lookupMax)
+    import qualified Data.Set as Set
+
+    import Data.IntSet (IntSet)
+    import qualified Data.IntSet as IntSet
+
+
+Common API Functions
+--------------------
+
+.. TIP::
+   All of these functions that work for ``Set`` will also work for ``IntSet``,
+   which has the element type ``a`` specialized to ``Int``. Anywhere that you
+   see ``Set Int`` you can replace it with ``IntSet``. This will speed up
+   most operations tremendously (see `Performance`_) with the exception of
+   ``size`` which is O(1) for ``Set`` and O(n) for ``IntSet``.
+
+.. NOTE::
+   ``fromList [some,list,elements]`` is how a ``Set`` is printed.
+
+
+Construction and Conversion
+^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Create an empty set
+"""""""""""""""""""
+
+::
+
+    Set.empty :: Set a
+    Set.empty = ...
+
+:haddock_short:`Data.Set#empty` creates a set with zero elements.
+
+::
+
+    Set.empty
+    > fromList []
+
+Create a set with one element (singleton)
+"""""""""""""""""""""""""""""""""""""""""
+
+::
+
+    Set.singleton :: a -> Set a
+    Set.singleton x = ...
+
+:haddock_short:`Data.Set#singleton` creates a set with a single element ``x`` in
+it.
+
+::
+
+    Set.singleton "containers"
+    > fromList ["containers"]
+
+    Set.singleton 1
+    > fromList [1]
+
+Create a set from a list
+""""""""""""""""""""""""
+
+::
+
+    Set.fromList :: Ord a => [a] -> Set a
+    Set.fromList xs = ...
+
+:haddock_short:`Data.Set#fromList` creates a set containing the elements of the
+list ``xs``. Since sets don't contain duplicates, if there are repeated elements
+in the list they will only appear once.
+
+::
+
+    Set.fromList ["base", "containers", "QuickCheck"]
+    > fromList ["QuickCheck","base","containers"]
+
+    Set.fromList [1, 1, 2, 3, 4, 4, 5, 1]
+    > fromList [1,2,3,4,5]
+
+Create a list from a set
+""""""""""""""""""""""""
+
+::
+
+    Set.toAscList, Set.toList, Set.elems :: Set a -> [a]
+    Set.toAscList s = ...
+
+:haddock_short:`Data.Set#toAscList`, :haddock_short:`Data.Set#toList`, and
+:haddock_short:`Data.Set#elems` return a list containing the elements of the set
+:haddock_short:``s`` in *ascending* order.
+
+.. NOTE::
+   These all do the same thing; use ``toAscList`` because its name indicates the
+   ordering.
+
+::
+
+    Set.toDescList :: Set a -> [a]
+    Set.toDescList s = ...
+
+:haddock_short:`Data.Set#toDescList` returns a list containing the elements of
+the set ``s`` in *descending* order.
+
+::
+
+    Set.toAscList (Set.fromList [0, 2, 4, 6])
+    > [0,2,4,6]
+
+    Set.toDescList (Set.fromList [0, 2, 4, 6]
+    > [6,4,2,0]
+
+
+Querying
+^^^^^^^^
+
+Check if an element is in a set (member)
+""""""""""""""""""""""""""""""""""""""""
+
+::
+
+    Set.member :: Ord a => a -> Set a -> Bool
+    Set.member x s = ...
+
+:haddock_short:`Data.Set#member` returns ``True`` if the element ``x`` is in the
+set ``s``, ``False`` otherwise.
+
+::
+
+    Set.member 0 Set.empty
+    > False
+
+    Set.member 0 (Set.fromList [0, 2, 4, 6])
+    > True
+
+Check if a set is empty
+"""""""""""""""""""""""
+
+::
+
+    Set.null :: Set a -> Bool
+    Set.null s = ...
+
+:haddock_short:`Data.Set#null` returns ``True`` if the set ``s`` is empty,
+``False`` otherwise.
+
+::
+
+    Set.null Set.empty
+    > True
+
+    Set.null (Set.fromList [0, 2, 4, 6])
+    > False
+
+
+The number of elements in a set
+"""""""""""""""""""""""""""""""
+
+::
+
+    Set.size :: Set a -> Int
+    Set.size s = ...
+
+:haddock_short:`Data.Set#size` returns the number of elements in the set ``s``.
+
+::
+
+    Set.size Set.empty
+    > 0
+
+    Set.size (Set.fromList [0, 2, 4, 6])
+    > 4
+
+Find the minimum/maximum element in a set
+"""""""""""""""""""""""""""""""""""""""""
+
+*Since version 0.5.9*
+
+::
+
+   lookupMin, lookupMax :: Set a -> Maybe a
+   lookupMin s = ...
+   lookupMax s = ...
+
+:haddock_short:`Data.Set#lookupMin` returns the minimum, or maximum
+respectively, element of the set ``s``, or ``Nothing`` if the set is empty.
+
+::
+
+    Set.lookupMin Set.empty
+    > Nothing
+
+    Set.lookupMin (Set.fromList [0, 2, 4, 6])
+    > Just 0
+
+    Set.lookupMax (Set.fromList [0, 2, 4, 6])
+    > Just 6
+
+.. WARNING::
+   Unless you're using an old version of ``containers`` **DO NOT** use
+   ``Set.findMin`` or ``Set.findMax``. They are partial and throw a runtime
+   error if the set is empty.
+
+Modification
+^^^^^^^^^^^^
+
+Adding a new element to a set
+"""""""""""""""""""""""""""""
+
+::
+
+    Set.insert :: Ord a => a -> Set a -> Set a
+    Set.insert x s = ...
+
+:haddock_short:`Data.Set#insert` places the element ``x`` into the set ``s``,
+replacing an existing equal element if it already exists.
+
+::
+
+    Set.insert 100 Set.empty
+    > fromList [100]
+
+    Set.insert 0 (Set.fromList [0, 2, 4, 6])
+    > fromList [0,2,4,6]
+
+Removing an element from a set
+""""""""""""""""""""""""""""""
+
+::
+
+    Set.delete :: Ord a => a -> Set a -> Set a
+    Set.delete x s = ...
+
+:haddock_short:`Data.Set#delete` the element ``x`` from the set ``s``. If it’s
+not a member it leaves the set unchanged.
+
+::
+
+    Set.delete 0 (Set.fromList [0, 2, 4, 6])
+    > fromList [2,4,6]
+
+Filtering elements from a set
+"""""""""""""""""""""""""""""
+
+::
+
+    Set.filter :: (a -> Bool) -> Set a -> Set a
+    Set.filter predicate s = ...
+
+:haddock_short:`Data.Set#filter` produces a set consisting of all elements of
+``s`` for which the `predicate`` returns ``True``.
+
+::
+
+    Set.filter (==0) (Set.fromList [0, 2, 4, 6])
+    > fromList [0]
+
+
+Set Operations
+^^^^^^^^^^^^^^
+
+Union
+"""""
+
+::
+
+    Set.union :: Ord a => Set a -> Set a -> Set a
+    Set.union l r = ...
+
+:haddock_short:`Data.Set#union` returns a set containing all elements that are
+in either of the two sets ``l`` or ``r`` (`set union
+<https://en.wikipedia.org/wiki/Union_(set_theory)>`_).
+
+::
+
+    Set.union Set.empty (Set.fromList [0, 2, 4, 6])
+    > fromList [0,2,4,6]
+
+    Set.union (Set.fromList [1, 3, 5, 7]) (Set.fromList [0, 2, 4, 6])
+    > fromList [0,1,2,3,4,5,6,7]
+
+Intersection
+""""""""""""
+
+::
+
+    Set.intersection :: Ord a => Set a -> Set a -> Set a
+    Set.intersection l r = ...
+
+:haddock_short:`Data.Set#intersection` returns a set the elements that are in
+both sets ``l`` and ``r`` (`set intersection
+<https://en.wikipedia.org/wiki/Intersection_(set_theory)>`_).
+
+::
+
+    Set.intersection Set.empty (Set.fromList [0, 2, 4, 6])
+    > fromList []
+
+    Set.intersection (Set.fromList [1, 3, 5, 7]) (Set.fromList [0, 2, 4, 6])
+    > fromList []
+
+    Set.intersection (Set.singleton 0) (Set.fromList [0, 2, 4, 6])
+    > fromList [0]
+
+Difference
+""""""""""
+
+::
+
+    Set.difference :: Ord a => Set a -> Set a -> Set a
+    Set.difference l r = ...
+
+:haddock_short:`Data.Set#difference` returns a set containing the elements that
+are in the first set ``l`` but not the second set ``r`` (`set
+difference/relative compliment
+<https://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement>`_).
+
+::
+
+    Set.difference (Set.fromList [0, 2, 4, 6]) Set.empty
+    > fromList [0,2,4,6]
+
+    Set.difference (Set.fromList [0, 2, 4, 6]) (Set.fromList [1, 3, 5, 7])
+    > fromList [0,2,4,6]
+
+    Set.difference (Set.fromList [0, 2, 4, 6]) (Set.singleton 0)
+    > fromList [2,4,6]
+
+Subset
+""""""
+
+::
+
+    Set.isSubsetOf :: Ord a => Set a -> Set a -> Bool
+    Set.isSubsetOf l r = ...
+
+:haddock_short:`Data.Set#isSubsetOf` returns ``True`` if all elements in the
+first set ``l`` are also in the second set ``r`` (`subset
+<https://en.wikipedia.org/wiki/Subset>`_).
+
+.. NOTE::
+   We use `infix notation
+   <https://wiki.haskell.org/Infix_operator#Using_infix_functions_with_prefix_notation>`_
+   so that it reads nicer. These are back-ticks (`), not single quotes (').
+
+::
+
+    Set.empty `Set.isSubsetOf` Set.empty
+    > True
+
+    Set.empty `Set.isSubsetOf` (Set.fromList [0, 2, 4, 6])
+    > True
+
+    (Set.singleton 0) `Set.isSubsetOf` (Set.fromList [0, 2, 4, 6])
+    > True
+
+    (Set.singleton 1) `Set.isSubsetOf` (Set.fromList [0, 2, 4, 6])
+    > False
+
+
+Serialization
+-------------
+
+The best way to serialize and deserialize sets is to use one of the many
+libraries which already support serializing sets. :haddock:`binary`,
+:haddock:`cereal`, and :haddock:`store` are some common libraries that people
+use.
+
+.. TIP::
+   If you are writing custom serialization code use
+   :haddock_short:`Data.Set#fromDistinctAscList` (see
+   `#405 <https://github.com/haskell/containers/issues/405>`_ for more info).
+
+Performance
+-----------
+
+The API docs are annotated with the Big-*O* complexities of each of the set
+operations. For benchmarks see the `haskell-perf/sets
+<https://github.com/haskell-perf/sets>`_ page.
+
+
+Looking for more?
+-----------------
+
+Didn't find what you're looking for? This tutorial only covered the most common
+set functions, for a full list of functions see the
+:haddock_short:`Data.Set#Set` and :haddock_short:`Data.IntSet#IntSet` API
+documentation.