5 years agoAdd test properties for splitRoot.
Ryan Newton [Wed, 4 Dec 2013 00:57:16 +0000 (19:57 -0500)] 
Add test properties for splitRoot.
Remove the ordering guarantee for IntSet and IntMap.
(Negative numbers screw it up.)

5 years agoDisable apparently rotted test cases. 10/10 test suites pass.
Ryan Newton [Wed, 4 Dec 2013 00:49:12 +0000 (19:49 -0500)] 
Disable apparently rotted test cases.  10/10 test suites pass.

5 years agoSwitch to in-order splitRoot. Provide the same for IntSet/IntMap.
Ryan Newton [Tue, 3 Dec 2013 22:10:26 +0000 (17:10 -0500)] 
Switch to in-order splitRoot.  Provide the same for IntSet/IntMap.

5 years agoAdd splitRoot examples to comments.
Ryan Newton [Tue, 3 Dec 2013 04:47:26 +0000 (23:47 -0500)] 
Add splitRoot examples to comments.

5 years agoRename to splitRoot. Add the same for Sets and expose it.
Ryan Newton [Tue, 3 Dec 2013 04:27:44 +0000 (23:27 -0500)] 
Rename to splitRoot.  Add the same for Sets and expose it.

5 years agoChange the split method to return a list, as per the discussion on the list.
Ryan Newton [Tue, 3 Dec 2013 04:15:05 +0000 (23:15 -0500)] 
Change the split method to return a list, as per the discussion on the list.
Bump version number to to reflect change.

5 years agoAdd splitTree to Map.Base. Not exposed publically yet.
Ryan Newton [Mon, 7 Oct 2013 04:13:59 +0000 (00:13 -0400)] 
Add splitTree to Map.Base.  Not exposed publically yet.

6 years agoAvoid dependency on Applicative (ST s) instance ...
Milan Straka [Mon, 7 Oct 2013 16:39:45 +0000 (18:39 +0200)] 
Avoid dependency on Applicative (ST s) instance ...

... present only in GHC 7.2+.

6 years agoRename join to link ...
Milan Straka [Mon, 7 Oct 2013 13:15:59 +0000 (15:15 +0200)] 
Rename join to link ...

... to get ready for AMP in GHC 7.10 and silence warning in GHC 7.8.

Keeping join would be quite a hassle. We need to silence warning in GHC
7.8, but we cannot say
  import Prelude hiding (....., join)
because join is not exported untiil 7.10. We also do not want to
explicitly list imported names from Prelude, because there are many
(I tried and stopped after a dozen).

We could silence the amp warning in GHC 7.7 - GHC 7.9 and have
conditional Prelude import for base >= 4.8, hiding join in one of them.
Nevertheless, this is too many problems compared to renaming an internal
join function to link.

6 years agoUse finiteBitSize with base >= 4.7...
Milan Straka [Mon, 7 Oct 2013 13:14:44 +0000 (15:14 +0200)] 
Use finiteBitSize with base >= 4.7...

... and silence warning in GHC 7.8.

6 years agoAdd Functor and Applicative instances for SetM...
Milan Straka [Mon, 7 Oct 2013 13:13:00 +0000 (15:13 +0200)] 
Add Functor and Applicative instances for SetM...

... to get ready for AMP proposal in GHC 7.10 and silence warning
in GHC 7.8.

6 years agoMerge pull request #32 from alphaHeavy/scc-functor
Milan Straka [Thu, 12 Sep 2013 21:16:43 +0000 (14:16 -0700)] 
Merge pull request #32 from alphaHeavy/scc-functor

Add Functor instance to Data.Graph.SCC

6 years agoAdd Functor instance to Data.Graph.SCC
Nathan Howell [Tue, 10 Sep 2013 22:46:51 +0000 (15:46 -0700)] 
Add Functor instance to Data.Graph.SCC

6 years agoBump version number to containers-
Johan Tibell [Wed, 4 Sep 2013 17:03:50 +0000 (10:03 -0700)] 
Bump version number to

6 years agoImport warning fix for GHC 7.7
Johan Tibell [Wed, 4 Sep 2013 17:02:28 +0000 (10:02 -0700)] 
Import warning fix for GHC 7.7

The unused import check is now more agressive so

    import Prelude hiding (foldr)

creates a warning if nothing from the Prelude is used.

6 years agoMerge GHC HEAD
Johan Tibell [Fri, 30 Aug 2013 21:06:54 +0000 (14:06 -0700)] 

6 years agoRemove redundant import
Johan Tibell [Fri, 30 Aug 2013 18:32:45 +0000 (11:32 -0700)] 
Remove redundant import

6 years agoBump version number to
Johan Tibell [Fri, 30 Aug 2013 18:29:35 +0000 (11:29 -0700)] 
Bump version number to

6 years agoStrict modules only strict in values inserted
Johan Tibell [Fri, 30 Aug 2013 18:26:51 +0000 (11:26 -0700)] 
Strict modules only strict in values inserted

Before all value arguments would be evaluated, now they are only
evaluated if they are actually inserted into the map.

6 years agoMerge tag 'v0.5.2.1' of git:// into ghc-head
Herbert Valerio Riedel [Fri, 30 Aug 2013 10:46:52 +0000 (12:46 +0200)] 
Merge tag 'v0.5.2.1' of git:// into ghc-head

6 years agoOptimize Map.foldMapWithKey.
Milan Straka [Tue, 2 Jul 2013 19:25:31 +0000 (21:25 +0200)] 
Optimize Map.foldMapWithKey.

Use optimalizations from foldMap and traverseWithKey -- associativity
and test for leaves.

6 years agoMerge pull request #24 from ekmett/master
Milan Straka [Tue, 2 Jul 2013 19:21:32 +0000 (12:21 -0700)] 
Merge pull request #24 from ekmett/master

Added `foldMapWithKey`.

6 years agoImprove Traversable instance of Map.
Milan Straka [Sun, 9 Jun 2013 11:38:09 +0000 (13:38 +0200)] 
Improve Traversable instance of Map.

Similarly to Foldable instance (commit #29d3fbcc), add a special case in
traverseWithKey when traversing a leaf. In this case, the Tips under the
leaf are not traversed. The speedup is 25%.

See the log of the mentioned commit #29d3fbcc for discussion of
alternative implementations.

6 years agoImprove Foldable instances.
Milan Straka [Sun, 9 Jun 2013 11:23:22 +0000 (13:23 +0200)] 
Improve Foldable instances.

- Employ implementation techniques used in normal folds, i.e.,
  * Inline fold and foldMap
  * Capture the function argument and do not pass it in the worker

  The Foldable.fold is only INLINABLE, because mappend and mempty depend
  only on Monoid dictionary and are fully specified when Foldable.fold
  is specialized. On the contrary, INLINE foldMap to allow the mapping
  function to be inlined.

  This improves complexity by ~60%.

- For Set and Map, add special case for a leaf. This avoids calling
  mempty for the Tips and mappending them with the value in the leaf.
  The improvement is further ~35% for Set and ~30% for Map.

  The leaves are recognized by comparing size of the tree to one. They
  could also be recognized by comparing left and right subtree to Tip,
  but that is slower.

  Also, cases when only left or right subtree is Tip could be
  recognized, but the implementation is still slower than recognizing
  only leaves using the tree size. It can be proved that at least 66% of
  Tips are under leaf nodes, so we miss at most one third of Tips in
  current implementation and do not cause so much code growth.

6 years agoMove the INLINE pragma after the function.
Milan Straka [Sun, 9 Jun 2013 09:36:43 +0000 (11:36 +0200)] 
Move the INLINE pragma after the function.

All other INLINEs are after function bodies.

6 years agoMerge pull request #25 from dreixel/master
Milan Straka [Tue, 12 Feb 2013 16:38:33 +0000 (08:38 -0800)] 
Merge pull request #25 from dreixel/master

Use the new Typeable class in GHC >= 7.7

6 years agoDo not use Typeable1..3 in GHC >= 7.7
Jose Pedro Magalhaes [Tue, 12 Feb 2013 13:21:39 +0000 (13:21 +0000)] 
Do not use Typeable1..3 in GHC >= 7.7

6 years agoImplement poly-kinded Typeable
Jose Pedro Magalhaes [Thu, 7 Feb 2013 14:00:21 +0000 (14:00 +0000)] 
Implement poly-kinded Typeable

This patch makes the Data.Typeable.Typeable class work with arguments of any
kind. In particular, this removes the Typeable1..7 class hierarchy, greatly
simplyfing the whole Typeable story. Also added is the AutoDeriveTypeable
language extension, which will automatically derive Typeable for all types and
classes declared in that module. Since there is now no good reason to give
handwritten instances of the Typeable class, those are ignored (for backwards
compatibility), and a warning is emitted.

The old, kind-* Typeable class is now called OldTypeable, and lives in the
Data.OldTypeable module. It is deprecated, and should be removed in some future
version of GHC.

6 years agoAdded `foldMapWithKey`.
Edward Kmett [Tue, 25 Dec 2012 10:57:40 +0000 (05:57 -0500)] 
Added `foldMapWithKey`.

6 years agoRemove references to Report and FFI from LICENSE
Milan Straka [Sun, 16 Dec 2012 20:19:39 +0000 (21:19 +0100)] 
Remove references to Report and FFI from LICENSE

The LICENSE claimed that the source code of containers comes from three
* from GHC project, licensed under GHC license
* from Haskell Report, licensed under Haskell Report license
* from FFI, licensed under FFT license
It did not specify which fragments of code came from where. That caused
confusion among the containers users.

Me (Milan Straka) and Johan Tibell believe that in the containers source
there is no code derived from Haskell Report, and that in the containers
source there is no code derived from FFI, so I removed the references to
Haskell Report and FFI from the LICENSE.

Now the LICENSE file contains only the GHC license, without any

6 years agoBump version number to containers-
Johan Tibell [Thu, 13 Dec 2012 16:52:58 +0000 (08:52 -0800)] 
Bump version number to

6 years agoMore style clean-ups
Johan Tibell [Thu, 13 Dec 2012 16:52:13 +0000 (08:52 -0800)] 
More style clean-ups

6 years agoAlways import shifts from BitUtil
Johan Tibell [Thu, 13 Dec 2012 16:47:17 +0000 (08:47 -0800)] 
Always import shifts from BitUtil

6 years agoStyle improvements
Johan Tibell [Thu, 13 Dec 2012 16:40:00 +0000 (08:40 -0800)] 
Style improvements

6 years agoRemove old copy of highestBitMask
Johan Tibell [Thu, 13 Dec 2012 16:34:10 +0000 (08:34 -0800)] 
Remove old copy of highestBitMask

This necessitated some code rearrangement.

6 years agoBump version number to
Johan Tibell [Thu, 13 Dec 2012 01:08:17 +0000 (17:08 -0800)] 
Bump version number to

6 years agohighestBitMap: clean-room reimplementation
Johan Tibell [Thu, 13 Dec 2012 00:55:55 +0000 (16:55 -0800)] 
highestBitMap: clean-room reimplementation

Replaced the previous implementation due to licensing concerns. The new
implementation is a clean-room reimplementation by Clark Gaebel, based
on the public domain implementation at

6 years agoRemove unnecessary Ord constraint in
Milan Straka [Mon, 26 Nov 2012 08:47:50 +0000 (09:47 +0100)] 
Remove unnecessary Ord constraint in

6 years agoMerge pull request #23 from ekmett/master
Milan Straka [Sun, 25 Nov 2012 17:19:56 +0000 (09:19 -0800)] 
Merge pull request #23 from ekmett/master

Allowing gunfold for Map, IntMap, Set, and IntSet.

6 years agoAllow `gunfold' on Map, IntMap, Set, and IntSet using virtual constructors.
Edward Kmett [Sun, 25 Nov 2012 01:26:52 +0000 (20:26 -0500)] 
Allow `gunfold' on Map, IntMap, Set, and IntSet using virtual constructors.

* Original Proposal:

7 years agoFix forgotten documentation of Int{Map,Set}.delete{Min,Max}.
Milan Straka [Wed, 21 Nov 2012 14:25:26 +0000 (15:25 +0100)] 
Fix forgotten documentation of Int{Map,Set}.delete{Min,Max}.

These functions used to call error on empty map, but do not so since

7 years agoProvide explicit definition for <*> instead of using ap.
Milan Straka [Wed, 14 Nov 2012 20:50:33 +0000 (21:50 +0100)] 
Provide explicit definition for <*> instead of using ap.

7 years agoModify imports so that Alternative can be used unqualified.
Milan Straka [Wed, 14 Nov 2012 20:50:05 +0000 (21:50 +0100)] 
Modify imports so that Alternative can be used unqualified.

7 years agoApplicative and Alternative instances for Seq
Taneb [Wed, 14 Nov 2012 12:10:54 +0000 (12:10 +0000)] 
Applicative and Alternative instances for Seq

The Alternative instance is basically the same as the pre-existing
MonadPlus instance, except names are qualified (empty clashes with
empty). The Applicative instance is similar to the Monad instance, and
relies on ap.

7 years agoFix the description of deprecated functions.
Milan Straka [Sun, 11 Nov 2012 21:26:33 +0000 (22:26 +0100)] 
Fix the description of deprecated functions.

They are not "obsolete", the are "deprecated".

7 years agoAdd test for deprecated methods of Data.Map and Data.IntMap.
Milan Straka [Sun, 11 Nov 2012 10:09:51 +0000 (11:09 +0100)] 
Add test for deprecated methods of Data.Map and Data.IntMap.

These properties cannot be tested in either map-properties or
intmap-properties, as these modules are designed to work with the .Lazy
and .Strict modules.

7 years agoAllow compilation of Data.IntSet.Base without cabal.
Milan Straka [Sun, 11 Nov 2012 09:39:06 +0000 (10:39 +0100)] 
Allow compilation of Data.IntSet.Base without cabal.

Use generic definition of bitcount when MIN_VERSION_base is undefined.

7 years agoFix module references in the documentation.
Milan Straka [Sun, 11 Nov 2012 08:56:58 +0000 (09:56 +0100)] 
Fix module references in the documentation.

The right format is "Data.Map.Lazy", not 'Data.Map.Lazy'.

7 years agoRevert to the original strictness properties of...
Milan Straka [Sat, 10 Nov 2012 20:47:36 +0000 (21:47 +0100)] 
Revert to the original strictness properties of...

deprecated functions, notably
* Data.Map.insertWith'
* Data.Map.insertWithKey'
* Data.Map.insertLookupWithKey'
* Data.IntMap.insertWith'
* Data.IntMap.insertWithKey'
The original behaviour was _not_ to evaluate the given value. Some
people are depending on this, using insertWith' as a strict version of
adjust -- undefined has to be passed as a value in that case.

7 years agoReorder the tests in set-properties.
Milan Straka [Sun, 11 Nov 2012 14:45:49 +0000 (15:45 +0100)] 
Reorder the tests in set-properties.

HUnit tests first, then QuickCheck properties.

7 years agoImprove the documentation of indexing API of Map and Set.
Milan Straka [Sun, 11 Nov 2012 14:43:01 +0000 (15:43 +0100)] 
Improve the documentation of indexing API of Map and Set.

* Explain the definition of index in every method.
* Point out the fact when 'error' can be called.

7 years agoImplement indexing operations on 'Set'
Patrick Palka [Sun, 4 Nov 2012 19:49:24 +0000 (14:49 -0500)] 
Implement indexing operations on 'Set'

7 years agoRemove from docs that hedge-union is faster in (big `union` small) case.
Milan Straka [Sun, 11 Nov 2012 14:57:16 +0000 (15:57 +0100)] 
Remove from docs that hedge-union is faster in (big `union` small) case.

As measured by SetOperations-Set.hs and SetOperations-Map.hs benchmarks,
it is not the case. Depending on the relative order of elements in the
set/map, both (big `union` small) and (small `union` big) cases can be
faster than the other.

7 years agoBump version number to
Johan Tibell [Mon, 8 Oct 2012 23:35:43 +0000 (16:35 -0700)] 
Bump version number to

7 years agoAnnotate IntSet.* with Key; move type Key = Int to IntSet.Base
Liyang HU [Tue, 2 Oct 2012 01:44:44 +0000 (10:44 +0900)] 
Annotate IntSet.* with Key; move type Key = Int to IntSet.Base

7 years agoAnnotate IntMap.fold*WithKey with correct Key synonym
Liyang HU [Tue, 2 Oct 2012 01:29:45 +0000 (10:29 +0900)] 
Annotate IntMap.fold*WithKey with correct Key synonym

7 years ago-Wall police
Johan Tibell [Thu, 20 Sep 2012 09:28:41 +0000 (11:28 +0200)] 
-Wall police

7 years agoRemove use of defaultMainWithOpts from test suite
Johan Tibell [Thu, 20 Sep 2012 09:20:05 +0000 (11:20 +0200)] 
Remove use of defaultMainWithOpts from test suite

defaultMainWithOpts doesn't allow us to pass additional flags, such as
--jxml, on the command line. The old behavior (i.e. setting the number
of tests) can still be achieved like so:

cabal test --test-option=-a500 \

7 years agoChange bitcount in IntSet to use popCount
Nicolas Trangez [Sat, 15 Sep 2012 09:18:08 +0000 (11:18 +0200)] 
Change bitcount in IntSet to use popCount

7 years agoAdd test to validate bitcount implementation using popCount
Nicolas Trangez [Sat, 15 Sep 2012 09:17:41 +0000 (11:17 +0200)] 
Add test to validate bitcount implementation using popCount

7 years agoImprove {Map,Set}.fromList.
Milan Straka [Thu, 30 Aug 2012 22:22:21 +0000 (00:22 +0200)] 
Improve {Map,Set}.fromList.

While the input is sorted, use implementation of fromDistinctAscList.
When first unordered key is found, switch to the general fromList
implementation, which inserts the rest of the keys to the already
constructed tree.

This gives a huge advantage for sorted inputs. The inplementation is
5% (for Map) and 0% (for Set) slower than fromDistinctAscList in that case.
The larger overhead for Map is probably because of the the pair unpacking.

For input list of size 2^12, the fromList is 10 times faster if the input
is sorted.

The fromList could be further improved by trying to handle semi-sorted
inputs. But currently I have no idea how to do it efficiently.

7 years agoAdd fromList with keys in descending order.
Milan Straka [Thu, 30 Aug 2012 22:19:03 +0000 (00:19 +0200)] 
Add fromList with keys in descending order.

Used to compare fromList on ordered and unordered inputs, as
a linear-time algorithm is used in former case.

7 years agoAllow running only specified benchmarks.
Milan Straka [Thu, 30 Aug 2012 21:39:11 +0000 (23:39 +0200)] 
Allow running only specified benchmarks.

7 years agoFix fromDistinctAscList benchmark.
Milan Straka [Thu, 30 Aug 2012 21:33:27 +0000 (23:33 +0200)] 
Fix fromDistinctAscList benchmark.

It used fromAscList instead fromDistinctAscList.

7 years agoImprove {Map,Set}.fromDistinctAscList.
Milan Straka [Thu, 30 Aug 2012 15:28:49 +0000 (17:28 +0200)] 
Improve {Map,Set}.fromDistinctAscList.

Benchmarks show 42% improvement for Map and 39% improvement for Set.

The new implementation builds the map on the fly, without needing to
know the number of elements in the list. It proceeds by building a map
of size 2^1-1, 2^2-1, 2^3-1, .... When the input list is empty, there is
at most log N trees left. These are joined from the smallest to the

7 years agoAdd fromList tests to Map and IntMap.
Milan Straka [Thu, 30 Aug 2012 15:26:32 +0000 (17:26 +0200)] 
Add fromList tests to Map and IntMap.

This test makes sure that fromList, fromAscList and
fromDistinctAscList returns the same map.

7 years agoAdd fromList variants to benchmark.
Milan Straka [Thu, 30 Aug 2012 14:51:57 +0000 (16:51 +0200)] 
Add fromList variants to benchmark.

Also set the size of inputs for various containers to the same value 2^12.

7 years agoForce the components of returned pairs strict-tuples
Johan Tibell [Fri, 24 Aug 2012 23:56:12 +0000 (16:56 -0700)] 
Force the components of returned pairs

Some functions, like partition, return a pair of values. Before this
change these functions would do almost no work and return immediately,
due to suspending most of the work in closures. This could cause space

Closes #14.

7 years agoFix haddock links to modules
Johan Tibell [Wed, 1 Aug 2012 23:22:31 +0000 (16:22 -0700)] 
Fix haddock links to modules

7 years agoMerge pull request #11 from thomie/master
Milan Straka [Fri, 11 May 2012 18:52:14 +0000 (11:52 -0700)] 
Merge pull request #11 from thomie/master

Data.Graph: refer to a better version of the King and Launchbury article

7 years agoRefer to article with less spelling errors (open access, same content)
Thomas Miedema [Fri, 11 May 2012 15:35:21 +0000 (18:35 +0300)] 
Refer to article with less spelling errors (open access, same content)

7 years agoMerge changes release by GHC HQ as ghc-7.6 containers- ghc-7.6.1-release ghc-7.6.2-release ghc-7.6.3-release
Johan Tibell [Thu, 3 May 2012 15:29:06 +0000 (08:29 -0700)] 
Merge changes release by GHC HQ as


7 years agoAdd tests and benchmarks to sdist.
Milan Straka [Mon, 30 Apr 2012 12:29:46 +0000 (14:29 +0200)] 
Add tests and benchmarks to sdist.

7 years agoAdd comment to tests/Makefile.
Milan Straka [Mon, 30 Apr 2012 12:28:30 +0000 (14:28 +0200)] 
Add comment to tests/Makefile.

Add comment to tests/Makefile that users should use cabal to build and
run tests.

7 years agoRemove type of local 'go' function in query methods of Set and Map.
Milan Straka [Sat, 28 Apr 2012 14:51:13 +0000 (16:51 +0200)] 
Remove type of local 'go' function in query methods of Set and Map.

The resulting implementations are a bit faster, and there seems to be no
increased heap-allocation. I will confirm this by examining GHC memory

7 years agoDefine Map.{union,difference,intersection}WithKey using mergeWithKey.
Milan Straka [Sat, 28 Apr 2012 14:36:31 +0000 (16:36 +0200)] 
Define Map.{union,difference,intersection}WithKey using mergeWithKey.

The resulting implementations are approximately 40-50% faster, although
for some input data the performance is worse. This happens
* in unionWithKey, if the data are disjunct: 15% slowdown
* in differenceWithKey, as now we recurse over the first tree and not
  the second. The slowdown happens also only for disjunct data: 30%.

See the SetOperations benchmark for yourself if you are interested.

7 years agoAdd Map.mergeWithKey.
Milan Straka [Sat, 28 Apr 2012 14:35:51 +0000 (16:35 +0200)] 
Add Map.mergeWithKey.

7 years agoRemove redundant parenthesis.
Milan Straka [Fri, 27 Apr 2012 11:34:48 +0000 (13:34 +0200)] 
Remove redundant parenthesis.

7 years agoFix warnings, formatting.
Milan Straka [Fri, 27 Apr 2012 09:58:55 +0000 (11:58 +0200)] 
Fix warnings, formatting.

7 years agoImprove {Map, Set}.union.
Milan Straka [Fri, 27 Apr 2012 09:51:48 +0000 (11:51 +0200)] 
Improve {Map, Set}.union.

Instead of having a special case set `union` set_of_size_1 in union,
move it to hedgeUnion, so it can be used recursively. Benchmark shows up
to 30% speedup.

7 years agoImprove {Map, Set}.intersection.
Milan Straka [Fri, 27 Apr 2012 09:30:13 +0000 (11:30 +0200)] 
Improve {Map, Set}.intersection.

Use the hedge-intersection algorithm, similar to hedge-union and

Depending on inputs, this causes up to 80% speedup.

Also remove Set.splitLookup, which was used only to define intersection.

7 years agoOnce again revert argument capturing by local 'go' function.
Milan Straka [Fri, 27 Apr 2012 09:12:07 +0000 (11:12 +0200)] 
Once again revert argument capturing by local 'go' function.

At last I found an example, where capturing the argument in local 'go'
function in 'member' causes increased heap-allocation. It is caused by
'go' function floating out of 'member' and allocating a dictionary and
the key argument.

This happens only with Map and Set methods. Therefore in IntMap and IntSet,
'go' function still captures the argument (and GHC shows no increased
heap-allocation as a result of that).

7 years agoImprove heap-allocation in mergeWithKey'.
Milan Straka [Fri, 27 Apr 2012 08:36:28 +0000 (10:36 +0200)] 
Improve heap-allocation in mergeWithKey'.

Avoid allocating the closure for local function 'merge'.

7 years agoAdd fromSet method.
Milan Straka [Wed, 25 Apr 2012 16:54:04 +0000 (18:54 +0200)] 
Add fromSet method.

Following a proposal on libraries@..., we add fromSet method to Map and
  Map.fromSet :: (k -> a) -> Set k -> Map k a
  IntMap.fromSet :: (Key -> a) -> IntSet -> IntMap a
It is implemented using exported Set and IntSet constructors.

Map.fromSet is trivial, as Map and Set have the same structure.

The IntMap.fromSet implementation is more complicated, as IntSet uses
dense representation of several last leves of the trie.

7 years agoFix warnings.
Milan Straka [Wed, 25 Apr 2012 16:45:59 +0000 (18:45 +0200)] 
Fix warnings.

7 years agoImprove manual makefile for tests.
Milan Straka [Tue, 24 Apr 2012 16:05:40 +0000 (18:05 +0200)] 
Improve manual makefile for tests.

Leave dependencies on GHC instead of make.

7 years agoImprove {Map, IntMap}.keysSet.
Milan Straka [Tue, 24 Apr 2012 15:32:04 +0000 (17:32 +0200)] 
Improve {Map, IntMap}.keysSet.

The keysSet method is now implemented using the exported constructors of
Data.{Set, IntSet}.Base.

The implementation of Map.keysSet is trivial, as Set and Map use same
tree structure.

The implementation of IntMap.keysSet is slightly complicated, because of
the dense representation of IntSet, where several last levels of the
tree are flatten into a bitmap.

7 years agoFactor Data.IntSet into Data.IntSet.Base and Data.IntSet.
Milan Straka [Tue, 24 Apr 2012 14:58:05 +0000 (16:58 +0200)] 
Factor Data.IntSet into Data.IntSet.Base and Data.IntSet.

Similarly to Map and IntMap, the whole functionality is in
Data.IntSet.Base. The Data.IntSet module just reexports methods from

The only difference between Data.IntSet.Base and Data.IntSet is that
Data.IntSet.Base exports the constructors of IntSet data type. This will
be used in IntMap to define efficient versions of keysSet and fromSet.

7 years agoFactor Data.Set into Data.Set.Base and Data.Set.
Milan Straka [Tue, 24 Apr 2012 14:45:45 +0000 (16:45 +0200)] 
Factor Data.Set into Data.Set.Base and Data.Set.

Similarly to Map and IntMap, the whole functionality is in
Data.Set.Base. The Data.Set module just reexports methods from Data.Set.

The only difference between Data.Set.Base and Data.Set is that
Data.Set.Base exports the constructors of Set data type. This will be
used in Map to define efficient versions of keysSet and fromSet.

7 years agoAdd lookupLT, lookupGT, lookupLE, lookupGE methods.
Milan Straka [Tue, 24 Apr 2012 14:23:13 +0000 (16:23 +0200)] 
Add lookupLT, lookupGT, lookupLE, lookupGE methods.

Following the proposal on libraries@..., we add lookupLT, lookupGT,
lookupLE, lookupGE methods to Set, Map, IntSet and IntMap.

The implementations were chosen using the LookupLE benchmark.
Current implementations do not heap-allocate apart from the result.

Corresponding tests are added. The test suites for Set and IntSet
now use HUnit too.

7 years agoOn 32-bit architectures, improve highestBitMask.
Milan Straka [Tue, 24 Apr 2012 14:20:29 +0000 (16:20 +0200)] 
On 32-bit architectures, improve highestBitMask.

Even on 32-bit architectures, bit shift of size 32 was performed.

7 years agoImprove one of the benchmarked methods: lookupGE4.
Milan Straka [Mon, 23 Apr 2012 16:29:50 +0000 (18:29 +0200)] 
Improve one of the benchmarked methods: lookupGE4.

7 years agoChange ASCII character for underline from ^ to ~.
Milan Straka [Mon, 23 Apr 2012 14:44:01 +0000 (16:44 +0200)] 
Change ASCII character for underline from ^ to ~.

We use the following:
  -- [Note: Some superimportant message]
  -- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Unfortunately, -- ^ is wrongly picked up by Haddock.
Instead we now use
  -- [Note: Some superimportant message]
  -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

7 years agoChange INLINE to INLINABLE on methods using Ord.
Milan Straka [Mon, 23 Apr 2012 13:54:13 +0000 (15:54 +0200)] 
Change INLINE to INLINABLE on methods using Ord.

As mentioned previously, INLINE - INLINABLE method chain does not result
in specialization, it has to be INLINABLE - INLINABLE.

7 years agoAdd benchmark of lookupGE to choose best implementation.
Milan Straka [Mon, 23 Apr 2012 08:57:45 +0000 (10:57 +0200)] 
Add benchmark of lookupGE to choose best implementation.

Most of the code is by Twan van Laarhoven, thanks.

7 years agoFix warnings.
Milan Straka [Mon, 23 Apr 2012 08:53:49 +0000 (10:53 +0200)] 
Fix warnings.

7 years agoMove SetOperations benchmark to its own subdirectory.
Milan Straka [Mon, 23 Apr 2012 08:02:12 +0000 (10:02 +0200)] 
Move SetOperations benchmark to its own subdirectory.

Also improve the infrastructure to handle benchmarks in different

7 years agoManually inline {Map,IntMap}.map.
Milan Straka [Sun, 22 Apr 2012 16:06:21 +0000 (18:06 +0200)] 
Manually inline {Map,IntMap}.map.

7 years agoInline {Map,Set}.fold* when 2 arguments are given.
Milan Straka [Sun, 22 Apr 2012 16:00:43 +0000 (18:00 +0200)] 
Inline {Map,Set}.fold* when 2 arguments are given.

Inlining folds when 2 arguments are given is consistent
with Prelude.foldr and {IntMap,IntSeT}.fold*.

7 years agoRemove obsolete comment about deleteWith.
Milan Straka [Sun, 22 Apr 2012 15:54:00 +0000 (17:54 +0200)] 
Remove obsolete comment about deleteWith.

DeleteWith is no longer method of any collection.