packages/containers.git
3 years agoUpdate changelog.md
David Feuer [Mon, 30 May 2016 23:36:56 +0000 (19:36 -0400)] 
Update changelog.md

3 years agoMerge pull request #270 from treeowl/seq-delete
David Feuer [Mon, 30 May 2016 23:34:20 +0000 (19:34 -0400)] 
Merge pull request #270 from treeowl/seq-delete

Add deleteAt to Data.Sequence

3 years agoAdd deleteAt to Data.Sequence
David Feuer [Mon, 30 May 2016 22:44:00 +0000 (18:44 -0400)] 
Add deleteAt to Data.Sequence

This is messy, and may remain so, but it would be nice to find
some way to clean it up a bit. Also, we can and should be
more eager about rebuilding and should look for opportunities to
use arithmetic to figure out sizes.

3 years agoMerge pull request #268 from treeowl/bench-insertAt
David Feuer [Mon, 30 May 2016 04:54:51 +0000 (00:54 -0400)] 
Merge pull request #268 from treeowl/bench-insertAt

Add insertAt benchmark

3 years agoAdd insertAt benchmark
David Feuer [Mon, 30 May 2016 04:46:58 +0000 (00:46 -0400)] 
Add insertAt benchmark

Make `insertAt` rebuild the tree eagerly, which saves a little
time and avoids the possibility that large thunks will build
up at the root of the tree when multiple elements are inserted.

For long sequences `insertAt` is around 4.6 times as fast as
splitting the sequence and re-forming it around the new element.

3 years agoMerge pull request #267 from treeowl/rename-cycleN
David Feuer [Mon, 30 May 2016 04:51:38 +0000 (00:51 -0400)] 
Merge pull request #267 from treeowl/rename-cycleN

Rename cycleN to cycleTaking

3 years agoRename cycleN to cycleTaking
David Feuer [Mon, 30 May 2016 04:03:11 +0000 (00:03 -0400)] 
Rename cycleN to cycleTaking

Make cycleTaking more tolerant of edge cases to match
list equivalent. Add QuickCheck property.

3 years agoMerge pull request #266 from treeowl/seq-safe-index
David Feuer [Mon, 30 May 2016 03:49:35 +0000 (23:49 -0400)] 
Merge pull request #266 from treeowl/seq-safe-index

Add lookup and (!?) to Data.Sequence

3 years agoMerge pull request #260 from treeowl/alterF-IntMap
David Feuer [Mon, 30 May 2016 03:49:00 +0000 (23:49 -0400)] 
Merge pull request #260 from treeowl/alterF-IntMap

Add alterF for Data.IntMap

3 years agoAdd alterF for Data.IntMap
David Feuer [Wed, 25 May 2016 07:17:14 +0000 (03:17 -0400)] 
Add alterF for Data.IntMap

The implementation is just taken from `Control.Lens.At`, because
`IntMap` lookup is so fast there's no point in trying to be clever
about it.

Clear up unused-binding warning in `Data.Sequence`.

3 years agoAdd lookup and (!?) to Data.Sequence
David Feuer [Mon, 30 May 2016 02:12:16 +0000 (22:12 -0400)] 
Add lookup and (!?) to Data.Sequence

Also improve the QuickCheck properties for `chunksOf` and
`insertAt`, and add pattern synonym documentation.

3 years agoMerge pull request #265 from treeowl/seq-insert
David Feuer [Mon, 30 May 2016 02:41:04 +0000 (22:41 -0400)] 
Merge pull request #265 from treeowl/seq-insert

Add insertAt to Data.Sequence

3 years agoAdd insertAt to Data.Sequence
David Feuer [Sun, 29 May 2016 20:28:22 +0000 (16:28 -0400)] 
Add insertAt to Data.Sequence

3 years agoMerge pull request #259 from treeowl/strictify-seq-adjust
David Feuer [Wed, 25 May 2016 05:07:00 +0000 (01:07 -0400)] 
Merge pull request #259 from treeowl/strictify-seq-adjust

Make Data.Sequence.adjust helpers stricter

3 years agoMake Data.Sequence.adjust helpers stricter
David Feuer [Wed, 25 May 2016 04:38:40 +0000 (00:38 -0400)] 
Make Data.Sequence.adjust helpers stricter

The helper functions now use bang patterns to ensure strictness in their
`Int` arguments.

Use a single unsigned comparison instead of two signed ones
for `adjust` and `index`.

3 years agoMerge pull request #258 from treeowl/cycleNlog
David Feuer [Tue, 24 May 2016 22:57:19 +0000 (18:57 -0400)] 
Merge pull request #258 from treeowl/cycleNlog

Add cycleN to changelog; fix up its documentation.

3 years agoAdd cycleN to changelog; fix up its documentation.
David Feuer [Tue, 24 May 2016 22:55:18 +0000 (18:55 -0400)] 
Add cycleN to changelog; fix up its documentation.

3 years agoMerge pull request #148 from treeowl/cycleN
David Feuer [Tue, 24 May 2016 21:44:11 +0000 (17:44 -0400)] 
Merge pull request #148 from treeowl/cycleN

Export cycleN

3 years agoExport cycleN
David Feuer [Mon, 16 Mar 2015 15:20:56 +0000 (11:20 -0400)] 
Export cycleN

Export `cycleN` and document its performance.

3 years agoUpdate changelog.md
David Feuer [Tue, 24 May 2016 18:59:10 +0000 (14:59 -0400)] 
Update changelog.md

3 years agoMerge pull request #256 from treeowl/use-quickcheck-fun
David Feuer [Tue, 24 May 2016 18:49:54 +0000 (14:49 -0400)] 
Merge pull request #256 from treeowl/use-quickcheck-fun

Use QuickCheck function support.

3 years agoUse QuickCheck function support
David Feuer [Tue, 24 May 2016 17:01:22 +0000 (13:01 -0400)] 
Use QuickCheck function support

Previously, a number of tests used functions directly as
arguments to QuickCheck properties. As a result, they needed
to include the horrifying `Text.Show.Functions`.

Now the properties requiring functions use
`Test.QuickCheck.Function.Fun`, which has both a meaningful
`Show` instance and proper shrinks.

3 years agoMerge pull request #255 from treeowl/cabal-more-exts
David Feuer [Tue, 24 May 2016 15:56:31 +0000 (11:56 -0400)] 
Merge pull request #255 from treeowl/cabal-more-exts

Remove unnecessary extensions from tests

3 years agoRemove unnecessary extensions from tests
David Feuer [Tue, 24 May 2016 06:03:13 +0000 (02:03 -0400)] 
Remove unnecessary extensions from tests

Use `Text.Show.Functions` (blech!) to avoid declaring our own,
similar instances and using `FlexibleInstances` to do so (double
blech!). Remove unused invocation of `GeneralizedNewtypeDeriving`.

3 years agoMerge pull request #254 from treeowl/inline-zip
David Feuer [Tue, 24 May 2016 04:58:21 +0000 (00:58 -0400)] 
Merge pull request #254 from treeowl/inline-zip

Speed up zipWith some more

3 years agoSpeed up zipWith some more
David Feuer [Tue, 24 May 2016 04:26:00 +0000 (00:26 -0400)] 
Speed up zipWith some more

This one's all about making nice to GHC by pulling
local functions to the top level and marking them
inline, as well as eta-expanding at a recursive
call site.

Old (after recent `splitAt` improvements):

benchmarking zip/ix10000/5000
time                 8.806 μs   (8.768 μs .. 8.857 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 8.787 μs   (8.766 μs .. 8.879 μs)
std dev              113.3 ns   (30.31 ns .. 244.0 ns)

benchmarking zip/nf100
time                 13.19 μs   (13.15 μs .. 13.24 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 13.19 μs   (13.15 μs .. 13.28 μs)
std dev              157.8 ns   (86.36 ns .. 288.1 ns)

benchmarking zip/nf10000
time                 1.768 ms   (1.764 ms .. 1.774 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 1.778 ms   (1.772 ms .. 1.793 ms)
std dev              29.50 μs   (16.59 μs .. 56.72 μs)

New:

benchmarking zip/ix10000/5000
time                 7.684 μs   (7.668 μs .. 7.704 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 7.685 μs   (7.675 μs .. 7.707 μs)
std dev              46.68 ns   (27.98 ns .. 73.76 ns)

benchmarking zip/nf100
time                 9.152 μs   (9.139 μs .. 9.170 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 9.166 μs   (9.148 μs .. 9.197 μs)
std dev              76.90 ns   (42.73 ns .. 140.9 ns)

benchmarking zip/nf10000
time                 1.294 ms   (1.291 ms .. 1.298 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 1.295 ms   (1.292 ms .. 1.298 ms)
std dev              10.51 μs   (7.936 μs .. 14.12 μs)

3 years agoUse pattern matching in splitAt
David Feuer [Tue, 24 May 2016 03:29:55 +0000 (23:29 -0400)] 
Use pattern matching in splitAt

At the top of the tree, we can match on specific numbers
instead of using comparisons.

3 years agoRemove pair rules (#253)
David Feuer [Mon, 23 May 2016 21:27:07 +0000 (17:27 -0400)] 
Remove pair rules (#253)

* Scrap alterF pair rewrite rules

The rules rewrote to an overly strict implementation.
Specifically, if the function gives us

```haskell
(b, undefined :: Maybe a)
```

then we need to produce

```haskell
(b, undefined :: Map k a)
```

Making the rules correct greatly reduces their benefit even
when they're beneficial, and introduces situations where they
may be harmful. So sadly I'm scrapping them.

* Re-fix Haddock markup for alterF

That was bundled with the reverted commits.

3 years agoMerge pull request #251 from treeowl/nix-splitAt-prime
David Feuer [Mon, 23 May 2016 03:13:33 +0000 (23:13 -0400)] 
Merge pull request #251 from treeowl/nix-splitAt-prime

Nix splitAt'

3 years agoNix splitAt'
David Feuer [Mon, 23 May 2016 03:11:20 +0000 (23:11 -0400)] 
Nix splitAt'

`splitAt'` wasn't really doing anything good, and certainly
wasn't worth the extra source code.

3 years agoMerge pull request #249 from treeowl/direct-middle
David Feuer [Mon, 23 May 2016 02:52:10 +0000 (22:52 -0400)] 
Merge pull request #249 from treeowl/direct-middle

Stop fearing the middle

3 years agoStop fearing the middle
David Feuer [Mon, 23 May 2016 02:33:39 +0000 (22:33 -0400)] 
Stop fearing the middle

A couple years ago I thought it *must* be a good idea to ever look down
the middle if it could possibly be avoided, but I never had any
benchmarks to support it, and it seems pretty silly in retrospect.
Reverting pending some numbers demonstrating it's really the way to go.

3 years agoMerge pull request #248 from treeowl/remove-redundant-eq
David Feuer [Mon, 23 May 2016 01:31:35 +0000 (21:31 -0400)] 
Merge pull request #248 from treeowl/remove-redundant-eq

Remove redundant Eq constraint

3 years agoMerge pull request #247 from treeowl/fix-at-strictness
David Feuer [Mon, 23 May 2016 01:28:34 +0000 (21:28 -0400)] 
Merge pull request #247 from treeowl/fix-at-strictness

Fix strictness of alterF rewrite target

3 years agoFix strictness of alterF rewrite target
David Feuer [Mon, 23 May 2016 01:10:38 +0000 (21:10 -0400)] 
Fix strictness of alterF rewrite target

The strict `alterF` rewrite target for `(,) b` was too strict.
I *think* it now has the correct semantics.

3 years agoRemove redundant Eq constraint
David Feuer [Sun, 22 May 2016 23:26:35 +0000 (19:26 -0400)] 
Remove redundant Eq constraint

The `Arbitrary (Map k v)` had a totally redundant `Eq k`
constraint for some reason.

3 years agoMerge pull request #246 from treeowl/alterF-pair
David Feuer [Sun, 22 May 2016 23:21:57 +0000 (19:21 -0400)] 
Merge pull request #246 from treeowl/alterF-pair

Add rewrite rule for alterF with pairs

3 years agoAdd rewrite rule for alterF with pairs
David Feuer [Sun, 22 May 2016 22:27:57 +0000 (18:27 -0400)] 
Add rewrite rule for alterF with pairs

Also fix alterF documentation formatting.

3 years agoChangelog update
David Feuer [Sun, 22 May 2016 18:34:23 +0000 (14:34 -0400)] 
Changelog update

3 years agoMerge pull request #222 from treeowl/foldMapWithIndexSequence
David Feuer [Sun, 22 May 2016 18:31:49 +0000 (14:31 -0400)] 
Merge pull request #222 from treeowl/foldMapWithIndexSequence

Add foldMapWithIndex for Data.Sequence

3 years agoAdd foldMapWithIndex for Data.Sequence
David Feuer [Fri, 13 May 2016 00:19:01 +0000 (20:19 -0400)] 
Add foldMapWithIndex for Data.Sequence

This finishes the indexed folds. Implementing `foldrWithIndex`
using this function gives wretched performance, unfortunately.
It would be nice to know why, and whether anything can be done
about that.

Also, clean up some monoid syntax and import `Data.Semigroup`
qualified (we only need it to write one instance).

3 years agoMerge pull request #245 from Gabriel439/gabriel/cabal_bench_2
David Feuer [Sun, 22 May 2016 04:27:10 +0000 (00:27 -0400)] 
Merge pull request #245 from Gabriel439/gabriel/cabal_bench_2

Integrate benchmarks with `cabal`. Fixes #188

3 years agoIntegrate benchmarks with `cabal`. Fixes #188
Gabriel Gonzalez [Sun, 22 May 2016 04:04:14 +0000 (21:04 -0700)] 
Integrate benchmarks with `cabal`. Fixes #188

3 years agoMerge pull request #146 from treeowl/chunks
David Feuer [Sun, 22 May 2016 03:21:23 +0000 (23:21 -0400)] 
Merge pull request #146 from treeowl/chunks

Add chunksOf to Data.Sequence

3 years agoAdd chunksOf to Data.Sequence
David Feuer [Mon, 16 Mar 2015 00:50:40 +0000 (20:50 -0400)] 
Add chunksOf to Data.Sequence

Break up a sequence into pieces of a given size. Based on
`Data.List.Split.chunksOf` and implemented using `splitMap`.

Also add an appropriate QuickCheck property.

3 years agoUpdate changelog.md
David Feuer [Sat, 21 May 2016 21:43:53 +0000 (17:43 -0400)] 
Update changelog.md

3 years agoMerge pull request #242 from treeowl/clean-split
David Feuer [Sat, 21 May 2016 21:35:12 +0000 (17:35 -0400)] 
Merge pull request #242 from treeowl/clean-split

Speed up sequence splitting and zipping some more

3 years agoSpeed up sequence splitting and zipping some more
David Feuer [Sat, 21 May 2016 06:01:50 +0000 (02:01 -0400)] 
Speed up sequence splitting and zipping some more

Rewrite `splitAt`, `take`, and `drop` helper functions to build full results
instead of returning pieces, and to build their results eagerly, instead of
(unnecessarily) suspending them lazily. This has a major impact on performance.
GHC specialization can't help us, because we're now treating the top layer of
the tree differently in every helper. As a result, there's a lot of source
code, but that's our problem.

Benchmark results, compared to containers 0.5.7.1:

Old: benchmarking splitAt/append/10
time                 1.950 ms   (1.946 ms .. 1.954 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 1.952 ms   (1.949 ms .. 1.958 ms)
std dev             53 12.41 μs   (7.154 μs .. 19.01 μs)

New: benchmarking splitAt/append/10
time                 1.056 ms   (1.050 ms .. 1.065 ms)
                     0.995 R²   (0.983 R² .. 1.000 R²)
mean                 1.073 ms   (1.057 ms .. 1.147 ms)
std dev              97.06 μs   (9.638 μs .. 221.7 μs)
variance introduced by outliers: 68% (severely inflated)

Old: benchmarking splitAt/append/100
time                 13.81 ms   (13.76 ms .. 13.84 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 13.88 ms   (13.84 ms .. 13.95 ms)
std dev              119.1 μs   (48.84 μs .. 204.2 μs)

New: benchmarking splitAt/append/100
time                 8.028 ms   (8.014 ms .. 8.046 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 8.041 ms   (8.029 ms .. 8.075 ms)
std dev              51.02 μs   (16.07 μs .. 94.69 μs)

Old: benchmarking splitAt/append/1000
time                 25.58 ms   (25.44 ms .. 25.75 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 25. ms   (25.47 ms .. 25.63 ms)
std dev              184.0 μs   (128.7 μs .. 272.0 μs)

New: benchmarking splitAt/append/1000
time                 15.30 ms   (15.20 ms .. 15.41 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 15.32 ms   (15.26 ms .. 15.45 ms)
std dev              190.0 μs   (89.60 μs .. 351.1 μs)

Old: benchmarking zip/ix10000/5000
time                 13.52 μs   (13.41 μs .. 13.77 μs)
                     0.996 R²   (0.987 R² .. 1.000 R²)
mean                 13.65 μs   (13.50 μs .. 14.19 μs)
std dev              882.1 ns   (174.4 ns .. 1.839 μs)
variance introduced by outliers: 72% (severely inflated)

New: benchmarking zip/ix10000/5000
time                 8.806 μs   (8.768 μs .. 8.857 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 8.787 μs   (8.766 μs .. 8.879 μs)
std dev              113.3 ns   (30.31 ns .. 244.0 ns)

Old: benchmarking zip/nf100
time                 19.99 μs   (19.96 μs .. 20.04 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 19.98 μs   (19.96 μs .. 20.00 μs)
std dev              64.04 ns   (34.52 ns .. 100.9 ns)

New: benchmarking zip/nf100
time                 13.19 μs   (13.15 μs .. 13.24 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 13.19 μs   (13.15 μs .. 13.28 μs)
std dev              157.8 ns   (86.36 ns .. 288.1 ns)

Old: benchmarking zip/nf10000
time                 2.578 ms   (2.567 ms .. 2.591 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 2.584 ms   (2.574 ms .. 2.598 ms)
std dev              40.16 μs   (30.17 μs .. 57.04 μs)

New: benchmarking zip/nf10000
time                 1.768 ms   (1.764 ms .. 1.774 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 1.778 ms   (1.772 ms .. 1.793 ms)
std dev              29.50 μs   (16.59 μs .. 56.72 μs)

3 years agoFix spelling error in comment
David Feuer [Fri, 20 May 2016 04:03:06 +0000 (00:03 -0400)] 
Fix spelling error in comment

3 years agoMerge pull request #240 from treeowl/fmapreverse
David Feuer [Fri, 20 May 2016 03:23:02 +0000 (23:23 -0400)] 
Merge pull request #240 from treeowl/fmapreverse

Fuse fmap with reverse for Data.Sequence

3 years agoFuse fmap with reverse for Data.Sequence
David Feuer [Fri, 20 May 2016 03:11:43 +0000 (23:11 -0400)] 
Fuse fmap with reverse for Data.Sequence

Add rules fusing `fmap f . reverse` and `reverse . fmap f`
for `Data.Sequence`. These make mapping over a sequence and
reversing it simultaneously as cheap as just mapping over it.

Closes #238.

3 years agoMerge pull request #239 from treeowl/map-strict-trav
David Feuer [Fri, 20 May 2016 02:54:27 +0000 (22:54 -0400)] 
Merge pull request #239 from treeowl/map-strict-trav

Make Data.Map.Strict.traverseWithKey strict enough

3 years agoMake Data.Map.Strict.traverseWithKey strict enough
David Feuer [Fri, 20 May 2016 02:29:24 +0000 (22:29 -0400)] 
Make Data.Map.Strict.traverseWithKey strict enough

Previously, `Data.Map.Strict` re-exported `traverseWithKey`
from `Data.Map.Base`. That function could produce a map containing
bottoms.

3 years agoMerge pull request #237 from treeowl/other-extensions
David Feuer [Fri, 20 May 2016 00:43:26 +0000 (20:43 -0400)] 
Merge pull request #237 from treeowl/other-extensions

Let Cabal know that we use CPP and BangPatterns

3 years agoNote Data.Sequence performance improvements
David Feuer [Fri, 20 May 2016 00:19:28 +0000 (20:19 -0400)] 
Note Data.Sequence performance improvements

3 years agoLet Cabal know that we use CPP and BangPatterns
David Feuer [Thu, 19 May 2016 23:51:41 +0000 (19:51 -0400)] 
Let Cabal know that we use CPP and BangPatterns

Use `other-extensions` to indicate this. I'm not convinced it's
worth the trouble to try to get real specific about what
extensions we use for each GHC version.

3 years agoMerge pull request #233 from treeowl/unscope-nonghc
David Feuer [Thu, 19 May 2016 23:43:15 +0000 (19:43 -0400)] 
Merge pull request #233 from treeowl/unscope-nonghc

Only use ScopedTypeVariables for GHC

3 years agoOnly use ScopedTypeVariables for GHC
David Feuer [Tue, 17 May 2016 20:58:25 +0000 (16:58 -0400)] 
Only use ScopedTypeVariables for GHC

This isn't (yet) standard, and we don't absolutely need it.
It is nice, however, to be able to give the type signature it
enables, so we can use it when compiling with GHC.

3 years agoMerge pull request #236 from treeowl/strictify-seq-splitat
David Feuer [Thu, 19 May 2016 23:02:38 +0000 (19:02 -0400)] 
Merge pull request #236 from treeowl/strictify-seq-splitat

Speed up Data.Sequence.splitAt and zipWith

3 years agoSpeed up Data.Sequence.splitAt and zipWith
David Feuer [Thu, 19 May 2016 01:45:29 +0000 (21:45 -0400)] 
Speed up Data.Sequence.splitAt and zipWith

Previously, `splitAt` returned a lazy pair, and was pretty much
lazy throughout. Now it's about as strict as it's allowed to be.

Avoid allocating anything extra when splitting at or before the
beginning of a sequence.

Fix misplaced bang annotation (my fault).

Hand-inline and reduce the splitting of the top of the tree. This
avoids a separate cons step at the end, saving some time when
splitting small sequences. This is particularly helpful for
zip performance.

Note: `zip` performance is, for some reason, rather sensitive to
how the inliner handles `deepL`. I don't know why. I also don't
really know how to fix it. Splitting in general is rather complicated
and hard to follow. It would be nice to fix that.

Rewrite `take` and `drop` so they don't build the parts of the
tree they don't actually use. Previously, they were written
using `splitAt`.

Use custom left and right views for `FingerTree`s. This was a side
effect of something I thought I wanted to do, but it's a good idea
anyway.

3 years agoMerge pull request #223 from treeowl/strictify-pairs
David Feuer [Thu, 19 May 2016 00:03:32 +0000 (20:03 -0400)] 
Merge pull request #223 from treeowl/strictify-pairs

Remove a bunch of unnecessary laziness from Data.Map

3 years agoRemove a bunch of unnecessary laziness
David Feuer [Thu, 12 May 2016 22:20:18 +0000 (18:20 -0400)] 
Remove a bunch of unnecessary laziness

Lots of functions in `Data.Map.Base` used lazy pairs and such for no
obviously good reason. As a result, they sometimes did strange things
like building up chains of suspensions to rebuild trees.

3 years agoMerge pull request #235 from haskell/changelog-foldtree
David Feuer [Wed, 18 May 2016 23:30:12 +0000 (19:30 -0400)] 
Merge pull request #235 from haskell/changelog-foldtree

Update changelog.md

3 years agoUpdate changelog.md changelog-foldtree
David Feuer [Wed, 18 May 2016 23:25:50 +0000 (19:25 -0400)] 
Update changelog.md

3 years agoMerge pull request #234 from treeowl/alterF
David Feuer [Wed, 18 May 2016 23:12:57 +0000 (19:12 -0400)] 
Merge pull request #234 from treeowl/alterF

Add alterF to Data.Map

3 years agoAdd `alterF` for Data.Map
David Feuer [Mon, 2 May 2016 18:29:36 +0000 (14:29 -0400)] 
Add `alterF` for Data.Map

Use a bit queue to implement `alterF` for `Data.Map`. This is fairly
competitive with the simple implementation in `Control.Lens.At`
even with `Int` keys. For keys that are more expensive to compare,
it should be substantially better. In case of extremely large maps
that would overflow the bit queue, this falls back to a slower,
Yoneda-based, implementation. This code is disabled when the word
size is at least 61, as maps with nearly a quadrillion entries seem
somewhat unlikely.

Add rules to specialize to `Const` and `Identity` functors.

Add QuickCheck properties to supplement the unit tests, including
ones that should trigger the rewrite rules and ones that should not.

Remove some more pre-7.0 junk.

3 years agoImplement lens-compatible `at` function
Phil Ruffwind [Mon, 28 Mar 2016 00:49:35 +0000 (20:49 -0400)] 
Implement lens-compatible `at` function

Akin to `alter` but allows an arbitrary Functor.
Add benchmarks for `at`
Add tests for `at`
Add `at` from Lens to benchmarks for comparison

3 years agoMerge pull request #232 from dmwit/master
David Feuer [Wed, 18 May 2016 19:24:30 +0000 (15:24 -0400)] 
Merge pull request #232 from dmwit/master

Add a catamorphism on Trees

3 years agoadd a catamorphism on Trees
Daniel Wagner [Tue, 17 May 2016 17:21:07 +0000 (10:21 -0700)] 
add a catamorphism on Trees

3 years agoMerge pull request #219 from treeowl/intmap-binbetter
David Feuer [Sun, 8 May 2016 19:46:55 +0000 (15:46 -0400)] 
Merge pull request #219 from treeowl/intmap-binbetter

Speed up IntMap

3 years agoSpeed up IntMap
David Feuer [Sun, 8 May 2016 00:54:24 +0000 (20:54 -0400)] 
Speed up IntMap

`delete`, `alter`, `update`, etc., used a `bin` smart
constructor to avoid installing any non-root `Nil`s. Now only
the ones that could have become `Nil` are checked, which is
a good bit cheaper since they're in cache. `adjustWithKey`
was implemented using `updateWithKey`, but in fact it never
needs to worry about `Nil`s, so implementing it directly
eliminates all such checks.

Make `updateLookupWithKey` in `Data.IntMap.Lazy` strict in its
recursive call to avoid essentially useless lazy pair allocation.

3 years agoMerge pull request #213 from treeowl/adjust-maps-faster
David Feuer [Mon, 2 May 2016 17:53:23 +0000 (13:53 -0400)] 
Merge pull request #213 from treeowl/adjust-maps-faster

Speed up adjust and adjustWithKey

3 years agoSpeed up adjust and adjustWithKey
David Feuer [Mon, 2 May 2016 17:07:19 +0000 (13:07 -0400)] 
Speed up adjust and adjustWithKey

Previously, `adjustWithKey` was implemented using `updateWithKey`.
`updateWithKey` needs to rebalance as it builds the result tree.
`adjustWithKey` never changes the shape of the tree, so
rebalancing on the way up is a waste of time.

3 years agoMerge pull request #212 from treeowl/clean-twi
David Feuer [Tue, 26 Apr 2016 19:17:37 +0000 (15:17 -0400)] 
Merge pull request #212 from treeowl/clean-twi

Clean up traverseWithIndex

3 years agoClean up traverseWithIndex
David Feuer [Tue, 26 Apr 2016 18:42:01 +0000 (14:42 -0400)] 
Clean up traverseWithIndex

Instead of copying the code over, use polymorphic
`traverseWithIndexDigit` and `traverseWithIndexNode`, inlined,
to implement `traverseWithIndexDigitE`, etc. This gives us the
desired specialization with less source code.

3 years agoMerge pull request #208 from treeowl/dump-ancient-impls
David Feuer [Tue, 26 Apr 2016 15:35:14 +0000 (11:35 -0400)] 
Merge pull request #208 from treeowl/dump-ancient-impls

Remove all support for nhc98 and GHC <7

3 years agoRemove all support for nhc98 and GHC <7
David Feuer [Tue, 26 Apr 2016 06:01:49 +0000 (02:01 -0400)] 
Remove all support for nhc98 and GHC <7

We no longer make any effort whatsoever to support any
version of nhc98 or any version of GHC before 7.0. We
cannot properly support implementations our continuous
integration does not test, and these ones are fairly
rare.

Bump version number

3 years agoMerge pull request #207 from treeowl/uncase-intmap
David Feuer [Tue, 26 Apr 2016 05:42:54 +0000 (01:42 -0400)] 
Merge pull request #207 from treeowl/uncase-intmap

Replace some case exprs with argument patterns

3 years agoMerge pull request #206 from treeowl/bang-intset
David Feuer [Tue, 26 Apr 2016 05:42:14 +0000 (01:42 -0400)] 
Merge pull request #206 from treeowl/bang-intset

Use BangPatterns to clean up Data.IntSet

3 years agoReplace some case exprs with argument patterns
David Feuer [Tue, 26 Apr 2016 05:14:09 +0000 (01:14 -0400)] 
Replace some case exprs with argument patterns

3 years agoUse BangPatterns to clean up Data.IntSet
David Feuer [Tue, 26 Apr 2016 04:43:54 +0000 (00:43 -0400)] 
Use BangPatterns to clean up Data.IntSet

Also remove some `case` expressions in favor of argument
patterns.

Remove strictness CPP macros from `containers.h`.

3 years agoMerge pull request #205 from treeowl/bang-intmap
David Feuer [Tue, 26 Apr 2016 03:43:14 +0000 (23:43 -0400)] 
Merge pull request #205 from treeowl/bang-intmap

Use BangPatterns to reduce clutter in Data.IntMap

3 years agoUse BangPatterns to reduce clutter in Data.IntMap
David Feuer [Tue, 26 Apr 2016 00:41:01 +0000 (20:41 -0400)] 
Use BangPatterns to reduce clutter in Data.IntMap

3 years agoMerge pull request #204 from treeowl/bang-set
David Feuer [Tue, 26 Apr 2016 00:24:30 +0000 (20:24 -0400)] 
Merge pull request #204 from treeowl/bang-set

Use bang patterns to reduce clutter in Data.Set

3 years agoUse bang patterns to reduce clutter in Data.Set
David Feuer [Mon, 25 Apr 2016 20:25:05 +0000 (16:25 -0400)] 
Use bang patterns to reduce clutter in Data.Set

3 years agoMerge pull request #203 from treeowl/bang-map
David Feuer [Mon, 25 Apr 2016 20:17:47 +0000 (16:17 -0400)] 
Merge pull request #203 from treeowl/bang-map

Use bang patterns to reduce clutter in Data.Map

3 years agoUse bang patterns to reduce clutter in Data.Map
David Feuer [Mon, 25 Apr 2016 19:22:23 +0000 (15:22 -0400)] 
Use bang patterns to reduce clutter in Data.Map

3 years agoAdd missing changelog info
David Feuer [Mon, 25 Apr 2016 12:26:25 +0000 (08:26 -0400)] 
Add missing changelog info

3 years agoFix silly changelog mistake
David Feuer [Mon, 25 Apr 2016 12:22:37 +0000 (08:22 -0400)] 
Fix silly changelog mistake

3 years agoMerge pull request #202 from treeowl/bang-sequences
David Feuer [Mon, 25 Apr 2016 04:31:16 +0000 (00:31 -0400)] 
Merge pull request #202 from treeowl/bang-sequences

Use bang patterns for Data.Sequence; avoid boxing

3 years agoAdd benchmarks
David Feuer [Mon, 25 Apr 2016 04:11:42 +0000 (00:11 -0400)] 
Add benchmarks

Add replicateA, traverse, and traverseWithIndex benchmarks.

3 years agoUse bang patterns for Data.Sequence; unbox
David Feuer [Sun, 24 Apr 2016 23:43:50 +0000 (19:43 -0400)] 
Use bang patterns for Data.Sequence; unbox

Use `BangPatterns` to reduce clutter in `Data.Sequence`.

When partially applying a `Deep`, `Node2`, or `Node3`
constructor in `traverse`, `traverseWithIndex`, and
`applicativeTree`, avoid boxing up the size argument.

3 years agoMerge pull request #121 from treeowl/intersperse
David Feuer [Fri, 22 Apr 2016 07:07:40 +0000 (03:07 -0400)] 
Merge pull request #121 from treeowl/intersperse

Add intersperse for sequences

3 years agoAdd intersperse for Seq
David Feuer [Sun, 28 Dec 2014 02:09:28 +0000 (21:09 -0500)] 
Add intersperse for Seq

`intersperse` is just like the one in `Data.List`. It is
implemented using `<**>` for optimal performance.

3 years agoMerge pull request #197 from haskell/revert-184-generic
David Feuer [Fri, 22 Apr 2016 06:02:24 +0000 (02:02 -0400)] 
Merge pull request #197 from haskell/revert-184-generic

Revert "add Generics instance for Map, Set, IntMap, and IntSet"

3 years agoMerge pull request #200 from treeowl/generic-tree
David Feuer [Fri, 22 Apr 2016 06:01:44 +0000 (02:01 -0400)] 
Merge pull request #200 from treeowl/generic-tree

Derive Generic and Generic1 for Data.Tree

3 years agoDerive Generic and Generic1 for Data.Tree
David Feuer [Fri, 22 Apr 2016 02:27:33 +0000 (22:27 -0400)] 
Derive Generic and Generic1 for Data.Tree

Unlike the other container types, `Data.Tree.Tree` is fully
exposed. Therefore, we can and should derive `Generic` and
`Generic1` instances for it.

3 years agoRevert "add Generics instance for Map, Set, IntMap, and IntSet" revert-184-generic
David Feuer [Thu, 21 Apr 2016 18:42:42 +0000 (14:42 -0400)] 
Revert "add Generics instance for Map, Set, IntMap, and IntSet"

3 years agoMerge pull request #196 from treeowl/changelog-patterns
David Feuer [Thu, 21 Apr 2016 17:42:09 +0000 (13:42 -0400)] 
Merge pull request #196 from treeowl/changelog-patterns

Add changelog entry for sequence pattern synonyms

3 years agoAdd changelog entry for sequence pattern synonyms
David Feuer [Thu, 21 Apr 2016 17:37:35 +0000 (13:37 -0400)] 
Add changelog entry for sequence pattern synonyms