As discussed in #870, the complexities for union, difference, etc. on
Set and Map were changed in #830 to fix some partiality in the
expressions, but along the way new partiality was introduced, and useful
special cases like m = 1 get incorrect complexity values from the new
formulas.

The original formula was as stated in the original paper:
  https://dl.acm.org/doi/10.1145/322123.322127
and this holds for 0 < m <= n, which seems sufficient to me. (The m=0
case is excluded, but for m=0 nothing needs to be done anyway. This
contrary to the m=1 case, in which useful work with very specific
complexity (namely, O(log(n))) needs to be done.)

This commit reverts all occurrences of the modified complexity formula
back to the original one.

fromRange (l,h) is faster than fromRange [l..h], primarily because we
can pack Tips with multiple elements at once.

IntMap.mapKeysMonotonic and IntMap.keysSet take linear time.

* Benchmarks for {Set,Map}.fromDistinct{Asc,Desc}List

* Improve {Set,Map}.fromDistinct{Asc,Desc}List

A faster and fusion-friendly implemention of the current strategy.

On GHC 9.2.5:
For Set this takes 56% less time when there is fusion and 30% when not.
For Map this takes 55% less time when there is fusion and 16% when not.

* Remove a now inaccurate claim in {Set,Map}.fromList

* Add a note explaining the implementation

* Pull out linkTop and linkAll helpers as INLINABLE

And leave further optimization to GHC.

* Test that last for Tree is lazy enough

last should only need to look at the path going down to the last leaf.

* Test foldMap and foldMap1 for Tree more

Test that they fold according to the structure of the tree.

This is the code that was originally used to generate the code to append sequences. Adding it to the repo for history and education.

Closes #908.

Co-authored-by: Samuel Schlesinger <samuelschlesinger@Samuels-MacBook-Air.local>

Added instructions to compile containers-test using symbolic links for Windows users

Co-authored-by: konsumlamm <44230978+konsumlamm@users.noreply.github.com>

* The `stack.yaml` was quite stale. It also was not obviously very
  useful in the context of a GHC boot package. Remove it, as well as the
  instructions for building and testing with `stack`.

* Expand the information on testing/benchmarking with `cabal`.

Closes #938

Add star and line graphs, which are the extremes of wide and deep
graphs.

Fixes #932

* Add `@since` annotations for the `MonadZip` instances for
  `Data.Sequence` and `Data.Tree`.

* Fix Haddock markup.

* Make `foldMap1` follow the tree structure. This makes it work lazily
  with semigroups like `Data.Semigroup.Last`.

* Remove the custom implementation of `last`; the default one works
  well with this `foldMap1`.

Fixes #919

Update Data.Graph documentation

* Using a custom prelude named `Prelude` breaks `cabal repl`.  Just
  rename it, and change imports all over the place.

* Squash a warning about dollar sign use in the test suite.

Fixes #898

For topSort and reverseTopSort the graph is expected to be acyclic.
For bcc the graph is expected to be undirected.

Update changelog and @since annotations

* Update `CHANGELOG.md`.

* Add missing `@since` annotations.

Closes #911.

Allow specialization of Data.Graph functions

Mark functions in Data.Graph that have an Ord constraint as INLINABLE
to allow specialization.

Optimize Data.Graph.bcc

* Concat difference lists instead of lists to avoid O(n^2) complexity
* Avoid the unnecessary tree labelling step
* Add explanatory comments

Implement Foldable1 for Data.Tree.Tree

* Add benchmarks for Data.Graph.transposeG

* Inline simple functions in Data.Graph

Mark vertices, edges, buildG, and reverseE as INLINE. These are
functions with simple definitions that produce or consume lists.
Inlining them allows fusion and other optimizations.
Improvements are seen in transposeG and scc (which uses transposeG),
and external callers could also benefit.