Add 'compose' for maps

* Make Map an instance of Bifoldable



* Replace the Arbitrary instance for Map with an adaptation of the one from Set

* Use a Map and toList instead of a list and fromList

Reimplement (<*) for sequences.

* Rename and clarify some functions based on discussions with
  @int-e and @Lysxia.
* Make `mapMulFT` unconditionally strict in its multiplier to avoid
  one silly box.
* Update changelog with credits.
* Build the 2-3 trees more eagerly to reduce heap allocation.

Xia Li-yao authored Apr 11, 2020 and David Feuer committed Apr 13, 2020

* Document the invariants of `raptyMiddle`.
* Simplify some of the arithmetic.
* Reorganize the arguments for clarity.

Remove the explicit intermediate spine structure from `(<*)`.
I don't really know if this is a good or a bad thing from a
clarity standpoint.

Make `(<*)` for `Data.Sequence` incrementally asymptotically optimal.
This finally completes the task, begun in December 2014, of making all
the `Applicative` methods for sequences asymptotically optimal
even when their results are consumed incrementally.

- Update .readthedocs.yml
- Use Python 3 compatible haddock-autolink Sphinx extension.

[ci skip]

Make previously (grandfathered) ReadTheDocs configuration explicit. This is in
preparation for upgrading to Python 3 which is the default on ReadTheDocs now.

[ci skip]

deleteFindMin was missing the map argument (`empty`).

This submodule appears to have been errenously removed in [30ccbaa2].

[30ccbaa2]: https://github.com/haskell/containers/commit/30ccbaa201043109bf1ee905c66ccd0dbe24422f#diff-fc048ebf98a95fc8a8ff9c949d9b49a9.

Closes #696.

Simon Jakobi authored Jan 19, 2020 and David Feuer committed Jan 19, 2020

Simply import `GHC.Exts` fully qualified to avoid fussy CPP.

Gabor Greif authored Jan 10, 2020 and David Feuer committed Jan 10, 2020

* Fix Haddocks for `mapAccumRWithKey`

Simon Jakobi authored Dec 29, 2019 and David Feuer committed Dec 29, 2019

Also:
* Fix a bunch of warnings.
* Disable "cabal check" in Travis CI, since it dislikes -Werror

Simon Jakobi authored Dec 17, 2019 and David Feuer committed Dec 25, 2019

Closes #692.

This includes a test for the effects sequencing in Data.Map.mergeA.

jwaldmann authored Dec 22, 2019 and David Feuer committed Dec 21, 2019

* Test that instances for Eq and Ord agree with going via toAscList

* Add benchmark for "instance Ord IntSet", using "Set IntSet"

* Improve implementation of "instance Ord IntSet"
that avoids toAscList and walks the tree directly. See #470

Matthew Pickering authored Aug 17, 2019 and David Feuer committed Dec 21, 2019

The function is self-recursive and not overloaded, therefore I see no reason for the pragma. 

Core lint warns - 

```
*** Core Lint warnings : in result of Simplifier ***
libraries/containers/containers/src/Data/Sequence/Internal/Sorting.hs:389:1: warning:
    [RHS of foldToMaybeTree :: forall b a.
                               (b -> b -> b) -> (a -> b) -> FingerTree a -> Maybe b]
    INLINE binder is (non-rule) loop breaker: foldToMaybeTree
```

Simon Jakobi authored Oct 07, 2019 and David Feuer committed Dec 21, 2019

Fixes #629.

Felix Paulusma authored Dec 18, 2019 and David Feuer committed Dec 18, 2019

* corrected traverseWithKey changing the structure of the map

* also updated the other traverse* functions to use the correct order of traversing

* added property tests for traversals





* fixed /mapAccumR?WithKey/ as well

* adjusted tests for map* functions to also incluse negative numbers

* fixed minimum and maximum methods of IntMap to keep order so that "minimum intMap == minimum (elems intMap)"


* added negative numbers to all unit tests

* fixed filterWithKeyA to also consider negative keys

* IntMap/tests: added degrade prop tests to traverseMaybeWithKey and misc

* IntMap/tests: also added degradation test from traverseWithKey to mapWithKey

Use countTrailingZeros for indexOfTheOnlyBit

Javran Cheng authored Jul 24, 2019 and David Feuer committed Jul 24, 2019

* Add Data.IntSet.mapMonotonic.

This patch fills in the missing piece for Data.IntSet,
since Data.{Map,IntMap} and Data.Set all have this function.
(for Map variant it's `mapKeysMonotonic`)

* test mapMonotonic property on id and linear.

Improve `fromAscList` and friends for `IntMap` and `IntSet`, making them somewhat faster and much easier to understand.

- no benchmarks, but the code is analogous to Data.IntMap.from*AscList*

benchmark summary:

old:
fromList                                 mean 244.4 μs  ( +- 7.088 μs  )
fromAscList                              mean 178.6 μs  ( +- 1.211 μs  )
fromDistinctAscList                      mean 105.5 μs  ( +- 1.048 μs  )

new:
fromList                                 mean 225.2 μs  ( +- 2.345 μs  )
fromAscList                              mean 84.71 μs  ( +- 1.011 μs  )
fromDistinctAscList                      mean 84.20 μs  ( +- 945.0 ns  )

benchmark summary:

old:
fromList                                 mean 86.33 μs  ( +- 557.8 ns  )
fromAscList                              mean 42.01 μs  ( +- 154.4 ns  )
fromDistinctAscList                      mean 15.74 μs  ( +- 90.03 ns  )

new:
fromList                                 mean 83.00 μs  ( +- 1.147 μs  )
fromAscList                              mean 14.40 μs  ( +- 367.6 ns  )
fromDistinctAscList                      mean 14.56 μs  ( +- 486.9 ns  )

Bertram Felgenhauer authored Jul 08, 2019 and David Feuer committed Jul 08, 2019

The Makefile for tests uses the same `outputdir` value for all
targets. This interacts badly with ghc's recompilation check:

> make bench-IntMap bench-IntSet
ghc -O2 -DTESTING IntMap.hs -I../include -i.. -o bench-IntMap -outputdir tmp -rtsopts
[1 of 1] Compiling Main             ( IntMap.hs, tmp/Main.o )
Linking bench-IntMap ...
ghc -O2 -DTESTING IntSet.hs -I../include -i.. -o bench-IntSet -outputdir tmp -rtsopts
Linking bench-IntSet ...
> ./bench-IntSet --small lookup
lookup                                   mean 218.5 μs  ( +- 1.470 μs  )
> make clean; make bench-IntSet
[...]
> ./bench-IntSet --small lookup
Error: none of the specified names matches a benchmark
Run "bench-IntSet --help" for usage information
> ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.6.5

To avoid this problem, use individual output directories for each
program.