packages/containers.git
3 years agoMerge pull request #305 from treeowl/restriction
David Feuer [Tue, 26 Jul 2016 05:36:09 +0000 (01:36 -0400)] 
Merge pull request #305 from treeowl/restriction

Add restrictKeys and withoutKeys

3 years agoAdd restrictKeys and withoutKeys
David Feuer [Tue, 26 Jul 2016 04:05:06 +0000 (00:05 -0400)] 
Add restrictKeys and withoutKeys

* Add `restrictKeys` and `withoutKeys` to `Data.Map` and
`Data.IntMap`.

* Add tests for the defining properties of these operations.

3 years agoMerge pull request #303 from treeowl/fix-replace
David Feuer [Mon, 25 Jul 2016 16:06:00 +0000 (12:06 -0400)] 
Merge pull request #303 from treeowl/fix-replace

Actually define the (<$) method

3 years agoActually define the (<$) method
David Feuer [Mon, 25 Jul 2016 16:01:26 +0000 (12:01 -0400)] 
Actually define the (<$) method

Accidentally defined a separate `(<$)` function for `Data.Map`.

Also, fix unused binding warnings.

3 years agoMerge pull request #302 from treeowl/intmap-inline-map
David Feuer [Mon, 25 Jul 2016 15:49:37 +0000 (11:49 -0400)] 
Merge pull request #302 from treeowl/intmap-inline-map

Rewrite IntMap map so it can inline; define <$

3 years agoRewrite IntMap map so it can inline; define <$
David Feuer [Mon, 25 Jul 2016 15:34:38 +0000 (11:34 -0400)] 
Rewrite IntMap map so it can inline; define <$

Previously, mapping a constant function would fill an `IntMap`
with thunks.

3 years agoMerge pull request #301 from treeowl/map-inline-map
David Feuer [Mon, 25 Jul 2016 15:22:15 +0000 (11:22 -0400)] 
Merge pull request #301 from treeowl/map-inline-map

Inline Map.map; define Map <$

3 years agoInline Map.map; define Map <$
David Feuer [Mon, 25 Jul 2016 14:45:18 +0000 (10:45 -0400)] 
Inline Map.map; define Map <$

Previously, `<$` would fill a map with thunks. Rewriting
`map` so it can inline fixes this. Defined a custom `<$` anyway.

Fixes #300

3 years agoMerge pull request #298 from treeowl/narrow-pattern-synonyms
David Feuer [Thu, 14 Jul 2016 02:47:36 +0000 (22:47 -0400)] 
Merge pull request #298 from treeowl/narrow-pattern-synonyms

Define pattern synonyms only for GHC >=8

3 years agoDefine pattern synonyms only for GHC >=8
David Feuer [Thu, 14 Jul 2016 02:24:05 +0000 (22:24 -0400)] 
Define pattern synonyms only for GHC >=8

The CPP required to support pattern synonyms with earlier GHC
versions produces too much clutter. It's bad enough having to
deal with exports with and without testing and with and without
pattern synonyms. Having two different export mechanisms goes too
far. If users demand support very strenuously, we can put some of
it back. Until then, I don't want to commit to supporting it
indefinitely.

Fixes #297

3 years agoMerge pull request #296 from treeowl/fromDescList
David Feuer [Fri, 8 Jul 2016 18:42:07 +0000 (14:42 -0400)] 
Merge pull request #296 from treeowl/fromDescList

Add fromDescList and fromDistinctDescList

3 years agoAdd fromDescList and fromDistinctDescList
David Feuer [Fri, 8 Jul 2016 18:08:49 +0000 (14:08 -0400)] 
Add fromDescList and fromDistinctDescList

The set versions are just like the map versions, pretty much.

3 years agoMerge pull request #295 from treeowl/map-fromDescending
David Feuer [Thu, 7 Jul 2016 20:50:20 +0000 (16:50 -0400)] 
Merge pull request #295 from treeowl/map-fromDescending

Add fromDesc functions for Data.Map

3 years agoAdd fromDesc functions for Data.Map
David Feuer [Thu, 7 Jul 2016 19:46:13 +0000 (15:46 -0400)] 
Add fromDesc functions for Data.Map

Add functions to convert descending lists to maps.

3 years agoMerge pull request #294 from treeowl/sequence-adjust
David Feuer [Thu, 7 Jul 2016 17:49:26 +0000 (13:49 -0400)] 
Merge pull request #294 from treeowl/sequence-adjust

Add Data.Sequence.adjust'

3 years agoAdd Data.Sequence.adjust'
David Feuer [Thu, 7 Jul 2016 17:09:03 +0000 (13:09 -0400)] 
Add Data.Sequence.adjust'

* Add `adjust'`, which forces the new value before installing it
in the sequence.

* Improve the documentation for `lookup`.

* Cut out some unnecessary code from `traverse`.

3 years agoMerge pull request #292 from treeowl/spitzner-nines
David Feuer [Wed, 29 Jun 2016 03:40:12 +0000 (23:40 -0400)] 
Merge pull request #292 from treeowl/spitzner-nines

Use Lennart Spitzner's implementation of `fromList`.

3 years agoClean up fromList
David Feuer [Wed, 15 Jun 2016 21:55:41 +0000 (17:55 -0400)] 
Clean up fromList

Remove unnecessary `s` parameter for tree top.

Remove unnecessary `let`s, and generally make things neater.

Make trees lean left.

Use local type signatures under GHC, where scoped
type variables are available.

Remove unnecessary bang patterns.

Begin to document design.

3 years agoData.Sequence.fromList: Apply 3->9 loop unrolling
Lennart Spitzner [Mon, 13 Jun 2016 17:17:03 +0000 (19:17 +0200)] 
Data.Sequence.fromList: Apply 3->9 loop unrolling

3 years agoData.Sequence.fromList: Reimplement using FinalList
Lennart Spitzner [Mon, 13 Jun 2016 14:40:16 +0000 (16:40 +0200)] 
Data.Sequence.fromList: Reimplement using FinalList

3 years agoAdd longer fromList benchmark
David Feuer [Tue, 14 Jun 2016 22:33:14 +0000 (18:33 -0400)] 
Add longer fromList benchmark

The previous benchmarks weren't big enough to reveal certain
cache effects.

3 years agoMerge pull request #287 from treeowl/clean-typeable
David Feuer [Sat, 11 Jun 2016 04:54:41 +0000 (00:54 -0400)] 
Merge pull request #287 from treeowl/clean-typeable

Clean up Typeable; derive more Generic

3 years agoClean up Typeable; derive more Generic
David Feuer [Sat, 11 Jun 2016 04:02:58 +0000 (00:02 -0400)] 
Clean up Typeable; derive more Generic

* Remove gunk apparently intended to support `Typeable` for
Hugs.

* Derive `Generic` and `Generic1` for `Data.Sequence.ViewL`
and `Data.Sequence.ViewR`.

3 years agoUpdate and organize changelog
David Feuer [Sat, 11 Jun 2016 03:52:59 +0000 (23:52 -0400)] 
Update and organize changelog

3 years agoMerge pull request #286 from treeowl/strictify-seq-fromList
David Feuer [Sat, 11 Jun 2016 03:37:21 +0000 (23:37 -0400)] 
Merge pull request #286 from treeowl/strictify-seq-fromList

Make Data.Sequence.fromList more eager

3 years agoMake Data.Sequence.fromList more eager
David Feuer [Sat, 11 Jun 2016 01:41:39 +0000 (21:41 -0400)] 
Make Data.Sequence.fromList more eager

`fromList` previously suspended most of its work,
storing the structure in thunks rather than trees.
Now it builds everything.

Old:

benchmarking fromList/10
time                 175.2 ns   (174.7 ns .. 175.7 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 175.2 ns   (174.8 ns .. 175.6 ns)
std dev              1.383 ns   (1.124 ns .. 1.775 ns)

benchmarking fromList/100
time                 2.712 μs   (2.707 μs .. 2.720 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 2.732 μs   (2.717 μs .. 2.779 μs)
std dev              76.64 ns   (40.38 ns .. 147.1 ns)
variance introduced by outliers: 35% (moderately inflated)

benchmarking fromList/1000
time                 32.24 μs   (32.18 μs .. 32.33 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 32.26 μs   (32.22 μs .. 32.35 μs)
std dev              194.7 ns   (100.0 ns .. 371.4 ns)

benchmarking fromList/10000
time                 510.3 μs   (508.2 μs .. 511.9 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 508.1 μs   (506.2 μs .. 509.8 μs)
std dev              5.787 μs   (4.788 μs .. 7.175 μs)

New:

benchmarking fromList/10
time                 139.8 ns   (139.5 ns .. 140.2 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 139.8 ns   (139.6 ns .. 140.3 ns)
std dev              1.023 ns   (547.5 ps .. 1.573 ns)

benchmarking fromList/100
time                 1.520 μs   (1.517 μs .. 1.525 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 1.522 μs   (1.518 μs .. 1.529 μs)
std dev              16.53 ns   (10.57 ns .. 24.26 ns)

benchmarking fromList/1000
time                 16.00 μs   (15.97 μs .. 16.05 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 15.99 μs   (15.97 μs .. 16.04 μs)
std dev              89.39 ns   (39.63 ns .. 151.2 ns)

benchmarking fromList/10000
time                 262.8 μs   (262.3 μs .. 263.5 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 262.8 μs   (262.4 μs .. 264.7 μs)
std dev              2.559 μs   (757.4 ns .. 5.482 μs)

3 years agoMerge pull request #283 from recursion-ninja/master
David Feuer [Sat, 11 Jun 2016 01:30:47 +0000 (21:30 -0400)] 
Merge pull request #283 from recursion-ninja/master

Corrected drawTree & drawForest to render multiline String values in a palatable manner.

3 years agoMerge pull request #285 from treeowl/strictify-more-sequence
David Feuer [Sat, 11 Jun 2016 01:22:36 +0000 (21:22 -0400)] 
Merge pull request #285 from treeowl/strictify-more-sequence

Be more eager about building by consing

3 years agoBe more eager about building by consing
David Feuer [Fri, 10 Jun 2016 19:17:46 +0000 (15:17 -0400)] 
Be more eager about building by consing

Also make `partition` build things much more eagerly.

3 years agoMerge pull request #284 from treeowl/seq-traverse-map-less
David Feuer [Fri, 10 Jun 2016 05:05:50 +0000 (01:05 -0400)] 
Merge pull request #284 from treeowl/seq-traverse-map-less

Make traverse fmap less

3 years agoMake traverse fmap less
David Feuer [Fri, 10 Jun 2016 04:42:11 +0000 (00:42 -0400)] 
Make traverse fmap less

Use safe coercions to avoid `fmap` at the leaves to deal with
`Elem` and at the root to deal with `Seq`. This should speed
things up for non-trivial functors.

3 years agoCorrected drawTree to render multi-line String values in a palatable manner.
recursion-ninja [Thu, 9 Jun 2016 23:39:19 +0000 (19:39 -0400)] 
Corrected drawTree to render multi-line String values in a palatable manner.

3 years agoUpdate .travis.yml with new GHC versions (#282)
Ossi Herrala [Sat, 4 Jun 2016 21:41:40 +0000 (00:41 +0300)] 
Update .travis.yml with new GHC versions (#282)

Add GHC 8.0.1 and replace 7.10.1 with 7.10.3.

Fixes #269

3 years agoWrite custom strict folds (#281)
David Feuer [Thu, 2 Jun 2016 02:20:50 +0000 (22:20 -0400)] 
Write custom strict folds (#281)

Writing `foldl'` and `foldr'` by hand, instead of using the
default definitions, makes them about twice as fast.

Fix completely bogus definition of `length` for `ViewR`.

3 years agoUse ScopedTypeVariables to optimize zipping (#280)
David Feuer [Wed, 1 Jun 2016 23:37:28 +0000 (19:37 -0400)] 
Use ScopedTypeVariables to optimize zipping (#280)

`splitMap` was annoyingly sensitive to any minor change anywhere,
presumably because it was tough on the inliner. Using
`ScopedTypeVariables` when compiling with GHC, we can pull the
splitting function out of the polymorphic recursion. Suddenly
GHC starts unboxing `Int`s and generally acting like a happier
compiler. I'm hopeful that `ScopedTypeVariables` will be in the
next standard so we can eventually drop the other code.

Also, modify the `Split` type to make it more obvious that we
only force things we're allowed to.

Also also, make `chunksOf` a bit more tolerant. Now it only
complains if it's asked to produce non-positive-sized chunks
of a non-empty sequence.

3 years agoMake >< build its result eagerly (#277)
David Feuer [Tue, 31 May 2016 17:55:37 +0000 (13:55 -0400)] 
Make >< build its result eagerly (#277)

Previously, `><` only built the top of the tree,
leaving the rest suspended lazily. Now it rebuilds
eagerly, using the full time allocated to it. The
improvements on the `splitAt/append` benchmark are
modest but meaningful. More importantly, it should no
longer be possible to use `><` to produce large chains
of thunks.

Fixes #274

Old: 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)

New: benchmarking splitAt/append/10
time                 987.8 μs   (982.7 μs .. 992.3 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 995.5 μs   (994.6 μs .. 997.2 μs)
std dev              3.845 μs   (1.988 μs .. 6.390 μs)

Old: 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)

New: benchmarking splitAt/append/100
time                 7.382 ms   (7.346 ms .. 7.427 ms)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 7.374 ms   (7.357 ms .. 7.430 ms)
std dev              75.55 μs   (41.64 μs .. 135.4 μs)

Old: 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)

New: benchmarking splitAt/append/1000
time                 13.68 ms   (13.61 ms .. 13.77 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 13.64 ms   (13.59 ms .. 13.69 ms)
std dev              118.9 μs   (89.45 μs .. 154.4 μs)

3 years agoMake `intersperse` work right up to the edge (#276)
David Feuer [Tue, 31 May 2016 17:29:20 +0000 (13:29 -0400)] 
Make `intersperse` work right up to the edge (#276)

Previously, `intersperse` would fail if passed a sequence of
length

```haskell
((maxBound :: Int) `quot` 2) + 1
```

Now it should be able to produce results of lengths right up to
`maxBound :: Int`.

3 years agoMerge pull request #273 from treeowl/eager-adjust
David Feuer [Tue, 31 May 2016 15:35:19 +0000 (11:35 -0400)] 
Merge pull request #273 from treeowl/eager-adjust

Sequences: strictify adjust; reimplement update

3 years agoSequences: strictify adjust; reimplement update
David Feuer [Tue, 31 May 2016 13:55:52 +0000 (09:55 -0400)] 
Sequences: strictify adjust; reimplement update

Previously, `adjust` would place a thunk at the top of the tree.
Now, it pushes that thunk all the way down to the appropriate
leaf. This way, performing multiple adjustments to different
locations will not lead to a thunk clog at the top.

Adjusting the *same* location many times, however, can lead to
a thunk clog at the leaf. This is generally unavoidable. `update`
used to be implemented as

```haskell
update i x = adjust (const x) i
```

which is subject to the thunk clog problem. By implementing the
`Elem` layer of `update` directly (duplicating code), we can
avoid subjecting `update` to this problem at all.

Also, bring all the insertion code together. It got separated
by mistake.

Actually export `alterF` from `Data.IntMap.Strict`.

3 years agoMerge pull request #272 from treeowl/seq-delete-cleanup
David Feuer [Tue, 31 May 2016 05:20:13 +0000 (01:20 -0400)] 
Merge pull request #272 from treeowl/seq-delete-cleanup

Some cleanup of deleteAt

3 years agoSome cleanup of deleteAt
David Feuer [Tue, 31 May 2016 03:58:23 +0000 (23:58 -0400)] 
Some cleanup of deleteAt

Use arithmetic to avoid inspecting nodes and build some things more
eagerly.

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