packages/containers.git
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"

8 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.

9 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.

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

13 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/.

18 months agoAdd stack.yaml file (#463)
Matt Renaud [Thu, 28 Dec 2017 18:27:14 +0000 (10:27 -0800)] 
Add stack.yaml file (#463)

* Add stack.yaml file to containers.

`stack setup` fails due to ChasingBottoms missing from Stackage

We default to lts-9.20 because lts-10.0 is currently not supported by many
development tools (such as intero) because ghc-mod does not yet support GHC
8.2 (https://github.com/DanielG/ghc-mod/issues/900).

This was tested and works with resolvers lts-10.0 and lts-9.20.

Using older resolvers <=lts-7.24 causes a conflict with the package ranges
specified in containers.cabal.

* Remove `stack init` step in CONTRIBUTING.md.

18 months agoUpdate CONTRIBUTING.md with benchmark instructions (#461)
Matt Renaud [Tue, 26 Dec 2017 04:57:24 +0000 (20:57 -0800)] 
Update CONTRIBUTING.md with benchmark instructions (#461)

This includes instructions for building and running benchmarks with both cabal-install and stack.

18 months agoAdd MonadFix instance for Data.Tree (#451)
David Feuer [Sat, 23 Dec 2017 05:52:13 +0000 (00:52 -0500)] 
Add MonadFix instance for Data.Tree (#451)

* Add a `MonadFix` instance for `Tree`. This is based on an instance for
  a somewhat more general type by G. Allais.
  See [MonadTree.hs](https://gist.github.com/gallais/4c59b949c743c0a85cab55dcb73aaf7c).

* Make `>>=` for `Tree` stricter. Previously, it was too lazy to satisfy the
  `Monad` laws, and that laziness was not particularly valuable.

* Add a small test suite for `Tree`. The `Arbitrary` instance is mediocre,
  and so is the `MonadFix` test, but something definitely seems better than
  nothing!

* Bump QuickCheck version to 2.7.1 for `genericShrink`.

Fixes #452

18 months agoImprove error message for `index` (#457)
Matt Renaud [Fri, 22 Dec 2017 17:10:30 +0000 (09:10 -0800)] 
Improve error message for `index` (#457)

* Improve error message for `index`

When the index is out of bounds mention which function is causing the error. We include the index `i` in the error message because it may be useful in debugging (-1 vs large number could narrow down where to look).

This was originally mentioned in https://github.com/haskell/containers/issues/347.

* Specify `Data.Sequence.index` in error message.

18 months agoAdd operator IntMap.!?. (#454)
Matt Renaud [Wed, 20 Dec 2017 22:56:24 +0000 (14:56 -0800)] 
Add operator IntMap.!?. (#454)

Add operator `IntMap.!?`.

This operator was added to `Data.Map` but was accidentally left out of the `IntMap`
API.

```haskell
(!?) :: IntMap a -> Key -> Maybe a
```

Fixes #453

* Add missing import of operator (!?) from internal module.

* Add operator !? property tests to test list.

* Fix precedence issue in properties test.

* Add @since 0.5.11 annotation to Data.IntMap.!?.

* Use Prelude.map instead of <$> in intmap-properties.

<$> was not introduced into base until GHC 7.10 so integration tests run against
earlier compilers fail[1]. We go with Prelude.map since it is the simplest way
to be compatible with all GHC versions.

Alternatives considered:
  - import Data.Functor ((<$>)) or fmap
    - causes unused import warnings for GHC versions with <$> in base.
  - conditionally import <$>
    - Unnecessary noise in compile list.

[1]
https://travis-ci.org/haskell/containers/builds/318987347?utm_source=github_status&utm_medium=notification

18 months agoCreate CONTRIBUTING.md (#455)
Matt Renaud [Wed, 20 Dec 2017 22:37:40 +0000 (14:37 -0800)] 
Create CONTRIBUTING.md (#455)

Create CONTRIBUTING.md

18 months agoUpdate changelog
David Feuer [Mon, 18 Dec 2017 20:06:12 +0000 (15:06 -0500)] 
Update changelog

18 months agoAdd @since-annotations (#447)
Simon Jakobi [Mon, 18 Dec 2017 19:13:06 +0000 (20:13 +0100)] 
Add @since-annotations (#447)

* Add @since-annotations for v0.5.9.1

* Add @since-annotations for v0.5.8

* Add @since-annotations for v0.5.7

* Add @since-annotations for v0.5.6.2

* Add @since-annotations for v0.5.4

This change doesn't add annotations for the Typeable[0-2] instances that the
changelog claims were added in v0.5.4.0 as haddocks on Hackage show the same
instances for earlier versions like v0.4.0.0.

* Add @since-annotions for the Data.IntMap.Merge additions in v0.5.9

NB the change on the annotations for `merge` and `mergeA`.

* Add annotations for the contents of Data.Map.Merge.*

18 months agoMerge pull request #348 from benjamin-hodgson/mapKeysWith-docs
David Feuer [Mon, 18 Dec 2017 18:01:31 +0000 (13:01 -0500)] 
Merge pull request #348 from benjamin-hodgson/mapKeysWith-docs

Improve documentation of mapKeysWith

18 months agoMerge pull request #431 from phadej/restrictKeys-example
David Feuer [Mon, 18 Dec 2017 17:58:01 +0000 (12:58 -0500)] 
Merge pull request #431 from phadej/restrictKeys-example

Add restictKeys example via intersect, also withoutKeys

18 months agoMerge pull request #444 from RyanGlScott/missing-home-modules
David Feuer [Mon, 18 Dec 2017 14:30:00 +0000 (09:30 -0500)] 
Merge pull request #444 from RyanGlScott/missing-home-modules

Fix -Wmissing-home-modules warnings

18 months agoFix -Wmissing-home-modules warnings
Ryan Scott [Wed, 6 Dec 2017 14:34:25 +0000 (09:34 -0500)] 
Fix -Wmissing-home-modules warnings

Fixes #434.