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.

7 years agoImprove heap-allocation by adding explicit type signatures.
Milan Straka [Sun, 22 Apr 2012 15:48:29 +0000 (17:48 +0200)] 
Improve heap-allocation by adding explicit type signatures.

When a local 'go' function is using methods from Ord dictionary,
this dictionary is heap-allocated at the entry to the outer function.
If it is given explicit type mentioning the Ord class, the dictionary is
passed on the stack, decreasing heap allocation.

7 years agoImprove Map indexing functions.
Milan Straka [Sat, 21 Apr 2012 20:14:42 +0000 (22:14 +0200)] 
Improve Map indexing functions.

* Manually inline findIndex and deleteAt to avoid allocation.

* Give type to local 'go' function of findIndex and lookupIndex
  to avoid heap allocation.

7 years agoImprove query functions of Map and Set.
Milan Straka [Sat, 21 Apr 2012 19:41:22 +0000 (21:41 +0200)] 
Improve query functions of Map and Set.

As documented in the Note: Local 'go' functions and capturing,
it is safe to use captured key argument in query functions.

Also, in order to decrease allocation, the query functions in Map
are manually inlined, so 'member' does not have to call 'lookup'
and heap-allocate 'Just a'.

Tests of query functions are much improved too.

7 years agoInsert missing space in an error message.
Milan Straka [Sat, 21 Apr 2012 19:37:14 +0000 (21:37 +0200)] 
Insert missing space in an error message.

7 years agoPrevent multiple warnings.
Milan Straka [Sat, 21 Apr 2012 18:25:00 +0000 (20:25 +0200)] 
Prevent multiple warnings.

Prevent multiple warnings caused by unsuccessful SpecConstr pass.
We do so by not inlining helper testing function.

7 years agoAdd empty line between Notes.
Milan Straka [Fri, 20 Apr 2012 18:26:47 +0000 (20:26 +0200)] 
Add empty line between Notes.

7 years agoInline Int{Map,Set}.{null, empty, singleton}.
Milan Straka [Fri, 20 Apr 2012 16:32:18 +0000 (18:32 +0200)] 
Inline Int{Map,Set}.{null, empty, singleton}.

These are probably inlined anyway, but we explicitly INLINE
them in Map and Set, so we do also in IntMap and IntSet for consistency.

7 years agoImprove query functions of IntMap and IntSet.
Milan Straka [Fri, 20 Apr 2012 16:18:55 +0000 (18:18 +0200)] 
Improve query functions of IntMap and IntSet.

As documented in the Note: Local 'go' functions and capturing,
it is safe to use captured key argument in query functions.

Also, in order to decrease allocation, the query functions in IntMap
are manually inlined, so 'member' does not have to call 'lookup'
and heap-allocate 'Just a'.

Tests of query functions are much improved too.

7 years agoReorder the data constructors of Map and Set.
Milan Straka [Fri, 20 Apr 2012 16:04:54 +0000 (18:04 +0200)] 
Reorder the data constructors of Map and Set.

The order of constructors has clearly no effect on corectness.

Inspired by the change in order of constructors of IntMap and IntSet,
the benchmark shows slight improvement when changing the data
constructors from Tip | Bin to Bin | Tip.

Also, we now consistently use the same order of constructors in all
these structures: Map, Set, IntMap, IntSet.

7 years agoImprove programming documentation.
Milan Straka [Fri, 20 Apr 2012 15:57:35 +0000 (17:57 +0200)] 
Improve programming documentation.

Move important programming comments to the beginning of the source file,
give them names and refer to the from the source code where necessarry.

7 years agoAdd forgotten GHC >= 7.0 condition in (!).
Milan Straka [Fri, 20 Apr 2012 15:43:14 +0000 (17:43 +0200)] 
Add forgotten GHC >= 7.0 condition in (!).

The INLINABLE pragma works only for GHC >= 7.0 and generates
warning for older compilers.

7 years agoMerge branch 'master' of
Milan Straka [Sat, 14 Apr 2012 17:04:41 +0000 (19:04 +0200)] 
Merge branch 'master' of

7 years agoImprove IntSet.{union, difference, intersection}.
Milan Straka [Sat, 14 Apr 2012 16:44:37 +0000 (18:44 +0200)] 
Improve IntSet.{union, difference, intersection}.

Incorporate improvements achieved in IntMap implementation by using
mergeWithKey' -- i.e., reorder and modify pattern matches of combining
functions, to play nicely with pattern match compiler. Also improve
the ``Tip vs Bin'' case handling.

7 years agoBenchmark of set operations -- union, difference, intersection.
Milan Straka [Sat, 14 Apr 2012 16:44:02 +0000 (18:44 +0200)] 
Benchmark of set operations -- union, difference, intersection.

7 years agoScripts for comparing csv results of benchmarks.
Milan Straka [Sat, 14 Apr 2012 16:40:31 +0000 (18:40 +0200)] 
Scripts for comparing csv results of benchmarks.

7 years agoAdd IntMap.mergeWithKey.
Milan Straka [Sat, 14 Apr 2012 14:55:46 +0000 (16:55 +0200)] 
Add IntMap.mergeWithKey.

The slightly more general internal function mergeWithKey' is used to
define both mergeWithKey and other combining functions union*,
difference*, intersection*.

The resulting implementations of union*, difference* and intersection*
are no slower than before, and up to 30% faster in case of two large
interleaved maps. Measured by benchmarks/SetOperations-IntMap.hs.

7 years agoMerge pull request #10 from batterseapower/master
Milan Straka [Fri, 30 Mar 2012 17:08:45 +0000 (10:08 -0700)] 
Merge pull request #10 from batterseapower/master

Add traverseWithKey to Map and IntMap API

7 years agoAdd traverseWithKey to Map and IntMap API
Max Bolingbroke [Fri, 30 Mar 2012 13:20:15 +0000 (14:20 +0100)] 
Add traverseWithKey to Map and IntMap API

Proposal reviewed and approved by the libraries list.
Particular thanks goes to Thomas Schilling for his suggestions
regarding how the function should be documented.

7 years agoAdd Makefile for manually building tests.
Milan Straka [Mon, 26 Mar 2012 14:37:48 +0000 (16:37 +0200)] 
Add Makefile for manually building tests.

7 years agoSmall benchmark changes.
Milan Straka [Mon, 26 Mar 2012 14:39:07 +0000 (16:39 +0200)] 
Small benchmark changes.

* Uncomment all working benchmarks.

* Use whnf instead of nf, as all containers are spine and key strict.

* Overhaul Makefile.

7 years agoMark Data.Map.(!) as INLINABLE instead of INLINE.
Milan Straka [Wed, 14 Mar 2012 17:30:43 +0000 (18:30 +0100)] 
Mark Data.Map.(!) as INLINABLE instead of INLINE.

This should have been done in commit 3f798e33. As mentioned in the
commit log, the chain
  m ! k = find k m
  {-# INLINE (!) #-}
  find k m = ...
  {-# INLINABLE find #-}
results in find not being specialized at the call site of (!).

7 years agoUpdate .gitignore.
Paolo Capriotti [Tue, 6 Mar 2012 10:57:33 +0000 (10:57 +0000)] 
Update .gitignore.

7 years agoImprove {Map,IntMap}.fold* tests.
Milan Straka [Sun, 4 Mar 2012 18:22:47 +0000 (19:22 +0100)] 
Improve {Map,IntMap}.fold* tests.

7 years agoFix Data.Sequence warnings.
Milan Straka [Sun, 4 Mar 2012 17:54:28 +0000 (18:54 +0100)] 
Fix Data.Sequence warnings.

As GHC HEAD found out, methods deep, node2, node3 were both

Also the -Wwarn option can be removed.

7 years agoImprove list fusion.
Milan Straka [Sun, 4 Mar 2012 15:29:42 +0000 (16:29 +0100)] 
Improve list fusion.

* Allow fusable methods to be converted back to the original call when
  no fusion happens. For that, foldlFB and foldrFB are used, inspired by
  mapFB from Prelude.

* Remove RULES for aliases like toList, assocs, elems, just INLINE them.

7 years agoImprove Int{Set,Map}.fold*.
Milan Straka [Sun, 4 Mar 2012 15:26:38 +0000 (16:26 +0100)] 
Improve Int{Set,Map}.fold*.

In the fold definitions, do not call go if the Bin constructor was
matched during the test for negative numbers. Instead, manually inline
that branch of go.

Otherwise GHC optimizer does this for us -- it creates local definition
of that branch of go and calls it. On my machine, it causes >200B growth
of object file, for every fold.

7 years agoImprove Int{Map,Set}.fold*.
Milan Straka [Sun, 4 Mar 2012 15:24:52 +0000 (16:24 +0100)] 
Improve Int{Map,Set}.fold*.

Improve Int{Map,Set}.fold* defitions to be inlinable with
two arguments only.

Otherwise GHC inlined toAscList, toDescList _and after that_ inlined
the fold, resulting in useless code growth.

7 years agoImprove IntMap.fold*.
Milan Straka [Sun, 4 Mar 2012 15:23:11 +0000 (16:23 +0100)] 
Improve IntMap.fold*.

Improve IntMap.fold* not to do two checks for negative numbers
-- both prefix and mask were tested. Mask tests are enough.

7 years agoImprove {Map,IntMap}.intersection* and its tests.
Milan Straka [Sat, 3 Mar 2012 10:28:18 +0000 (11:28 +0100)] 
Improve {Map,IntMap}.intersection* and its tests.

* Add tests for intersectionWith*.
* Add specific Map.intersection implementation instead of using
* Refactor Map.intersectionWithKey implementatioin.

7 years agoAdd toDescList.
Milan Straka [Mon, 12 Dec 2011 12:08:36 +0000 (13:08 +0100)] 
Add toDescList.

Add toDescList to IntMap, Set and IntSet. Also add
corresponding fusion RULES and tests.

The function is added as community was opposed to removing
toDescList from Map.

7 years agoImprove formatting of oneliners.
Milan Straka [Mon, 12 Dec 2011 11:12:42 +0000 (12:12 +0100)] 
Improve formatting of oneliners.

7 years agoImprove tests.
Milan Straka [Wed, 7 Dec 2011 19:47:48 +0000 (20:47 +0100)] 
Improve tests.

* Test IntMap.mapKeys, mapKeysWith, mapKeysMonotonic, which were just

* Unify map-properties and intmap-properties as possible, by renaming
  methods and changing comments, so that they are the same in both.

7 years agoAdd IntMap.mapKeys* methods.
Milan Straka [Wed, 7 Dec 2011 19:42:10 +0000 (20:42 +0100)] 
Add IntMap.mapKeys* methods.

Add IntMap.mapKeys, mapKeysWith, mapKeysMonotonic.
These functions are present in the Map module and we want IntMap
to be a replacement of Map Int.

The IntMap.mapKeysMonotonic is not as efficient as Map.mapKeysMonotonic
because of the IntMap representation -- the trie structure changes
wildly when the keys changes, even if the ordering of keys is not

Also, some time complexities were corrected.

7 years agoImprove performance of Map.mapKeys[With].
Milan Straka [Wed, 7 Dec 2011 19:38:57 +0000 (20:38 +0100)] 
Improve performance of Map.mapKeys[With].

We can manually fuse fFirst . toList
    where fFirst (a, b) = (f a, b)
using the right fold as
  foldrWithKey (\k x xs -> (f k, x) : xs) []

7 years agoRemove unnecessary methods from Data.Map.Strict.
Milan Straka [Wed, 7 Dec 2011 19:05:36 +0000 (20:05 +0100)] 
Remove unnecessary methods from Data.Map.Strict.

Remove implementations of mapKeys and mapKeysMonotonic
from Data.Map.Strict module. These methods modify keys only
and even Data.Map.Lazy are strict in keys.

7 years agoGeneralize IntMap.update{Min,Max}[WithKey].
Milan Straka [Wed, 7 Dec 2011 18:54:43 +0000 (19:54 +0100)] 
Generalize IntMap.update{Min,Max}[WithKey].

Previously these methods were given an argument of type
  [Key ->] a -> a
Now they are given an argument of type
  [Key ->] a -> Maybe a
That makes them compatible with Map counterparts.

7 years agoUnify IntMap.deleteFind{Min,Max} with the Map ...
Milan Straka [Mon, 5 Dec 2011 21:33:18 +0000 (22:33 +0100)] 
Unify IntMap.deleteFind{Min,Max} with the Map ...

... counterparts.

The type signature has changed from
  IntMap.deleteFind{Min,Max} :: IntMap a -> (a, IntMap a)
  IntMap.deleteFind{Min,Max} :: IntMap a -> ((Key, a), IntMap a)

7 years agoInt{Set.Map}.delete{Min,Max} doesn't fail on empty.
Milan Straka [Mon, 5 Dec 2011 21:14:46 +0000 (22:14 +0100)] 
Int{Set.Map}.delete{Min,Max} doesn't fail on empty.

Make Int{Map,Set}.delete{Min,Max} behave like {Map,Set}.delete{Min,Max}.
* Old behaviour: Int{Set,Map}.delete{Min,Max} empty ==> error
* New behaviour: Int{Set,Map}.delete{Min,Max} empty ==  empty

7 years agoDisable ropt_plain_output.
Milan Straka [Fri, 2 Mar 2012 16:48:44 +0000 (17:48 +0100)] 
Disable ropt_plain_output.

The ropt_plain_output was used to disables ansi sequences in the test
log. But it works only for test-framework < 0.5.

In test-framework >= 0.5, ropt_plain_output no longer exists. The line
"ropt_color_mode = Just ColorNever" can be used, but test-framework >= 0.5
detects it is not writing to the terminal and disables ansi sequences by

It is difficult to compile ropt_plain_output conditionally for
test-framework < 0.5 only (MIN_VERSION_* macros are not defined for
dependencies of tests, conditions in cabal tests do not work for
ghc-7.0). We therefore do not set ropt_plain_output and live with ansi
sequences in test logs produces by test-framework < 0.5.

8 years agoFix GHC HEAD build breakages
Johan Tibell [Wed, 18 Jan 2012 16:52:26 +0000 (08:52 -0800)] 
Fix GHC HEAD build breakages

GHC HEAD adds a warning for SPECIALISE pragmas that will never fire
and Data.Sequence contains such a pragma.

8 years agoMerge pull request #6 from bovinespirit/master
Milan Straka [Sun, 25 Dec 2011 11:36:25 +0000 (03:36 -0800)] 
Merge pull request #6 from bovinespirit/master

Remove NFData instances from benchmark code

8 years agoRemove NFData instances from benchmarks
Matt West [Sat, 24 Dec 2011 20:52:29 +0000 (20:52 +0000)] 
Remove NFData instances from benchmarks

8 years agoMerge pull request #5 from hvr/master-ghc74fixups
Milan Straka [Tue, 20 Dec 2011 07:05:30 +0000 (23:05 -0800)] 
Merge pull request #5 from hvr/master-ghc74fixups

Relax build deps to allow GHC-7.4's deepseq-1.3.0

8 years agoRelax build deps to allow GHC-7.4's deepseq-1.3.0
Herbert Valerio Riedel [Mon, 19 Dec 2011 18:00:20 +0000 (19:00 +0100)] 
Relax build deps to allow GHC-7.4's deepseq-1.3.0

8 years agoBump version and relax deepseq dependency ghc-7.4 containers- ghc-7.4.1-release ghc-7.4.2-release
Ian Lynagh [Thu, 15 Dec 2011 20:11:19 +0000 (20:11 +0000)] 
Bump version and relax deepseq dependency

8 years agoAllow test-suites to work with GHC < 7.0.
Milan Straka [Thu, 1 Dec 2011 21:33:03 +0000 (22:33 +0100)] 
Allow test-suites to work with GHC < 7.0.

Due to several problems with older versions of GHC and Cabal,
some extensions have to be switched unconditionaly in test-suites
to allow GHC < 7.0 to work.

The reason is
* GHC < 7.0 cannot handle conditional LANGUAGE pragmas and therefore
  the extensions have to be specified in cabal file.
* GHC = 7.0 with bundled Cabal cannot handle conditionals in
  test-suites and so we cannot enable the extensions conditionally.

When testing with GHC < 7.0 is no longer necessary, the extensions
in test-suites can be removed.

8 years agoImprovements of test-suites compilation.
Milan Straka [Wed, 30 Nov 2011 21:20:23 +0000 (22:20 +0100)] 
Improvements of test-suites compilation.

Previously the test-suites could be compiled only when a special
testing version of the library was built using -ftesting flag.
As commented by Duncan, that is bad -- users which enable testing
by default would install the testing version of library.

Now the test-suites do not link against the whole containers,
but compiles the necessary modules separately, with special testing