containers
Assorted concrete container types
Version on this page: | 0.6.5.1 |
LTS Haskell 22.43: | 0.6.7 |
Stackage Nightly 2024-12-05: | 0.6.8 |
Latest on Hackage: | 0.7 |
containers-0.6.5.1@sha256:a029734132bb3471f8a91e3deaa095581a97410c405a1c665643053db87d87c1,2596
Module documentation for 0.6.5.1
- Data
- Data.Containers
- Data.Graph
- Data.IntMap
- Data.IntSet
- Data.Map
- Data.Sequence
- Data.Set
- Data.Tree
- Utils
- Utils.Containers
- Utils.Containers.Internal
- Utils.Containers
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.
Changes
Changelog for containers
package
0.6.5.1
Bug fixes
-
foldr'
andfoldl'
forMap
andSet
are now strict everywhere they should be, and we have detailed tests to make sure they stay that way. (Thanks, coot.) -
The
Ord IntSet
instance, which was broken in the last version, has been repaired.
New instance
- We now have
Ord a => Ord (Tree a)
(Thanks, Ericson2314.)
Testing fixes
- Thanks to konsumlamm and infinity0 for various bug fixes in the test suite.
0.6.4.1
Bug fixes
- Replace value-forcing variants of
compose
with lazy variants.- This brings
compose
closer in line with functions likeunion
andintersection
which don’t evaluate any map values. (Thanks, Simon Jakobi)
- This brings
Additions
-
Add
reverseTopSort
toData.Graph
(Thanks, James Parker) -
Expose
traverseMaybeWithKey
fromData.IntMap.{Lazy,Strict}
(Thanks, Simon Jakobi)
Other changes
-
Improvements to the testsuite: #663, #662 (Thanks, Bertram Felgenhauer)
-
Fix build with
stack test
(Thanks, Simon Jakobi)
0.6.3.1
Bug fixes
-
Fix
traverse
andtraverseWithKey
forIntMap
, which would previously produce invalidIntMap
s when the input contained negative keys (Thanks, Felix Paulusma). -
Fix the traversal order of various functions for
Data.IntMap
:traverseWithKey
,traverseMaybeWithKey
,filterWithKeyA
,minimum
,maximum
,mapAccum
,mapAccumWithKey
,mapAccumL
,mapAccumRWithKey
,mergeA
(Thanks, Felix Paulusma, Simon Jakobi).
Additions
-
Add
compose
forMap
andIntMap
(Thanks, Alexandre Esteves). -
Add
alterF
forSet
andIntSet
(Thanks, Simon Jakobi). -
Add
Data.IntSet.mapMonotonic
(Thanks, Javran Cheng). -
Add
instance Bifoldable Map
(Thanks, Joseph C. Sible).
Performance improvements
-
Make
(<*)
forData.Sequence
incrementally asymptotically optimal. This finally completes the task, begun in December 2014, of making all theApplicative
methods for sequences asymptotically optimal even when their results are consumed incrementally. Many thanks to Li-Yao Xia and Bertram Felgenhauer for helping to clean up and begin to document this rather tricky code. -
Speed up
fromList
and related functions inData.IntSet
,Data.IntMap
andData.IntMap.Strict
(Thanks, Bertram Felgenhauer). -
Use
count{Leading,Trailing}Zeros
inData.IntSet
internals (Thanks, Alex Biehl).
Other changes
-
Reduce usage of the
Forest
type synonym inData.Tree
(Thanks, David Feuer). -
Address a Core lint warning for
foldToMaybeTree
(Thanks, Matthew Pickering). -
Improve documentation (Thanks to Daniel Wagner, Johannes Waldmann, Steve Mao, Gabriel Greif, Jean-Baptiste Mazon, Ziyang Liu, Matt Renaud, Li-Yao Xia).
-
Improvements to the testsuite and benchmarks (Thanks, Bertram Felgenhauer, Simon Jakobi, Johannes Waldmann).
-
Canonicalise
Seq
’sMonoid
instance (Thanks, Fumiaki Kinoshita).
0.6.2.1
-
Add
disjoint
forMap
andIntMap
(Thanks, Simon Jakobi). -
Fix documentation bugs (Thanks, olligobber).
-
Fix unused imports (Thanks, Ben Gamari).
0.6.1.1
-
Fix Foldable instance for IntMap, which previously placed positively keyed entries before negatively keyed ones for
fold
,foldMap
, andtraverse
. -
Make strict
IntMap
merges strict. -
Make
Data.IntMap.Merge.Strict
tactics (exceptpreserveMissing
) strict. -
Add a strict
Data.Map.Merge.Strict.preserveMissing'
tactic. -
Make
stimes
for sequences work with 0 arguments, and make it more efficient. -
Speed up
cartesianProduct
forData.Set
. -
Speed up
Data.Set.isSubsetOf
,Data.Map.isSubmapOf
, andData.Set.disjoint
. -
Allow inlining for
Data.Sequence.traverseWithIndex
, making it faster thansequence
combined withmapWithIndex
. -
Produce more concise assembly from
maskW
. (Thanks, Mateusz Kowalczyk) -
Use
countLeadingZeros
to implementhighestBitMask
(Thanks, Dmitry Ivanov) -
Improve documentation. (Thanks to jwaldmann, Yuji Yamamoto, David Sanders, Alec Theriault, Vaibhav Sagar, Boro Sitnikovski, Morten Kolstad, Vados, Benjamin Web, Chris Martin, Alexandre Esteves).
-
Clean up packaging and testing. (Thanks, David Eichmann, Simon Jakobi, Oleg Grenrus, Andreas Klebinger)
0.6.0.1
- Released with GHC 8.6
New functions and class instances
-
Add
Data.Containers.ListUtils
offeringnub
-like functions. (Thanks to Gershom Bazerman for starting the process of writing these.) -
Add
Generic
andGeneric1
instances for keyData.Sequence.Internal
types:Node
,Digit
,Elem
, andFingerTree
.
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.
-
Data.IntMap
:insertWith'
,insertWithKey'
,fold
, andfoldWithKey
. -
Data.Map
:insertWith'
,insertWithKey'
,insertLookupWithKey'
,fold
, andfoldWithKey
.
The same has been done for the deprecated exports of showTree
and
showTreeWith
. These function remain available in the internal Debug
modules.
Changes to existing functions
- Generalize the types of
unions
andunionsWith
. (Thanks, jwaldmann.)
Performance improvements
-
Speed up folds and
traverse
on sequences. (Thanks, Donnacha Oisín Kidney.) -
Speed up
Data.Set.union
. (Thanks, Joachim Breitner.) -
Speed up several algorithms in
Data.Graph
a bit by using unboxed arrays where appropriate. -
Implement
Data.Graph.indegree
directly instead of taking the transpose and calculating itsoutdegree
. 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.
-
Improve
Data.Graph
documentation, and reorganize map and set documentation. -
Remove the
Data.Map.Lazy.Merge
andData.Map.Strict.Merge
modules. These were renamed and deprecated almost as soon as they were introduced.
0.5.11
- Released with GHC 8.4.
New functions and class instances
-
Add a
MonadFix
instance forData.Sequence
. -
Add a
MonadFix
instance forData.Tree
. -
Add
powerSet
,cartesianProduct
, anddisjointUnion
forData.Set
. (Thanks, Edward Kmett.) -
Add
disjoint
forData.Set
andData.IntSet
. (Thanks, Víctor López Juan.) -
Add
lookupMin
andlookupMax
toData.IntMap
. (Thanks, bwroga.) -
Add
unzip
andunzipWith
toData.Sequence
. Make unzipping build its results in lockstep to avoid certain space leaks. -
Add carefully optimized implementations of
sortOn
andunstableSortOn
toData.Sequence
. (Thanks, Donnacha Oisín Kidney.)
Changes to existing functions and features
-
Make
Data.Sequence.replicateM
a synonym forreplicateA
for post-AMPbase
. -
Rewrite the
IsString
instance head for sequences, improving compatibility with the list instance and also improving type inference. We used to haveinstance IsString (Seq Char)
Now we commit more eagerly with
instance a ~ Char => IsString (Seq a)
-
Make
>>=
forData.Tree
strict in the result of its second argument; being too lazy here is almost useless, and violates one of the monad identity laws. Specifically,return () >>= \_ -> undefined
should always beundefined
, but this was not the case. -
Harmonize laziness details for
minView
andmaxView
betweenData.IntMap
andData.Map
.
Performance improvement
- Speed up both stable and unstable sorting for
Data.Sequence
by (Thanks, Donnacha Oisín Kidney.)
Other changes
-
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.
-
Add Haddock
@since
annotations for changes made since version 0.5.4 (Thanks, Simon Jakobi.) -
Add a (very incomplete) test suite for
Data.Tree
. -
Add structural validity checks to the test suites for
Data.IntMap
andData.IntSet
(Thanks to Joachim Breitner for catching an error in a first draft.)
0.5.10.2
-
Released with GHC 8.2.
-
Use
COMPLETE
pragmas to declare complete sets of pattern synonyms forData.Sequence
. At last! -
Make
Data.IntMap.Strict.traverseWithKey
force the values before installing them in the result. Previously, this function could be used to produce anIntMap
containing undefined values. -
Fix strictness bugs in various rewrite rules for
Data.Map.Strict
andData.IntMap.Strict
. Previously, rules could unintentionally reduce strictness. The most important change in this regard is the elimination of rules rewriting*.Strict.map coerce
tocoerce
. To map a coercion over a structure for free, be sure to use the lazymap
orfmap
. It is possible to write rules that do a somewhat better job of this, but it turns out to be a bit messy. -
Optimize
Data.IntMap.restrictKeys
andData.IntMap.withoutKeys
. The semantic fix in 0.5.10.1 left them rather slow in certain cases. -
Speed up
size
forIntSet
andIntMap
(thanks, Mike Ledger!). -
Define a custom
liftA2
inApplicative
instances for base 4.10, and useliftA2
rather than<*>
whenever it may be beneficial. -
Add
liftA2
-relatedRULES
forData.Sequence
. -
Export non-deprecated versions of
showTree
andshowTreeWith
fromData.IntMap.Internal.Debug
.
0.5.10.1
-
Fix completely incorrect implementations of
Data.IntMap.restrictKeys
andData.IntMap.withoutKeys
. Make the tests for these actually run. (Thanks to Tom Smalley for reporting this.) -
Fix a minor bug in the
Show1
instance ofData.Tree
. This produced valid output, but with fewer parentheses thanShow
. (Thanks, Ryan Scott.) -
Add
MonadZip
instance forData.Sequence
. -
Remove meaningless stability annotations (Thanks, Simon Jakobi.)
0.5.9.2
- Backport bug fixes from 0.5.10.1
0.5.9.1
-
Add
merge
andmergeA
forData.IntMap
. -
Add instances for
Data.Graph.SCC
:Foldable
,Traversable
,Data
,Generic
,Generic1
,Eq
,Eq1
,Show
,Show1
,Read
, andRead1
. -
Add lifted instances (from
Data.Functor.Classes
) forData.Sequence
,Data.Map
,Data.Set
,Data.IntMap
, andData.Tree
. (Thanks to Oleg Grenrus for doing a lot of this work.) -
Properly deprecate functions in
Data.IntMap
long documented as deprecated. -
Rename several internal modules for clarity. Thanks to esoeylemez for starting this process.
-
Make
Data.Map.fromDistinctAscList
andData.Map.fromDistinctDescList
more eager, improving performance. -
Plug space leaks in
Data.Map.Lazy.fromAscList
andData.Map.Lazy.fromDescList
by manually inlining constant functions. -
Add
lookupMin
andlookupMax
toData.Set
andData.Map
as total alternatives tofindMin
andfindMax
. -
Add
!?
toData.Map
as a total alternative to!
. -
Avoid using
deleteFindMin
anddeleteFindMax
internally, preferring total functions instead. New implementations of said functions lead to slight performance improvements overall.
0.5.8.2
- 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.
-
Use
BangPatterns
throughout to reduce noise. This extension is now required to compilecontainers
. -
Improve QuickCheck properties taking arbitrary functions by using
Test.QuickCheck.Function.Fun
instead of evilShow
instances for functions. -
Expose several internal modules through Cabal (as requested by Edward Kmett). These remain completely unsupported.
New exports and instances
-
Add
alterF
,restrictKeys
, andwithoutKeys
toData.Map
andData.IntMap
. -
Add
take
,drop
,splitAt
,takeWhileAntitone
,dropWhileAntitone
, andspanAntitone
forData.Map
andData.Set
. Thanks to Cale Gibbard for suggesting these. -
Add
merge
,mergeA
, and associated merge tactics forData.Map
. Many thanks to Cale Gibbard, Ryan Trinkle, and Dan Doel for inspiring the merge idea and helping refine the interface. -
Add
traverseMaybeWithKey
,fromDescList
,fromDescListWith
,fromDescListWithKey
, andfromDistinctDescList
toData.Map
. -
Add
fromDescList
andfromDistinctDescList
toData.Set
. -
Add
Empty
,:<|
, and:|>
pattern synonyms forData.Sequence
. -
Add
adjust'
,(!?)
,lookup
,chunksOf
,cycleTaking
,insertAt
,deleteAt
,intersperse
,foldMapWithIndex
, andtraverseWithIndex
forData.Sequence
. -
Derive
Generic
andGeneric1
forData.Tree.Tree
,Data.Sequence.ViewL
, andData.Sequence.ViewR
. -
Add
foldTree
forData.Tree
. (Thanks, Daniel Wagner!)
Semantic changes
-
Make
Data.Sequence.splitAt
strict in its arguments. Previously, it returned a lazy pair. -
Fix completely erroneous definition of
length
forData.Sequence.ViewR
. -
Make
Data.Map.Strict.traverseWithKey
force result values before installing them in the new map. -
Make
drawTree
handle newlines better. (Thanks, recursion-ninja!)
Deprecations
-
All functions in
Data.Map
proper that have been documented as deprecated since version 0.5 or before now haveDEPRECATED
pragmas and will actually be removed after another cycle or two. -
Tree printing functions in
Data.Map
intended for library debugging are now deprecated. They will continue to be available for the foreseeable future in an internal module.
Performance changes
-
Substantially speed up
splitAt
,zipWith
,take
,drop
,fromList
,partition
,foldl'
, andfoldr'
forData.Sequence
. Special thanks to Lennart Spitzner for digging into the performance problems with previous versions offromList
and finding a way to make it really fast. Slightly optimizereplicateA
. Stoptraverse
from performing many unnecessaryfmap
operations. -
Most operations in
Data.Sequence
advertised as taking logarithmic time (including><
andadjust
) 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
fmap
withreverse
forData.Sequence
. -
Switch from hedge algorithms to divide-and-conquer algorithms for union, intersection, difference, and merge in both
Data.Map
andData.Set
. These algorithms are simpler, are known to be asymptotically optimal, and are faster according to our benchmarks. -
Speed up
adjust
forData.Map
. Allowmap
to inline, and define a custom(<$)
. This considerably improves mapping with a constant function. -
Remove non-essential laziness in
Data.Map.Lazy
implementation. -
Speed up deletion and alteration functions for
Data.IntMap
.
0.5.7.1 Dec 2015
-
Planned to bundle with GHC 8.0.1.
-
Add
IsString
instance toData.Sequence
. -
Define
Semigroup
instances forData.Map
,Data.Set
,Data.IntMap
,Data.IntSet
andData.Sequence
.
0.5.6.2 Dec 2014
-
Bundled with GHC 7.10.1.
-
Add role annotations for
Data.Map
andData.Set
. -
Add
IsList
instances forData.Map
,Data.Set
,Data.IntMap
andData.IntSet
. -
Several performance improvements for
Data.Sequence
. -
Add
Data.Sequence.fromFunction
andData.Sequence.fromArray
.
0.5.4.0 Jan 2014
-
Bundled with GHC 7.8.1.
-
The
Data.Map.fromList
andData.Set.fromList
now use linear-time algorithm if the input is sorted, without need to callfromDistinctAscList
. -
Implement indexing operations (
lookupIndex
,findIndex
,elemAt
,deletaAt
) forData.Set
too. -
Add
Applicative
andAlternative
instances forData.Sequence
. -
Add
foldMapWithKey
toData.Map
andData.IntMap
. -
Implement poly-kinded
Typeable
. -
Add
Functor
instance forData.Graph.SCC
. -
Add
Data.Map.splitRoot
andData.Set.splitRoot
.
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.Map
andData.IntMap
modules 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.
-
The
Data.IntSet
representation changed to store small sets using bits in anWord
. 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 exports
foldr,
foldr’,
foldland
foldl’`. -
Data.Set now exports
foldr,
foldr’,
foldland
foldl’`. -
Data.IntMap now exports
foldr,
foldr’,
foldl,
foldl’,
foldrWithKey,
foldrWithKey’,
foldlWithKeyand
foldlWithKey’`. -
Data.IntSet now exports
foldr,
foldr’,
foldland
foldl’`. -
Data.Map.foldWithKey
is no longer deprecated, although it is expected to be deprecated again in the future. -
There are now
NFData
instance forData.Map.Map
,Data.Set.Set
,Data.IntMap.IntMap
,Data.IntSet.IntSet
andData.Tree.Tree
.
0.4.1.0 Aug 2011
-
Bundled with GHC 7.2.1.
-
Data.Map
now exports new functionsfoldrWithKey'
andfoldlWithKey'
, which are strict variants offoldrWithKey
andfoldlWithKey
respectively. -
Data.IntMap
now exports new functionsinsertWith'
andinsertWithKey'
, which are strict variants ofinsertWith
andinsertWithKey
respectively.
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
insertLookupWithKey'
inData.Map
. -
The
foldWithKey
function inData.Map
has been deprecated in favour offoldrWithKey
.
0.3.0.0 Dec 2009
-
Bundled with GHC 6.12.1.
-
mapAccumRWithKey
has been added toData.IntMap
. -
A
Traversable
instance has been added toData.IntMap.IntMap
. -
The types of
Data.IntMap.intersectionWith
andData.IntMap.intersectionWithKey
have been changed fromintersectionWith :: (a -> b -> a) -> IntMap a -> IntMap b -> IntMap a
intersectionWithKey :: (Key -> a -> b -> a) -> IntMap a -> IntMap b -> IntMap a
tointersectionWith :: (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.findMin
andData.IntMap.findMax
have been changed fromfindMin :: IntMap a -> a
findMax :: IntMap a -> a
tofindMin :: IntMap a -> (Int,a)
findMax :: IntMap a -> (Int,a)
-
Data.Map
now exportsmapAccumRWithKey
,foldrWithKey
,foldlWithKey
andtoDescList
. -
Data.Sequence
now exportsreplicate
,replicateA
,replicateM
,iterateN
,unfoldr
,unfoldl
,scanl
,scanl1
,scanr
,scanr1
,tails
,inits
,takeWhileL
,takeWhileR
,dropWhileL
,dropWhileR
,spanl
,spanr
,breakl
,breakr
,partition
,filter
,sort
,sortBy
,unstableSort
,unstableSortBy
,elemIndexL
,elemIndicesL
,elemIndexR
,elemIndicesR
,findIndexL
,findIndicesL
,findIndexR
,findIndicesR
,foldlWithIndex
,foldrWithIndex
,mapWithIndex
,zip
,zipWith
,zip3
,zipWith3
,zip4
andzipWith4
.
0.2.0.0 Nov 2008
-
Bundled with GHC 6.10.1.
-
Various result type now use
Maybe
rather than allowing anyMonad
.
0.1.0.0 Nov 2007
-
Bundled with GHC 6.8.1.
-
Initial split off from GHC base.