packages/containers.git
3 months agoAllowed inlining for traverseWithIndex (#623)
Donnacha Oisín Kidney [Fri, 12 Apr 2019 00:54:22 +0000 (01:54 +0100)] 
Allowed inlining for traverseWithIndex (#623)

* Allowed inlining for traverseWithIndex

Switched NOINLINE to INLINE:
- Ideally this would be INLINABLE, but that can't have phase controls
- This is the next best, which gets the proper performance benefits and also the phase controles so the rewrite rules still fire properly

Because this was prompted by sequenceA.mapWithIndex being faster, a benchamrk of that operation has been added to compare.

* INLINABLE can have phase controls

As it turns out, INLINABLE *can* have phase controls.

Benchmarks so no real change:

benchmarking traverseWithIndex/State/10
time                 368.6 ns   (364.2 ns .. 372.2 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 366.6 ns   (363.2 ns .. 370.0 ns)
std dev              11.56 ns   (9.593 ns .. 14.54 ns)
variance introduced by outliers: 46% (moderately inflated)

benchmarking traverseWithIndex/State/100
time                 4.730 μs   (4.663 μs .. 4.796 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 4.702 μs   (4.660 μs .. 4.752 μs)
std dev              149.9 ns   (123.3 ns .. 192.9 ns)
variance introduced by outliers: 40% (moderately inflated)

benchmarking traverseWithIndex/State/1000
time                 65.15 μs   (64.31 μs .. 66.13 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 66.58 μs   (65.80 μs .. 67.65 μs)
std dev              3.082 μs   (2.343 μs .. 4.561 μs)
variance introduced by outliers: 50% (moderately inflated)

benchmarking sequenceA.mapWithIndex/State/10
time                 597.8 ns   (589.4 ns .. 606.8 ns)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 602.1 ns   (595.9 ns .. 610.4 ns)
std dev              23.84 ns   (17.59 ns .. 38.02 ns)
variance introduced by outliers: 56% (severely inflated)

benchmarking sequenceA.mapWithIndex/State/100
time                 5.915 μs   (5.854 μs .. 6.023 μs)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 6.006 μs   (5.939 μs .. 6.078 μs)
std dev              235.9 ns   (199.3 ns .. 285.5 ns)
variance introduced by outliers: 50% (moderately inflated)

benchmarking sequenceA.mapWithIndex/State/1000
time                 83.08 μs   (81.80 μs .. 84.81 μs)
                     0.998 R²   (0.998 R² .. 0.999 R²)
mean                 83.78 μs   (83.04 μs .. 84.50 μs)
std dev              2.604 μs   (2.277 μs .. 3.018 μs)
variance introduced by outliers: 30% (moderately inflated)

* put INLINABLE behind a macro

3 months agoUpdate cycleTaking docs
David Feuer [Thu, 11 Apr 2019 04:54:50 +0000 (00:54 -0400)] 
Update cycleTaking docs

[skip ci]

3 months agoImplement stimes for sequences
David Feuer [Thu, 11 Apr 2019 04:29:31 +0000 (00:29 -0400)] 
Implement stimes for sequences

Implement `stimes` for sequences using `cycleNTimes`. This makes
it work when the argument is 0 (unlike the default). `cycleNTimes`
is faster and lazier than `stimesMonoid` because it takes advantage
of the finger tree structure of sequences.

Closes #618

3 months agoReplace criterion with gauge as the benchmark framework
Simon Jakobi [Sat, 13 Oct 2018 19:57:35 +0000 (21:57 +0200)] 
Replace criterion with gauge as the benchmark framework

3 months agoFix compilation of 'set-properties' test suite with GHC-8.6
Simon Jakobi [Sun, 17 Mar 2019 19:10:25 +0000 (20:10 +0100)] 
Fix compilation of 'set-properties' test suite with GHC-8.6

Fixes #570.

3 months agobenchmarks comparer: Use `/usr/bin/env` to find perl
John Ericson [Mon, 18 Mar 2019 05:22:39 +0000 (01:22 -0400)] 
benchmarks comparer: Use `/usr/bin/env` to find perl

This is needed on NixOS. FHS does say if perl is installed it shoul be
found at `/usr/bin/perl`, so can't say this is more portable in general,
but doesn't hurt FHS systems either

3 months agoImprove isSubsetOf (#615)
David Feuer [Tue, 9 Apr 2019 11:03:18 +0000 (07:03 -0400)] 
Improve isSubsetOf (#615)

* Add recursive size tests to `Data.Set.isSubsetOf`.

* Add a special case for singleton subsets to avoid extra splits
  at all the leaves.

* Do the same for `isSubmapOf`.

* Add the singleton special case to `disjoint`.

* Tighten advertised bounds and improve documentation.

Closes #614

5 months agoImprove ListUtils docs
David Feuer [Tue, 5 Feb 2019 21:33:29 +0000 (16:33 -0500)] 
Improve ListUtils docs

* Tighten the performance bounds. The final size of the set is
  the number of *distinct* elements in the list, not the total number
  of elements.

* Fix missing parenthesis.

* Add example.

5 months agoAdd notes on cartesianProduct performance
David Feuer [Thu, 31 Jan 2019 08:18:15 +0000 (03:18 -0500)] 
Add notes on cartesianProduct performance

I came up with an implementation that is obviously big-O optimal,
but that seems much slower in my limited tests. Add a note about that, and
document the conjecture that the implementation we use is optimal
too.

5 months agoSpeed up special cases of Cartesian products
David Feuer [Thu, 31 Jan 2019 06:51:17 +0000 (01:51 -0500)] 
Speed up special cases of Cartesian products

If the second argument of `Data.Set.cartesianProduct` happens to
be empty or a singleton, then we don't need to merge a bunch of trees.
So let's not.

5 months agoCorrect order of arguments Map.member
benjaminweb [Tue, 22 Jan 2019 12:37:46 +0000 (13:37 +0100)] 
Correct order of arguments Map.member

5 months agoSimplify Arbitrary instance for IntMap
David Feuer [Mon, 21 Jan 2019 21:07:06 +0000 (16:07 -0500)] 
Simplify Arbitrary instance for IntMap

Closes #594

5 months agoFix Foldable instance for IntMap (fixes #579) (#593)
Matt Renaud [Tue, 22 Jan 2019 03:41:53 +0000 (19:41 -0800)] 
Fix Foldable instance for IntMap (fixes #579) (#593)

* Fix Foldable instance for IntMap.

As reported in https://github.com/haskell/containers/issues/579 the Foldable
instance for IntMap is unlawful and internally inconsistent. This was caused as
a result of the internal representation used by IntMap.

More specifically, `fold`, `foldMap`, and `traverse` (via `traverseWithKey`)
always placed positively keyed entries before negative keyed ones. To fix this
we need to check to see if the mask is positive or negative.

Tested by adding new property tests, verifying they failed with the
implementation at HEAD, and then passed after the changes.

5 months agoTypo fix in set.rst (#589)
Vados [Fri, 18 Jan 2019 16:23:02 +0000 (01:23 +0900)] 
Typo fix in set.rst (#589)

"addional" -> "additional"

6 months agoUpdated Set.unions documentation to mention Foldable instead of list (#585)
Morten Kolstad [Wed, 19 Dec 2018 19:48:27 +0000 (20:48 +0100)] 
Updated Set.unions documentation to mention Foldable instead of list (#585)

The previous documentation for unions said that you need a list of sets,
but the type says that it can be any Foldable structure:

    unions :: (Foldable f, Ord a) => f (Set a) -> Set a

Changed the wording to "The union of the sets in a Foldable structure".

7 months agoRephrase sentence
Boro Sitnikovski [Wed, 28 Nov 2018 02:37:25 +0000 (03:37 +0100)] 
Rephrase sentence

7 months agoUpdate Internal.hs
Vaibhav Sagar [Sun, 2 Dec 2018 20:33:33 +0000 (15:33 -0500)] 
Update Internal.hs

Edit docs for `powerSet`.

7 months agoHaddock fixes (#560)
Alec Theriault [Sun, 2 Dec 2018 06:27:21 +0000 (22:27 -0800)] 
Haddock fixes (#560)

Tweaked documentation fixing Haddock markup. Mostly:

  * qualifying out-of-scope or ambiguous identifiers
  * properly escaping character literals in examples
  * several obvious typos

7 months agoFix typo of "Map.abjust" to "Map.adjust"
Matthias Hetzenberger [Sat, 1 Dec 2018 16:23:57 +0000 (17:23 +0100)] 
Fix typo of "Map.abjust" to "Map.adjust"

7 months agoRemove unused imports. (#576)
David Eichmann [Wed, 14 Nov 2018 14:39:27 +0000 (15:39 +0100)] 
Remove unused imports. (#576)

Due to a bug in ghc, some unused imports do not yield warnings.
This commit will remove such unused imports in preparation for
the ghc bug fix (see https://ghc.haskell.org/trac/ghc/ticket/13064).

8 months agoFix typos in the documentation. (#575)
David Sanders [Thu, 25 Oct 2018 15:33:01 +0000 (08:33 -0700)] 
Fix typos in the documentation. (#575)

* Fix a typo in sequence.rst

* Fix a misspelling in the documentation.

8 months agoFix sample code of alterF in haddock
Yuji Yamamoto [Tue, 16 Oct 2018 07:06:02 +0000 (16:06 +0900)] 
Fix sample code of alterF in haddock

Found by a question in StackOverflow https://stackoverflow.com/questions/52828746/haskell-data-map-strict-alterf-parse-error-on-input/52829097

9 months agoUpdate criterion bounds
klebinger.andreas@gmx.at [Fri, 27 Jul 2018 13:53:18 +0000 (15:53 +0200)] 
Update criterion bounds

9 months agoSwitch to using 'friendly' pygments style for docs. (#567)
Matt Renaud [Sun, 30 Sep 2018 03:34:14 +0000 (20:34 -0700)] 
Switch to using 'friendly' pygments style for docs. (#567)

The 'sphinx' style changed to have a dull green background colour which is ugly
and more difficult to read. The 'friendly' style has a neutral background and is
nicer to look at (and looks like what the 'sphinx' style used to look like).

10 months agoData.Graph.stronglyConnComp: document ordering (#562)
jwaldmann [Mon, 3 Sep 2018 17:58:34 +0000 (19:58 +0200)] 
Data.Graph.stronglyConnComp: document ordering (#562)

10 months agoCorrect typo
Mark Seemann [Fri, 3 Aug 2018 07:52:00 +0000 (09:52 +0200)] 
Correct typo

10 months agoMerge pull request #559 from ploeh/patch-2
Mark Seemann [Wed, 22 Aug 2018 14:50:58 +0000 (16:50 +0200)] 
Merge pull request #559 from ploeh/patch-2

Add examples for foldTree

12 months agoFixing a typo in sequence.rst
David Sanders [Tue, 26 Jun 2018 18:35:02 +0000 (11:35 -0700)] 
Fixing a typo in sequence.rst

12 months agoExpress `spanAntitone` in terms of `partitionWithKey` instead of `partition`
Sebastian Graf [Sat, 23 Jun 2018 20:01:47 +0000 (22:01 +0200)] 
Express `spanAntitone` in terms of `partitionWithKey` instead of `partition`

The current haddock doesn't type-check.

12 months agoFix version number
David Feuer [Mon, 18 Jun 2018 03:22:07 +0000 (23:22 -0400)] 
Fix version number

12 months agoBump version
David Feuer [Mon, 18 Jun 2018 03:20:25 +0000 (23:20 -0400)] 
Bump version

15 months agoUpdate documentation for strict insertWithKey.
AndreasPK [Tue, 10 Apr 2018 21:28:36 +0000 (23:28 +0200)] 
Update documentation for strict insertWithKey.

The documentation describes the arguments as `insertWithKey f key value mp` .
This updates the later referenced argument names to match these.

15 months agofix typo disjoin
Julie Moronuki [Mon, 26 Mar 2018 04:19:12 +0000 (00:19 -0400)] 
fix typo disjoin

16 months agoFix Documentation Typos (#545)
Frank Steffahn [Sat, 10 Mar 2018 04:12:06 +0000 (05:12 +0100)] 
Fix Documentation Typos (#545)

In the Haddocks, fix a bunch of infix functions with unescaped backticks that got formatted all wrong.

16 months agoAdd Generic and Generic1 for Seq internals (#540)
David Feuer [Fri, 9 Mar 2018 21:53:03 +0000 (16:53 -0500)] 
Add Generic and Generic1 for Seq internals (#540)

Add `Generic` and `Generic1` instances for `Data.Sequence.Internal`
types: `FingerTree`, `Node`, `Elem`, and `Digit`.

16 months agoImprove Data.Tree documentation. (#534)
Matt Renaud [Fri, 9 Mar 2018 21:44:34 +0000 (13:44 -0800)] 
Improve Data.Tree documentation. (#534)

This partially addresses #495.

16 months agoFix Documentation Typo in Data/Sequence.hs (#541)
Frank Steffahn [Fri, 9 Mar 2018 20:32:18 +0000 (21:32 +0100)] 
Fix Documentation Typo in Data/Sequence.hs (#541)

In the module header, in a code example where “index” is used infix, the back-ticks need to be escaped, otherwise haddock interprets them as (an alternative form of) quotes for a hyperlinked identifier which in particular makes the back-ticks invisible in the documentation and generates invalid Haskell code in the code example.

16 months agoDisable deprecated things (#536)
David Feuer [Fri, 9 Mar 2018 20:29:20 +0000 (15:29 -0500)] 
Disable deprecated things (#536)

Disable all deprecated functions by making them produce type errors when used.
This is an experimental removal approach.  It may or may not really be a good
idea. The benefit is that unlike deprecation it *forces* people to make a
change, and unlike immediate removal it tells them what change to make.

With GHC 8.0 and above, the type errors are pretty. With earlier
versions of GHC, they're gross. With a hypothetical non-GHC compiler, the
functions are just removed.

16 months agoUnbox some more graph stuff (#543)
David Feuer [Fri, 9 Mar 2018 19:39:19 +0000 (14:39 -0500)] 
Unbox some more graph stuff (#543)

* Replace boxed arrays of `Int` with unboxed ones.
* Make a `zipWith` able to fuse.
* Use `fmap` in `outdegree` rather than a custom function for
  mapping with an index we don't need anyway.
* Use `.Safe` array modules in `Data.Graph`.

16 months agoDrop support for pre-7.6 GHC
David Feuer [Fri, 9 Mar 2018 17:19:18 +0000 (12:19 -0500)] 
Drop support for pre-7.6 GHC

* Bump base dependency
* Bump `array` dependency
* Assume at least 7.6 when compiling with GHC
* Drop support for compiling without MIN_VERSION macros. These
  are now built into GHC. We can add some sort of support back
  if we expand to a non-GHC compiler, but that support will look
  completely different anyway.
* Remove deprecated `Data.Map.Lazy.Merge` and `Data.Map.Strict.Merge`
  modules. These were renamed almost immediately after they were
  introduced.
* Update changelog

16 months agoremove foldlStrict, generalize type of unions, see #520 (#524)
jwaldmann [Fri, 9 Mar 2018 17:18:07 +0000 (18:18 +0100)] 
remove foldlStrict, generalize type of unions, see #520 (#524)

16 months agoSpeed up indegree
David Feuer [Thu, 8 Mar 2018 00:47:45 +0000 (19:47 -0500)] 
Speed up indegree

Instead of taking the transpose of a graph and then calculating
the outdegree, calculate the indegree directly. This probably
won't actually improve performance much (if at all) until
`base-4.12` or so comes out: see
[GHC Trac #14785](https://ghc.haskell.org/trac/ghc/ticket/14785).
If we want, we can reimplement `accumArray` ourselves to work around
this problem.

Fixes #533

16 months agoImprove Data.Graph documentation. (#532)
Matt Renaud [Thu, 8 Mar 2018 00:26:05 +0000 (16:26 -0800)] 
Improve Data.Graph documentation. (#532)

* Improve module docs
* Re-orders function documentation order
* Adds examples
* Don't use Table type alias, use Array Vertex a instead.

16 months agoAvoid two-layers of pattern matchin in `union` (#537)
Joachim Breitner [Tue, 20 Feb 2018 15:34:45 +0000 (10:34 -0500)] 
Avoid two-layers of pattern matchin in `union` (#537)

by matching on the size field instead. I expect this to yield (slightly)
more efficient code. According to the benchmark, this yields a 4% speed
improvement for `union` and 3% for `unions`.

17 months agoReorganize Map and IntMap Haddocks. (#519)
Matt Renaud [Mon, 12 Feb 2018 17:40:39 +0000 (09:40 -0800)] 
Reorganize Map and IntMap Haddocks. (#519)

- Move "Construction" section to the top
- Include fromList functions in "construction" section
- Remove "operators" section, you don't go "looking for operators", you go
  "looking for functionality" which may be available as an operator.
- Move most common query operations (lookup and friends) to the top
- Move Insertion and Deletion sections below Construction.

[ci skip]

17 months agoReorganize Set and IntSet Haddocks. (#531)
Matt Renaud [Thu, 8 Feb 2018 18:20:29 +0000 (10:20 -0800)] 
Reorganize Set and IntSet Haddocks. (#531)

This moves the Construction section to the top, puts all "construction like"
functions under that heading, and moves Insertion and Deletion under
Construction. Also, moves operators out of their own section and
into the appropriate section, and moves `member` to the top of the Query
section.

[ci skip]

17 months agoFix IntSet and IntMap validity tests. (#530)
Matt Renaud [Thu, 8 Feb 2018 05:42:19 +0000 (21:42 -0800)] 
Fix IntSet and IntMap validity tests. (#530)

The previous implementations only checked the commonPrefix and maskRespected
invariant for the top level Bin constructor and didn't appropriately recurse
into subtrees.

This resolves #522.

17 months agoUnbox the `SetM` array (#528)
David Feuer [Tue, 6 Feb 2018 23:08:12 +0000 (18:08 -0500)] 
Unbox the `SetM` array (#528)

`Data.Graph` uses a mutable array to track which vertices have
been visited. This was implemented using an `STArray s Vertex Bool`.
This is obviously bad, because the garbage collector will have to
trace the array if it's alive during a collection. Using an unboxed
array instead should always be better. Indeed, doing so will also
dramatically reduce the size of the array, from the number of
vertices in the graph to that divided by the word size. Each array
operation is slightly more complex, but we'll surely win from
memory locality and such anyway.

17 months agoRemove "strict map" wording from docs (#521)
Matt Renaud [Wed, 31 Jan 2018 22:47:15 +0000 (14:47 -0800)] 
Remove "strict map" wording from docs (#521)

* Remove "strict map" wording from docs

There's no such things as a "strict map", only a Strict API which forces evaluation of values before inserting them into the map.

[ci skip]

17 months agoIntroduction/tutorial doc improvements. (#512)
Matt Renaud [Mon, 29 Jan 2018 16:39:58 +0000 (08:39 -0800)] 
Introduction/tutorial doc improvements. (#512)

Changes:
--------

- Update titles so that package name is visible in browser tabs
- Fix typo in sequence docs
- Use https://github.com/m-renaud/haddock-autolink
- Update theme (dark grey with green) for desktop and mobile

Why use a submodule?
--------------------

Improvements to the autolinker don't need to take place in the containers repo. Also, if other projects end up using it the code doesn't get out of sync (not everyone needs to copy/paste the Sphinx extension).

If you're not modifying the docs you don't need to pull down all the Python code. If you do want to build the container docs locally you need to pull down the submodule code (see the CONTRIBUTING.md file for exact commands to run).

Read the docs natively supports submodules so this has no visible effect on the docs.

[ci skip]

17 months agoImprove IntSet and IntMap module docs. (#507)
Matt Renaud [Mon, 29 Jan 2018 01:43:15 +0000 (17:43 -0800)] 
Improve IntSet and IntMap module docs. (#507)

17 months agoadded since annotations to sorting functions (#518)
Donnacha Oisín Kidney [Sun, 28 Jan 2018 02:44:28 +0000 (02:44 +0000)] 
added since annotations to sorting functions (#518)

17 months agoAdd RULES for nub functions (#517)
David Feuer [Sun, 28 Jan 2018 01:10:50 +0000 (20:10 -0500)] 
Add RULES for nub functions (#517)

* Add rewrite rules to allow the nub functions in `ListUtils`
  to participate in fold/build fusion.

* For the sake of simplicity, define `nubOrd` and `nubInt` in terms
  of `nubOrdOn` and `nubIntOn`.

17 months agoFaster traverse (#516)
Donnacha Oisín Kidney [Sat, 27 Jan 2018 21:38:49 +0000 (21:38 +0000)] 
Faster traverse (#516)

17 months agotest stability of sort and sortOn (#514)
Donnacha Oisín Kidney [Sat, 27 Jan 2018 19:06:18 +0000 (19:06 +0000)] 
test stability of sort and sortOn (#514)

The test may not be necessary for `sortOn`, but that's okay.

17 months agoadd nubOrd and friends (#515)
gbaz [Fri, 26 Jan 2018 22:11:05 +0000 (17:11 -0500)] 
add nubOrd and friends (#515)

17 months agoSpeed up folds on Sequences (#510)
Donnacha Oisín Kidney [Thu, 25 Jan 2018 13:53:46 +0000 (13:53 +0000)] 
Speed up folds on Sequences (#510)

* much faster foldMap
* much faster foldl'
* much quicker foldr
* more folds optimised
* put coercions in their own module

* added coercion operator that can be used in foldl

* Added tests for the laziness of foldr' and foldl'

17 months agoUpdate changelog again
David Feuer [Tue, 23 Jan 2018 01:53:30 +0000 (20:53 -0500)] 
Update changelog again

17 months agoImprove Data.Map (strict and lazy) module docs (#497)
Matt Renaud [Tue, 23 Jan 2018 00:50:19 +0000 (16:50 -0800)] 
Improve Data.Map (strict and lazy) module docs (#497)

[ci skip]

17 months agoRespond to suggestions on Data.Sequence docs (#506)
David Feuer [Tue, 23 Jan 2018 00:44:19 +0000 (19:44 -0500)] 
Respond to suggestions on Data.Sequence docs (#506)

Several Redditors responded to [my RFC](https://www.reddit.com/r/haskell/comments/7p6eg2/request_for_comments_on_expanded_datasequence_docs/).
Edit the `Data.Sequence` documentation to address most of their concerns.

[skip ci]

17 months agoImprove Data.Set module docs. (#502)
Matt Renaud [Mon, 22 Jan 2018 18:05:33 +0000 (10:05 -0800)] 
Improve Data.Set module docs. (#502)

* Improve Data.Set module docs.

[ci skip]

* Move strictness properties into module docs.

[ci skip]

* Address review comments.

[ci skip]

* Reword first paragraph.

[ci skip]

17 months agoFix power of 2 validity check. (#505)
Matt Renaud [Mon, 22 Jan 2018 17:31:29 +0000 (09:31 -0800)] 
Fix power of 2 validity check. (#505)

Previously an incorrect check of divisible by 2 was being performed, this fixes
the behaviour.

17 months agoBump version
David Feuer [Mon, 22 Jan 2018 09:31:18 +0000 (04:31 -0500)] 
Bump version

17 months agoMerge pull request #503 from treeowl/minmaxview-fixup
David Feuer [Mon, 22 Jan 2018 09:25:00 +0000 (04:25 -0500)] 
Merge pull request #503 from treeowl/minmaxview-fixup

Minmaxview fixup

17 months agoImprove min and max view laziness and inlining
David Feuer [Mon, 8 Jan 2018 21:26:44 +0000 (16:26 -0500)] 
Improve min and max view laziness and inlining

* Harmonize laziness (not strictness!) of min and max views between
`IntMap` and `Map`.

* Improve GHC's ability to unbox the results of min and max views
  for `IntMap`.

17 months agoUpdate changelog.md
David Feuer [Mon, 22 Jan 2018 06:05:24 +0000 (01:05 -0500)] 
Update changelog.md

17 months agoMerge pull request #377 from vlopezj/disjoint
David Feuer [Mon, 22 Jan 2018 05:56:50 +0000 (00:56 -0500)] 
Merge pull request #377 from vlopezj/disjoint

* Add `Data.IntSet.disjoint`
* Add `Data.Set.disjoint`

17 months agoUpdate changelog
David Feuer [Mon, 22 Jan 2018 05:47:59 +0000 (00:47 -0500)] 
Update changelog

17 months agosortOn functions using same heap as sort and unstableSort (#500)
Donnacha Oisín Kidney [Mon, 22 Jan 2018 05:38:36 +0000 (05:38 +0000)] 
sortOn functions using same heap as sort and unstableSort (#500)

Add

```haskell
sortOn, unstableSortOn :: Ord b => (a -> b) -> Seq a -> Seq a
```

analogous to `Data.List.sortOn`. We minimize the performance cost by integrating the decorate-sort-undecorate paradigm into the heap structure. It will still be somewhat faster to use ``sortBy (compare `on` f)`` than `sortOn f` if `f` is very cheap, but otherwise `sortOn` will be faster.

17 months agoAdd minView benchmark for Map
David Feuer [Mon, 8 Jan 2018 22:44:52 +0000 (17:44 -0500)] 
Add minView benchmark for Map

17 months agoAdd `disjoint` for Data.Set
Víctor López Juan [Fri, 19 Jan 2018 21:19:00 +0000 (22:19 +0100)] 
Add `disjoint` for Data.Set

This is added mostly for consistency with `IntSet.disjoint`.
Performance also improves compared to the corresponding
`(null.).intersection` implementation.

Benchmark set-benchmarks: RUNNING...
[...]
benchmarking disjoint:false
time                 69.64 ns   (68.87 ns .. 70.69 ns)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 69.39 ns   (68.31 ns .. 70.86 ns)
std dev              3.819 ns   (2.979 ns .. 4.857 ns)
variance introduced by outliers: 75% (severely inflated)

benchmarking disjoint:true
time                 611.5 μs   (606.6 μs .. 618.0 μs)
                     0.999 R²   (0.997 R² .. 1.000 R²)
mean                 620.2 μs   (608.3 μs .. 664.9 μs)
std dev              68.26 μs   (14.09 μs .. 140.9 μs)
variance introduced by outliers: 79% (severely inflated)

benchmarking null.intersection:false
time                 234.9 μs   (227.3 μs .. 241.2 μs)
                     0.995 R²   (0.993 R² .. 0.998 R²)
mean                 218.8 μs   (214.7 μs .. 224.3 μs)
std dev              14.66 μs   (11.51 μs .. 18.56 μs)
variance introduced by outliers: 62% (severely inflated)

benchmarking null.intersection:true
time                 732.3 μs   (701.0 μs .. 767.7 μs)
                     0.989 R²   (0.983 R² .. 0.996 R²)
mean                 726.3 μs   (711.1 μs .. 742.9 μs)
std dev              50.46 μs   (38.81 μs .. 63.17 μs)
variance introduced by outliers: 58% (severely inflated)

17 months agoAdd function to check if two `IntSet`s are `disjoint`.
Víctor López Juan [Sun, 1 Jan 2017 21:12:43 +0000 (22:12 +0100)] 
Add function to check if two `IntSet`s are `disjoint`.

This function is equivalent to computing the intersection and checking
if it is empty. However, it is more efficient because the intersection
set does not need to be built in memory, and the computation can
be short-circuited as soon as two non-disjoint `Tip`s are found.

Benchmark intset-benchmarks: RUNNING...
[...]
benchmarking disjoint:false
time                 149.2 ns   (147.7 ns .. 150.6 ns)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 147.0 ns   (145.4 ns .. 148.6 ns)
std dev              5.281 ns   (4.234 ns .. 6.800 ns)
variance introduced by outliers: 54% (severely inflated)

benchmarking disjoint:true
time                 2.500 μs   (2.468 μs .. 2.533 μs)
                     0.999 R²   (0.999 R² .. 0.999 R²)
mean                 2.451 μs   (2.425 μs .. 2.477 μs)
std dev              81.58 ns   (69.22 ns .. 98.12 ns)
variance introduced by outliers: 44% (moderately inflated)

benchmarking null.intersection:false
time                 4.077 μs   (4.038 μs .. 4.122 μs)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 4.026 μs   (3.983 μs .. 4.090 μs)
std dev              170.3 ns   (121.3 ns .. 264.2 ns)
variance introduced by outliers: 54% (severely inflated)

benchmarking null.intersection:true
time                 2.527 μs   (2.468 μs .. 2.610 μs)
                     0.996 R²   (0.993 R² .. 0.999 R²)
mean                 2.490 μs   (2.459 μs .. 2.535 μs)
std dev              122.4 ns   (85.89 ns .. 180.2 ns)
variance introduced by outliers: 63% (severely inflated)

17 months agoFaster stable sort (#492)
Donnacha Oisín Kidney [Sat, 20 Jan 2018 20:56:57 +0000 (20:56 +0000)] 
Faster stable sort (#492)

Use a new, faster implementation for stable sort

The old stable sort simply called Data.List.sort: here, we construct a pairing heap, but tag each element with its original position in the sequence. Then we perform heap sort, the same sort as used in `unstableSort`.

17 months agoMove bitcount to Utils.Internal.BitUtil. (#498)
Matt Renaud [Fri, 19 Jan 2018 16:27:24 +0000 (08:27 -0800)] 
Move bitcount to Utils.Internal.BitUtil. (#498)

Previously this lived in IntSet.Internal and was not exported. This utility
function will be needed by IntSet.Internal, IntSetValidity, and
IntMapValidity. The latter two need it to verify that the mask is a power
of two (the bitcount of the mask == 1).

17 months agoAdd unzips for sequences (#494)
David Feuer [Wed, 17 Jan 2018 09:34:55 +0000 (04:34 -0500)] 
Add unzips for sequences (#494)

* Add `unzip` and `unzipWith` to `Data.Sequence`.

* Make `unzipWith` *actually* avoid certain space leaks by
  ensuring that the result trees are constructed in lock-step.

18 months agoUpdate sitemap to point to https pages.
Matt Renaud [Thu, 11 Jan 2018 23:47:47 +0000 (15:47 -0800)] 
Update sitemap to point to https pages.

[ci skip]

18 months agoAdded notes on skew-heap attempt (#490)
Donnacha Oisín Kidney [Thu, 11 Jan 2018 20:13:41 +0000 (20:13 +0000)] 
Added notes on skew-heap attempt (#490)

* Added notes on skew-heap attempt

* added reference to notes in comments

18 months agoCreate sitemap.xml
Matt Renaud [Thu, 11 Jan 2018 19:58:06 +0000 (11:58 -0800)] 
Create sitemap.xml

[ci skip]

18 months agoVerify site ownership for Google analytics/webmaster tools. (#485)
Matt Renaud [Thu, 11 Jan 2018 19:11:43 +0000 (11:11 -0800)] 
Verify site ownership for Google analytics/webmaster tools. (#485)

[ci skip]

18 months agoFix formatting bug.
Matt Renaud [Thu, 11 Jan 2018 18:53:08 +0000 (10:53 -0800)] 
Fix formatting bug.

[ci skip]

18 months agoAdd "introduction and tutorial" to index header.
Matt Renaud [Thu, 11 Jan 2018 18:47:03 +0000 (10:47 -0800)] 
Add "introduction and tutorial" to index header.

[ci skip]

18 months agoChange syntax for implicit :haddock: autolink. (#484)
Matt Renaud [Thu, 11 Jan 2018 17:33:44 +0000 (09:33 -0800)] 
Change syntax for implicit :haddock: autolink. (#484)

Implicit links must now start with a slash '/'

Before:
  Module        => Not possible
  Module#ident  => current_package/Module#ident

After:
  /Module       => current_package/Module
  /Module#ident => current_package/Module#ident

Previously Module#ident would implicitly link to <package>/Module#ident, but
this prevented implicitly linking to <package>/Module (since its not possible to
differentiate between an explicit Haddock package link or an implicit link
within the current package.

[ci skip]

18 months agoAdd favicon to docs. (#487)
Matt Renaud [Thu, 11 Jan 2018 05:26:07 +0000 (21:26 -0800)] 
Add favicon to docs. (#487)

[ci skip]

18 months agoAdd missing highlight:: haskell annotation
Matt Renaud [Wed, 10 Jan 2018 17:55:20 +0000 (09:55 -0800)] 
Add missing highlight:: haskell annotation

Adding this back in fixes syntax highlighting of Haskell source code.

[ci skip]

18 months agoSmall typo fixes in set docs.
Matt Renaud [Wed, 10 Jan 2018 16:29:09 +0000 (08:29 -0800)] 
Small typo fixes in set docs.

[ci skip]

18 months agoMerge branch 'modrenaud'
David Feuer [Tue, 9 Jan 2018 05:13:08 +0000 (00:13 -0500)] 
Merge branch 'modrenaud'

18 months agoAdd docs for containers package.
Matt Renaud [Fri, 29 Dec 2017 02:19:26 +0000 (18:19 -0800)] 
Add docs for containers package.

- Configuration for ReadTheDocs
- Introduction to the containers package
- API and usage docs for Set, IntSat, Map, IntMap, and Sequence

[ci skip]

18 months agoUpdate CONTRIBUTING.md with Pull Request guidance. (#468)
Matt Renaud [Mon, 8 Jan 2018 20:30:45 +0000 (12:30 -0800)] 
Update CONTRIBUTING.md with Pull Request guidance. (#468)

- Link to the libraries@haskell.org discussion if applicable
- Run benchmarks and include results
- Add unit tests
- Update change log
- Let us know how you would like to be credited

Addresses treeowl@s comment in
https://github.com/haskell/containers/pull/455#issuecomment-353204381.

[ci skip]

18 months agoRework Data.Sequence documentation
David Feuer [Sun, 7 Jan 2018 07:56:49 +0000 (02:56 -0500)] 
Rework Data.Sequence documentation

* Add extended introductory information to the module description.

* Add examples of pattern synonym usage.

* Experimentally switch to proper mathematics for big-O. Hopefully
  people won't complain about the loading speed.

* Tighten the performance bound for `chunksOf`.

18 months agoImprove inference for IsString instance for Seq (#481)
David Feuer [Mon, 8 Jan 2018 05:36:28 +0000 (00:36 -0500)] 
Improve inference for IsString instance for Seq (#481)

When I originally added an `IsString` instance for `Seq`, we
conservatively used

```haskell
instance IsString (Seq Char)
```

to allow for the possibility that we might eventually want to write
additional instances. But the result is very bad inference and
a discrepency with the instance for lists. So let's not do that.

18 months agoUpdate replicateM post-AMP (#480)
David Feuer [Mon, 8 Jan 2018 04:45:52 +0000 (23:45 -0500)] 
Update replicateM post-AMP (#480)

Make `replicateM` a synonym for `replicateA` for `base >= 4.8.0`.

18 months agoMerge pull request #476 from treeowl/sum-product
David Feuer [Mon, 8 Jan 2018 03:26:11 +0000 (22:26 -0500)] 
Merge pull request #476 from treeowl/sum-product

 Add Cartesian products and disjoint unions for Set

18 months agoMark Internal modules not-home (#477)
David Feuer [Sun, 7 Jan 2018 10:29:01 +0000 (05:29 -0500)] 
Mark Internal modules not-home (#477)

Let Haddock know that it shouldn't consider the `Internal` modules
home for any identifiers. This should've been done when I exposed
those internal modules. Whoops.

18 months agoAdd tests for new Set functions
David Feuer [Fri, 5 Jan 2018 06:33:11 +0000 (01:33 -0500)] 
Add tests for new Set functions

Add QuickCheck properties for `cartesianProduct` and
`disjointUnion`.

18 months agoAdd Cartesian products and disjoint unions for Set
Edward Kmett [Fri, 5 Jan 2018 06:26:24 +0000 (01:26 -0500)] 
Add Cartesian products and disjoint unions for Set

Add

  * `cartesianProduct :: Set a -> Set b -> Set (a, b)`
  * `disjointUnion :: Set a -> Set b -> Set (Either a b)`

Fixes #442

18 months agoMerge pull request #474 from treeowl/powerSet
David Feuer [Thu, 4 Jan 2018 07:44:20 +0000 (02:44 -0500)] 
Merge pull request #474 from treeowl/powerSet

Add powerSet to Data.Set

18 months agoAdd a test for Set.powerSet
David Feuer [Wed, 3 Jan 2018 21:12:53 +0000 (16:12 -0500)] 
Add a test for Set.powerSet

18 months agoAdd powerSet to Data.Set
Edward Kmett [Wed, 3 Jan 2018 21:10:55 +0000 (16:10 -0500)] 
Add powerSet to Data.Set

This should be considerably more efficient than what can be written
using the public API because it can glue trees together without
needing to perform a full divide-and-conquer union.

Addresses #442

18 months agoStop hand-unboxing shifts (#471)
David Feuer [Wed, 3 Jan 2018 21:39:01 +0000 (16:39 -0500)] 
Stop hand-unboxing shifts (#471)

We used to unbox shifts manually to make sure things inlined
adequately. Based on my benchmarks, that doesn't seem to be
necessary anymore. The differences are small, and for `IntMap`
benchmarks actually seem to favor doing the simple thing.

18 months agoAdd validity checks for IntSet and IntMap (#456)
Matt Renaud [Sat, 30 Dec 2017 17:08:11 +0000 (09:08 -0800)] 
Add validity checks for IntSet and IntMap (#456)

These checks codify the invariants laid out in the IntSet and IntMap comments. We
add validity checks for constructed IntSets and IntMaps as well as union,
intersection, and difference operations on them.

* Add validity tests for functions producing IntSets/IntMaps.
* Add field comments for IntMap Bin constructor.
* Move validity checks into tests/.