packages/containers.git
3 years agoRefactor internal modules (#324)
Ertugrul Söylemez [Wed, 31 Aug 2016 14:50:01 +0000 (16:50 +0200)] 
Refactor internal modules (#324)

* Ignore more dev files.

* Rename .Base modules to .Internal.

  * Data.IntMap.Base -> Data.IntMap.Internal
  * Data.IntSet.Base -> Data.IntSet.Internal
  * Data.Map.Base -> Data.Map.Internal
  * Data.Sequence.Base -> Data.Sequence.Internal
  * Data.Set.Base -> Data.Set.Internal

* Unhide internal modules, add missing warning.

* Unexpose utility modules except for .Utils.BitUtil and .Utils.BitQueue.

3 years agoUpdate changelog.md
David Feuer [Wed, 31 Aug 2016 06:49:34 +0000 (02:49 -0400)] 
Update changelog.md

3 years agoBump version in containers.cabal
David Feuer [Wed, 31 Aug 2016 05:27:56 +0000 (01:27 -0400)] 
Bump version in containers.cabal

3 years agoFix documentation formatting
David Feuer [Wed, 31 Aug 2016 04:58:58 +0000 (00:58 -0400)] 
Fix documentation formatting

3 years agoMerge pull request #323 from treeowl/deprecate-ancient
David Feuer [Wed, 31 Aug 2016 03:55:26 +0000 (23:55 -0400)] 
Merge pull request #323 from treeowl/deprecate-ancient

Deprecate some functions in Data.Map

3 years agoDeprecate some functions in Data.Map
David Feuer [Wed, 31 Aug 2016 03:13:18 +0000 (23:13 -0400)] 
Deprecate some functions in Data.Map

* `Data.Map` has had several functions documented as deprecated,
but without actual `DEPRECATED` pragmas, for years. Add the
pragmas so we can move toward removal in a couple more major
versions.

* The `showTree` and `showTreeWith` functions don't seem like a
good fit for the public API. I'm deprecating them, but they will
remain available for the foreseeable future in `Data.Map.Base`
or some other internal module.

3 years agoMerge pull request #322 from treeowl/set-extras
David Feuer [Wed, 31 Aug 2016 03:13:09 +0000 (23:13 -0400)] 
Merge pull request #322 from treeowl/set-extras

Add new index-based and unsafe Set functions

3 years agoAdd new index-based and unsafe Set functions
David Feuer [Wed, 31 Aug 2016 02:48:12 +0000 (22:48 -0400)] 
Add new index-based and unsafe Set functions

These match the ones just added for maps.

3 years agoUpdate changelog.md
David Feuer [Wed, 31 Aug 2016 02:25:00 +0000 (22:25 -0400)] 
Update changelog.md

3 years agoMerge pull request #321 from treeowl/more-monotonic
David Feuer [Wed, 31 Aug 2016 02:02:08 +0000 (22:02 -0400)] 
Merge pull request #321 from treeowl/more-monotonic

Add more indexed and unsafe functions for Data.Map

3 years agoAdd more indexed and unsafe functions for Data.Map
David Feuer [Thu, 25 Aug 2016 21:44:51 +0000 (17:44 -0400)] 
Add more indexed and unsafe functions for Data.Map

* Offer `take`, `drop`, and `splitAt` by index.

* Offer 'takeWhileAntitone`, `dropWhileAntitone`, and `spanAntitone`.

3 years agoMerge pull request #319 from treeowl/generalMerge2
David Feuer [Thu, 25 Aug 2016 20:13:02 +0000 (16:13 -0400)] 
Merge pull request #319 from treeowl/generalMerge2

Add general merge functions for maps

3 years agoAdd general merge functions for maps
David Feuer [Mon, 8 Aug 2016 15:52:23 +0000 (11:52 -0400)] 
Add general merge functions for maps

* Add `merge` and `mergeA` for `Data.Map`,
  in the new modules `Data.Map.Lazy.Merge` and
  `Data.Map.Strict.Merge`.

* Expose internal modules per Ed Kmett's request

* Make `difference` for maps and sets conform more closely
  to the algorithm in Blelloch et al so we can rely on their proof.

3 years agoMerge pull request #318 from treeowl/kill-warnings
David Feuer [Wed, 10 Aug 2016 21:35:35 +0000 (17:35 -0400)] 
Merge pull request #318 from treeowl/kill-warnings

Kill a bunch of silly warnings.

3 years agoKill a bunch of silly warnings.
David Feuer [Wed, 10 Aug 2016 20:39:04 +0000 (16:39 -0400)] 
Kill a bunch of silly warnings.

Just name shadowing and unused binding nonsense.

3 years agoMerge pull request #315 from treeowl/map-combination-update
David Feuer [Sat, 6 Aug 2016 19:38:08 +0000 (15:38 -0400)] 
Merge pull request #315 from treeowl/map-combination-update

Continue to improve map functions

3 years agoBunch of changes
David Feuer [Sat, 6 Aug 2016 18:20:25 +0000 (14:20 -0400)] 
Bunch of changes

* Continue set and map combination rewrites.

* Add bias tests to `Data.Set` suite.

* Replace `Arbitrary` instance for sets.

* Use specialized function to produce pairs of sets
  for combination tests.

This is a horribly large and incomplete commit,
but it all works and I need to move on to some other things.
Sorry, world.

3 years agoContinue to improve map functions
David Feuer [Mon, 1 Aug 2016 21:40:14 +0000 (17:40 -0400)] 
Continue to improve map functions

Rewrite `unionWith`, `intersectionWithKey`, etc., as independent
functions. Writing either in terms of the other leads to closures
being allocated with extra indirection for the passed function.
`mergeWithKey` misses singleton optimizations for unions. For the
rest, I think `mergeWithKey` is hard to understand, and it's not
immediately obvious how the parts are supposed to fit together.
Since it's used only to reduce *source* code size, and not actual
*generated* code size, I'd rather avoid it for the most part.
I've left `differenceWith` and `differenceWithKey` alone, as they
appear to be rather deeply tied to the concepts in `mergeWithKey`.

3 years agoMerge pull request #312 from treeowl/isTrue
David Feuer [Mon, 1 Aug 2016 18:29:31 +0000 (14:29 -0400)] 
Merge pull request #312 from treeowl/isTrue

Use isTrue# for pointer equality

3 years agoUse isTrue# for pointer equality
David Feuer [Mon, 1 Aug 2016 17:56:31 +0000 (13:56 -0400)] 
Use isTrue# for pointer equality

Edward Kmett says it's better to do that and take the load off
core-to-core. Currently, that gets shifted to codegen, I think.

3 years agoMerge pull request #311 from treeowl/set-ptr-equality
David Feuer [Mon, 1 Aug 2016 17:32:58 +0000 (13:32 -0400)] 
Merge pull request #311 from treeowl/set-ptr-equality

Use pointer equality to enhance sharing for Sets

3 years agoUse pointer equality to enhance sharing for Sets
David Feuer [Mon, 1 Aug 2016 17:10:00 +0000 (13:10 -0400)] 
Use pointer equality to enhance sharing for Sets

Use pointer equality to avoid allocating new copies of existing
structures. This helps a number of benchmarks a *lot*. Unfortunately,
it hurts some others a little.

3 years agoMerge pull request #310 from treeowl/set-div-conq
David Feuer [Mon, 1 Aug 2016 06:41:32 +0000 (02:41 -0400)] 
Merge pull request #310 from treeowl/set-div-conq

Stop using hedge algorithms

3 years agoStop using hedge algorithms
David Feuer [Fri, 29 Jul 2016 01:52:08 +0000 (21:52 -0400)] 
Stop using hedge algorithms

Replace hedge algorithms with divide and conquer algorithms for unions,
intersections, differences, and merges in `Data.Set` and `Data.Map`. The
divide and conquer algorithms

* are much simpler,

* have recently been proven asymptotically optimal, and

* are faster on most benchmarks, sometimes much faster, and never
  much slower.

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.