This package contains efficient general-purpose implementations 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.
The declared cost of each operation is either worst-case or amortized, but remains valid even if structures are shared.
Released with GHC 8.6
New functions and class instances
nub-like functions. (Thanks to Gershom Bazerman for starting the process of writing these.)
Generic1instances for key
Death of deprecated functions
The following functions have been disabled. As an experiment in function removal technology, the functions are still temporarily present, but any attempts to use them will result in type errors advising on replacement.
The same has been done for the deprecated exports of
showTreeWith. These function remain available in the internal
Changes to existing functions
Generalize the types of
unionsWith. (Thanks, jwaldmann.)
Speed up folds and
traverseon sequences. (Thanks, Donnacha Oisín Kidney.)
Data.Set.union. (Thanks, Joachim Breitner.)
Speed up several algorithms in
Data.Grapha bit by using unboxed arrays where appropriate.
Data.Graph.indegreedirectly instead of taking the transpose and calculating its
outdegree. This may not lead to an immediate performance improvement (see GHC Trac #14785) but it should be better eventually.
Other package changes
Drop support for GHC versions before 7.6.
Data.Graphdocumentation, and reorganize map and set documentation.
Data.Map.Strict.Mergemodules. These were renamed and deprecated almost as soon as they were introduced.
Released with GHC 8.4.
New functions and class instances
Data.Set. (Thanks, Edward Kmett.)
Data.IntSet. (Thanks, Víctor López Juan.)
Data.IntMap. (Thanks, bwroga.)
Data.Sequence. Make unzipping build its results in lockstep to avoid certain space leaks.
Add carefully optimized implementations of
Data.Sequence. (Thanks, Donnacha Oisín Kidney.)
Changes to existing functions and features
Data.Sequence.replicateMa synonym for
IsStringinstance head for sequences, improving compatibility with the list instance and also improving type inference. We used to have
instance IsString (Seq Char)
Now we commit more eagerly with
instance a ~ Char => IsString (Seq a)
Data.Treestrict in the result of its second argument; being too lazy here is almost useless, and violates one of the monad identity laws. Specifically,
return () >>= \_ -> undefinedshould always be
undefined, but this was not the case.
Harmonize laziness details for
Speed up both stable and unstable sorting for
Data.Sequenceby (Thanks, Donnacha Oisín Kidney.)
Update for recent and upcoming GHC and Cabal versions (Thanks, Herbert Valerio Reidel, Simon Jakobi, and Ryan Scott.)
Improve external and internal documentation (Thanks, Oleg Grenrus and Benjamin Hodgson.)
Add tutorial-style documentation.
@sinceannotations for changes made since version 0.5.4 (Thanks, Simon Jakobi.)
Add a (very incomplete) test suite for
Add structural validity checks to the test suites for
Data.IntSet(Thanks to Joachim Breitner for catching an error in a first draft.)
Released with GHC 8.2.
COMPLETEpragmas to declare complete sets of pattern synonyms for
Data.Sequence. At last!
Data.IntMap.Strict.traverseWithKeyforce the values before installing them in the result. Previously, this function could be used to produce an
IntMapcontaining undefined values.
Fix strictness bugs in various rewrite rules for
Data.IntMap.Strict. Previously, rules could unintentionally reduce strictness. The most important change in this regard is the elimination of rules rewriting
coerce. To map a coercion over a structure for free, be sure to use the lazy
fmap. It is possible to write rules that do a somewhat better job of this, but it turns out to be a bit messy.
Data.IntMap.withoutKeys. The semantic fix in 0.5.10.1 left them rather slow in certain cases.
IntMap(thanks, Mike Ledger!).
Define a custom
Applicativeinstances for base 4.10, and use
<*>whenever it may be beneficial.
Export non-deprecated versions of
Fix completely incorrect implementations of
Data.IntMap.withoutKeys. Make the tests for these actually run. (Thanks to Tom Smalley for reporting this.)
Fix a minor bug in the
Data.Tree. This produced valid output, but with fewer parentheses than
Show. (Thanks, Ryan Scott.)
Remove meaningless stability annotations (Thanks, Simon Jakobi.)
Backport bug fixes from 0.5.10.1
Add instances for
Add lifted instances (from
Data.Tree. (Thanks to Oleg Grenrus for doing a lot of this work.)
Properly deprecate functions in
Data.IntMaplong documented as deprecated.
Rename several internal modules for clarity. Thanks to esoeylemez for starting this process.
Data.Map.fromDistinctDescListmore eager, improving performance.
Plug space leaks in
Data.Map.Lazy.fromDescList by manually inlining constant functions.
Data.Mapas total alternatives to
Data.Mapas a total alternative to
deleteFindMaxinternally, preferring total functions instead. New implementations of said functions lead to slight performance improvements overall.
Backport bug fixes from 0.5.10.1.
0.5.8.1 Aug 2016
General package changes
Remove all attempts to support nhc98 and any versions of GHC before 7.0.
Integrate benchmarks with Cabal. (Thanks, Gabriel Gonzalez!)
Make Cabal report required extensions properly, and stop using default extensions. Note that we do not report extensions conditionally enabled based on GHC version, as doing so would lead to a maintenance nightmare with no obvious benefits.
BangPatternsthroughout to reduce noise. This extension is now required to compile
Improve QuickCheck properties taking arbitrary functions by using
Test.QuickCheck.Function.Funinstead of evil
Showinstances for functions.
Expose several internal modules through Cabal (as requested by Edward Kmett). These remain completely unsupported.
New exports and instances
Data.Set. Thanks to Cale Gibbard for suggesting these.
mergeA, and associated merge tactics for
Data.Map. Many thanks to Cale Gibbard, Ryan Trinkle, and Dan Doel for inspiring the merge idea and helping refine the interface.
:|>pattern synonyms for
Data.Tree. (Thanks, Daniel Wagner!)
Data.Sequence.splitAtstrict in its arguments. Previously, it returned a lazy pair.
Fix completely erroneous definition of
Data.Map.Strict.traverseWithKeyforce result values before installing them in the new map.
drawTreehandle newlines better. (Thanks, recursion-ninja!)
All functions in
Data.Mapproper that have been documented as deprecated since version 0.5 or before now have
DEPRECATEDpragmas and will actually be removed after another cycle or two.
Tree printing functions in
Data.Mapintended for library debugging are now deprecated. They will continue to be available for the foreseeable future in an internal module.
Substantially speed up
Data.Sequence. Special thanks to Lennart Spitzner for digging into the performance problems with previous versions of
fromListand finding a way to make it really fast. Slightly optimize
traversefrom performing many unnecessary
Most operations in
Data.Sequenceadvertised as taking logarithmic time (including
adjust) now use their full allotted time to avoid potentially building up chains of thunks in the tree. In general, the only remaining operations that avoid doing more than they really need are the particular bulk creation and transformation functions that really benefit from the extra laziness. There are some situations where this change may slow programs down, but I think having more predictable and usually better performance more than makes up for that.
Add rewrite rules to fuse
Switch from hedge algorithms to divide-and-conquer algorithms for union, intersection, difference, and merge in both
Data.Set. These algorithms are simpler, are known to be asymptotically optimal, and are faster according to our benchmarks.
mapto inline, and define a custom
(<$). This considerably improves mapping with a constant function.
Remove non-essential laziness in
Speed up deletion and alteration functions for
0.5.7.1 Dec 2015
Planned to bundle with GHC 8.0.1.
0.5.6.2 Dec 2014
Bundled with GHC 7.10.1.
Add role annotations for
Several performance improvements for
0.5.4.0 Jan 2014
Bundled with GHC 7.8.1.
Data.Set.fromListnow use linear-time algorithm if the input is sorted, without need to call
Implement indexing operations (
0.5.0.0 May 2012
Bundled with GHC 7.6.1.
- Major improvements since last release:
- a clearer distinction between value-lazy and value-strict containers,
- performance improvements across the board,
- a big internal clean-up, and
- new functions for e.g. merging, updating, and searching containers.
While the old
Data.IntMapmodules will continue to exist for the foreseeable future, we've abandoned the practice of having the strict and lazy versions of each function distinguished by an apostrophe. The distinction is instead made at the module level, by introducing four new modules: Data.Map.Strict Data.Map.Lazy Data.IntMap.Strict Data.IntMap.Lazy
This split has three benefits: It makes the choice between value-strict and value-lazy containers more declarative; you pick once at import time, instead of having to remember to use the strict or lazy versions of a function every time you modify the container. It alleviates a common source of performance issues, by forcing the user to think about the strictness properties upfront. For example, using insertWith instead of insertWith' is a common source of containers-related performance bugs. * There are fewer functions per module, making it easier to get an overview of each module.
Note that the types used in the strict and lazy APIs are the same, so you can still use the same container in a "mixed" manner, if needed.
Data.IntSetrepresentation changed to store small sets using bits in an
Word. Larger sets are stored as a collection of such dense small sets, connected together by a prefix trie.
0.4.2.1 Feb 2012
Bundled with GHC 7.4.1.
Data.Map now exportsfoldr
Data.Set now exportsfoldr
Data.IntMap now exportsfoldr
Data.IntSet now exportsfoldr
Data.Map.foldWithKeyis no longer deprecated, although it is expected to be deprecated again in the future.
There are now
0.4.1.0 Aug 2011
Bundled with GHC 7.2.1.
Data.Mapnow exports new functions
foldlWithKey', which are strict variants of
Data.IntMapnow exports new functions
insertWithKey', which are strict variants of
0.4.0.0 Nov 2010
Bundled with GHC 7.0.1.
Strictness is now more consistent, with containers being strict in their elements even in singleton cases.
There is a new function
Data.Maphas been deprecated in favour of
0.3.0.0 Dec 2009
Bundled with GHC 6.12.1.
mapAccumRWithKeyhas been added to
Traversableinstance has been added to
The types of
Data.IntMap.intersectionWithKeyhave been changed from
intersectionWith :: (a -> b -> a) -> IntMap a -> IntMap b -> IntMap a
intersectionWithKey :: (Key -> a -> b -> a) -> IntMap a -> IntMap b -> IntMap ato
intersectionWith :: (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
intersectionWithKey :: (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
The types of
Data.IntMap.findMaxhave been changed from
findMin :: IntMap a -> a
findMax :: IntMap a -> ato
findMin :: IntMap a -> (Int,a)
findMax :: IntMap a -> (Int,a)
0.2.0.0 Nov 2008
Bundled with GHC 6.10.1.
Various result type now use
Mayberather than allowing any
0.1.0.0 Nov 2007
Bundled with GHC 6.8.1.
Initial split off from GHC base.