From 374d1c9887746efe98a08ef6a7abc7967ff513e1 Mon Sep 17 00:00:00 2001
From: Matt Renaud
Date: Sun, 28 Jan 2018 17:43:15 0800
Subject: [PATCH] Improve IntSet and IntMap module docs. (#507)

Data/IntMap/Lazy.hs  72 ++++++++++++++++++
Data/IntMap/Strict.hs  98 +++++++++++++++++++++++++++
Data/IntSet.hs  29 ++++++++++
3 files changed, 109 insertions(+), 90 deletions()
diff git a/Data/IntMap/Lazy.hs b/Data/IntMap/Lazy.hs
index ebd579c..4b765ad 100644
 a/Data/IntMap/Lazy.hs
+++ b/Data/IntMap/Lazy.hs
@@ 14,26 +14,47 @@
 Maintainer : libraries@haskell.org
 Portability : portable

 An efficient implementation of maps from integer keys to values
 (dictionaries).

 API of this module is strict in the keys, but lazy in the values.
 If you need valuestrict maps, use "Data.IntMap.Strict" instead.
 The 'IntMap' type itself is shared between the lazy and strict modules,
 meaning that the same 'IntMap' value can be passed to functions in
 both modules (although that is rarely needed).
+ = Finite Int Maps (lazy interface)

 These modules are intended to be imported qualified, to avoid name
 clashes with Prelude functions, e.g.
+ The @'IntMap' v@ type represents a finite map (sometimes called a dictionary)
+ from keys of type @Int@ to values of type @v@.

 > import Data.IntMap.Lazy (IntMap)
 > import qualified Data.IntMap.Lazy as IntMap
+ The functions in "Data.IntMap.Strict" are careful to force values before
+ installing them in an 'IntMap'. This is usually more efficient in cases where
+ laziness is not essential. The functions in this module do not do so.
+
+ For a walkthrough of the most commonly used functions see the
+ .
+
+ This module is intended to be imported qualified, to avoid name clashes with
+ Prelude functions:
+
+ > import Data.IntMap.Lazy (IntMap)
+ > import qualified Data.IntMap.Lazy as IntMap
+
+ Note that the implementation is generally /leftbiased/. Functions that take
+ two maps as arguments and combine them, such as `union` and `intersection`,
+ prefer the values in the first argument to those in the second.
+
+
+ == Detailed performance information
+
+ The amortized running time is given for each operation, with /n/ referring to
+ the number of entries in the map and /W/ referring to the number of bits in
+ an 'Int' (32 or 64).
+
+ Benchmarks comparing "Data.IntMap.Lazy" with other dictionary
+ implementations can be found at https://github.com/haskellperf/dictionaries.
+
+
+ == Implementation

 The implementation is based on /bigendian patricia trees/. This data
 structure performs especially well on binary operations like 'union'
 and 'intersection'. However, my benchmarks show that it is also
 (much) faster on insertions and deletions when compared to a generic
 sizebalanced map implementation (see "Data.Map").
+ structure performs especially well on binary operations like 'union' and
+ 'intersection'. Additionally, benchmarks show that it is also (much) faster
+ on insertions and deletions when compared to a generic sizebalanced map
+ implementation (see "Data.Map").

 * Chris Okasaki and Andy Gill, \"/Fast Mergeable Integer Maps/\",
 Workshop on ML, September 1998, pages 7786,
@@ 43,18 +64,9 @@
 Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),
 October 1968, pages 514534.

 Operation comments contain the operation time complexity in
 the BigO notation .
 Many operations have a worstcase complexity of /O(min(n,W))/.
 This means that the operation can become linear in the number of
 elements with a maximum of /W/  the number of bits in an 'Int'
 (32 or 64).

module Data.IntMap.Lazy (
  * Strictness properties
  $strictness

 * Map type
#if !defined(TESTING)
IntMap, Key  instance Eq,Show
@@ 211,15 +223,3 @@ module Data.IntMap.Lazy (
import Data.IntMap.Internal as IM hiding (showTree, showTreeWith)
import Data.IntMap.Internal.DeprecatedDebug

 $strictness

 This module satisfies the following strictness property:

 * Key arguments are evaluated to WHNF

 Here are some examples that illustrate the property:

 > insertWith (\ new old > old) undefined v m == undefined
 > insertWith (\ new old > old) k undefined m == OK
 > delete undefined m == undefined
diff git a/Data/IntMap/Strict.hs b/Data/IntMap/Strict.hs
index dc638f0..96ade46 100644
 a/Data/IntMap/Strict.hs
+++ b/Data/IntMap/Strict.hs
@@ 15,26 +15,63 @@
 Maintainer : libraries@haskell.org
 Portability : portable

 An efficient implementation of maps from integer keys to values
 (dictionaries).

 API of this module is strict in both the keys and the values.
 If you need valuelazy maps, use "Data.IntMap.Lazy" instead.
 The 'IntMap' type itself is shared between the lazy and strict modules,
 meaning that the same 'IntMap' value can be passed to functions in
 both modules (although that is rarely needed).
+ = Finite Int Maps (strict interface)

 These modules are intended to be imported qualified, to avoid name
 clashes with Prelude functions, e.g.
+ The @'IntMap' v@ type represents a finite map (sometimes called a dictionary)
+ from key of type @Int@ to values of type @v@.

 > import Data.IntMap.Strict (IntMap)
 > import qualified Data.IntMap.Strict as IntMap
+ Each function in this module is careful to force values before installing
+ them in a 'Map'. This is usually more efficient when laziness is not
+ necessary. When laziness /is/ required, use the functions in
+ "Data.IntMap.Lazy".
+
+ In particular, the functions in this module obey the following law:
+
+  If all values stored in all maps in the arguments are in WHNF, then all
+ values stored in all maps in the results will be in WHNF once those maps
+ are evaluated.
+
+ For a walkthrough of the most commonly used functions see the
+ .
+
+ This module is intended to be imported qualified, to avoid name clashes with
+ Prelude functions:
+
+ > import Data.IntMap.Strict (IntMap)
+ > import qualified Data.IntMap.Strict as IntMap
+
+ Note that the implementation is generally /leftbiased/. Functions that take
+ two maps as arguments and combine them, such as `union` and `intersection`,
+ prefer the values in the first argument to those in the second.
+
+
+ == Detailed performance information
+
+ The amortized running time is given for each operation, with /n/ referring to
+ the number of entries in the map and /W/ referring to the number of bits in
+ an 'Int' (32 or 64).
+
+ Benchmarks comparing "Data.IntMap.Strict" with other dictionary
+ implementations can be found at https://github.com/haskellperf/dictionaries.
+
+
+ == Warning
+
+ The 'IntMap' type is shared between the lazy and strict modules, meaning that
+ the same 'IntMap' value can be passed to functions in both modules. This
+ means that the 'Functor', 'Traversable' and 'Data' instances are the same as
+ for the "Data.IntMap.Lazy" module, so if they are used the resulting map may
+ contain suspended values (thunks).
+
+
+ == Implementation

 The implementation is based on /bigendian patricia trees/. This data
 structure performs especially well on binary operations like 'union'
 and 'intersection'. However, my benchmarks show that it is also
 (much) faster on insertions and deletions when compared to a generic
 sizebalanced map implementation (see "Data.Map").
+ structure performs especially well on binary operations like 'union' and
+ 'intersection'. Additionally, benchmarks show that it is also (much) faster
+ on insertions and deletions when compared to a generic sizebalanced map
+ implementation (see "Data.Map").

 * Chris Okasaki and Andy Gill, \"/Fast Mergeable Integer Maps/\",
 Workshop on ML, September 1998, pages 7786,
@@ 44,24 +81,11 @@
 Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),
 October 1968, pages 514534.

 Operation comments contain the operation time complexity in
 the BigO notation .
 Many operations have a worstcase complexity of /O(min(n,W))/.
 This means that the operation can become linear in the number of
 elements with a maximum of /W/  the number of bits in an 'Int'
 (32 or 64).

 Be aware that the 'Functor', 'Traversable' and 'Data' instances
 are the same as for the "Data.IntMap.Lazy" module, so if they are used
 on strict maps, the resulting maps will be lazy.

 See the notes at the beginning of Data.IntMap.Internal.
module Data.IntMap.Strict (
  * Strictness properties
  $strictness

 * Map type
#if !defined(TESTING)
IntMap, Key  instance Eq,Show
@@ 310,24 +334,6 @@ import Data.Functor((<$>))
#endif
import Control.Applicative (Applicative (..), liftA2)
 $strictness

 This module satisfies the following strictness properties:

 1. Key arguments are evaluated to WHNF;

 2. Keys and values are evaluated to WHNF before they are stored in
 the map.

 Here's an example illustrating the first property:

 > delete undefined m == undefined

 Here are some examples that illustrate the second property:

 > map (\ v > undefined) m == undefined  m is not empty
 > mapKeys (\ k > undefined) m == undefined  m is not empty

{
Query
}
diff git a/Data/IntSet.hs b/Data/IntSet.hs
index f47dccf..3409d55 100644
 a/Data/IntSet.hs
+++ b/Data/IntSet.hs
@@ 14,7 +14,13 @@
 Maintainer : libraries@haskell.org
 Portability : portable

 An efficient implementation of integer sets.
+
+ = Finite Int Sets
+
+ The @'IntSet'@ type represents a set of elements of type @Int@.
+
+ For a walkthrough of the most commonly used functions see their
+ .

 These modules are intended to be imported qualified, to avoid name
 clashes with Prelude functions, e.g.
@@ 22,6 +28,17 @@
 > import Data.IntSet (IntSet)
 > import qualified Data.IntSet as IntSet

+
+ == Performance information
+
+ Many operations have a worstcase complexity of /O(min(n,W))/.
+ This means that the operation can become linear in the number of
+ elements with a maximum of /W/  the number of bits in an 'Int'
+ (32 or 64).
+
+
+ == Implementation
+
 The implementation is based on /bigendian patricia trees/. This data
 structure performs especially well on binary operations like 'union'
 and 'intersection'. However, my benchmarks show that it is also
@@ 38,14 +55,10 @@

 Additionally, this implementation places bitmaps in the leaves of the tree.
 Their size is the natural size of a machine word (32 or 64 bits) and greatly
 reduce memory footprint and execution times for dense sets, e.g. sets where
 it is likely that many values lie close to each other. The asymptotics are
 not affected by this optimization.
+ reduces the memory footprint and execution times for dense sets, e.g. sets
+ where it is likely that many values lie close to each other. The asymptotics
+ are not affected by this optimization.

 Many operations have a worstcase complexity of /O(min(n,W))/.
 This means that the operation can become linear in the number of
 elements with a maximum of /W/  the number of bits in an 'Int'
 (32 or 64).

module Data.IntSet (

1.9.1