packages/containers.git
2 years agoUpdate changelog
David Feuer [Thu, 15 Dec 2016 04:52:10 +0000 (23:52 -0500)] 
Update changelog

2 years agoMerge pull request #367 from treeowl/lift-map
David Feuer [Thu, 15 Dec 2016 03:23:45 +0000 (22:23 -0500)] 
Merge pull request #367 from treeowl/lift-map

Add lifted instances for Data.Map

2 years agoAdd lifted instances for Data.Map
Oleg Grenrus [Thu, 15 Dec 2016 02:51:28 +0000 (21:51 -0500)] 
Add lifted instances for Data.Map

2 years agoMerge pull request #366 from treeowl/lift-tree
David Feuer [Thu, 15 Dec 2016 02:05:38 +0000 (21:05 -0500)] 
Merge pull request #366 from treeowl/lift-tree

Add lifted instances for Data.Tree

2 years agoAdd lifted instances for Data.Tree
David Feuer [Thu, 15 Dec 2016 01:52:08 +0000 (20:52 -0500)] 
Add lifted instances for Data.Tree

Add `Eq1`, `Show1`, `Eq1`, and `Ord1` instances for `Data.Tree`.

2 years agoMerge pull request #365 from treeowl/lift-set
David Feuer [Wed, 14 Dec 2016 18:30:02 +0000 (13:30 -0500)] 
Merge pull request #365 from treeowl/lift-set

Add instances for Data.Set

2 years agoAdd instances for Data.Set
Oleg Grenrus [Wed, 14 Dec 2016 01:43:15 +0000 (20:43 -0500)] 
Add instances for Data.Set

Add `Eq1`, `Ord1`, and `Show1` instances for `Data.Set`.

2 years agoMerge pull request #364 from treeowl/lift-sequence
David Feuer [Wed, 14 Dec 2016 01:03:02 +0000 (20:03 -0500)] 
Merge pull request #364 from treeowl/lift-sequence

Add lifted instances for Data.Sequence

2 years agoAdd lifted instances for Data.Sequence
David Feuer [Tue, 13 Dec 2016 17:50:57 +0000 (12:50 -0500)] 
Add lifted instances for Data.Sequence

Add instances of `Eq1`, `Ord1`, `Show1`, and `Read1` for
`Data.Sequence`.

2 years agoMerge pull request #362 from wrengr/IntMapGeneralMerge
wren romano [Sun, 11 Dec 2016 22:21:34 +0000 (14:21 -0800)] 
Merge pull request #362 from wrengr/IntMapGeneralMerge

Int map general merge

2 years agoMerge branch 'master' into IntMapGeneralMerge
wren romano [Sun, 11 Dec 2016 22:19:44 +0000 (14:19 -0800)] 
Merge branch 'master' into IntMapGeneralMerge

2 years agoData.IntMap.Internal: actually exporting mergeA etc
wren romano [Sun, 11 Dec 2016 22:17:55 +0000 (14:17 -0800)] 
Data.IntMap.Internal: actually exporting mergeA etc

2 years agoMerge pull request #358 from wrengr/IntMapGeneralMerge
wren romano [Sun, 11 Dec 2016 22:02:45 +0000 (14:02 -0800)] 
Merge pull request #358 from wrengr/IntMapGeneralMerge

IntMap general merge

2 years agoIntMap: added deprecation for debugging functions
wren romano [Sun, 27 Nov 2016 04:14:48 +0000 (20:14 -0800)] 
IntMap: added deprecation for debugging functions

2 years agoIntMap: adding intermediate data structures to strictify recursion
wren romano [Sun, 27 Nov 2016 04:11:59 +0000 (20:11 -0800)] 
IntMap: adding intermediate data structures to strictify recursion

2 years agoData.IntMap.Internal: fixed the Tip vs Bin case of MergeA
wren romano [Tue, 8 Nov 2016 02:15:38 +0000 (18:15 -0800)] 
Data.IntMap.Internal: fixed the Tip vs Bin case of MergeA

2 years agoData.IntMap.Internal: corrected order of effects in mergeA
wren romano [Mon, 7 Nov 2016 07:36:17 +0000 (23:36 -0800)] 
Data.IntMap.Internal: corrected order of effects in mergeA

That is, corrected the order for the Tip vs Bin cases. Still haven't
tested everything all together.

2 years agoData.IntMap.Internal: preliminary version of mergeA
wren romano [Mon, 7 Nov 2016 07:17:09 +0000 (23:17 -0800)] 
Data.IntMap.Internal: preliminary version of mergeA

This version fills in all the todos, and the code matches the pure
version fairly well, but (a) the outputs have not been debugged,
and (b) the order of effects is known to be wrong.

2 years agoMerge branch 'refs/heads/master' into IntMapGeneralMerge
wren romano [Mon, 7 Nov 2016 01:15:00 +0000 (17:15 -0800)] 
Merge branch 'refs/heads/master' into IntMapGeneralMerge

2 years agoData.IntMap.Internal: rebasing and minor adjustments
wren gayle romano [Mon, 5 Sep 2016 23:39:28 +0000 (16:39 -0700)] 
Data.IntMap.Internal: rebasing and minor adjustments

2 years agoMerge pull request #352 from erikd/master
David Feuer [Sun, 30 Oct 2016 12:16:40 +0000 (08:16 -0400)] 
Merge pull request #352 from erikd/master

Data.Sequence.Internal: Fix CPP usage

2 years agoData.Sequence.Internal: Fix CPP usage
Erik de Castro Lopo [Sun, 23 Oct 2016 01:15:42 +0000 (12:15 +1100)] 
Data.Sequence.Internal: Fix CPP usage

There was a mixture of `#ifdef TESTING` and `#if TESTING`. The later
works, but is not really correct. GHC HEAD now has a `-Wcpp-undef`
warning that we would like to turn on and hence need this fixed.

3 years agoMerge pull request #337 from treeowl/map-min-max
David Feuer [Wed, 7 Sep 2016 05:09:48 +0000 (01:09 -0400)] 
Merge pull request #337 from treeowl/map-min-max

Quit using deleteFindMin and deleteFindMax

3 years agoQuit using deleteFindMin and deleteFindMax
David Feuer [Tue, 6 Sep 2016 23:37:34 +0000 (19:37 -0400)] 
Quit using deleteFindMin and deleteFindMax

Stop using `deleteFindMin` or `deleteFindMax` internally, in both
`Data.Set` and `Data.Map`.

* The `deleteFindMin` and `deleteFindMax` functions are partial,
and also rather ugly. Reimplement `minView`, `minViewWithKey`, `glue`,
etc., using total functions. With manual call-pattern specialization,
this produces pretty core, and slight performance improvements as well.
I'm not sure why GHC doesn't do that specialization for us, but I
couldn't seem to convince it to.

* Add `lookupMin` and `lookupMax`, total versions of `findMin`
and `findMax`, to both `Data.Set` and `Data.Map`. Add `!?`, a
total version of `!`, to `Data.Map`.

3 years agoData.IntMap.Internal: first pass of getting {merge,mergeA} to typecheck
wren gayle romano [Mon, 5 Sep 2016 23:39:28 +0000 (16:39 -0700)] 
Data.IntMap.Internal: first pass of getting {merge,mergeA} to typecheck

3 years agoData.Map.Internal: initial copy & paste of {merge,mergeA} stuff
wren gayle romano [Mon, 5 Sep 2016 23:14:09 +0000 (16:14 -0700)] 
Data.Map.Internal: initial copy & paste of {merge,mergeA} stuff

3 years agoData.Map.Internal.mergeA: corrected the floating out of g1
wren gayle romano [Mon, 5 Sep 2016 22:46:22 +0000 (15:46 -0700)] 
Data.Map.Internal.mergeA: corrected the floating out of g1

3 years agoData.Map.Internal.mergeA: floated out the missingSubtree progection of g1
wren gayle romano [Mon, 5 Sep 2016 21:55:35 +0000 (14:55 -0700)] 
Data.Map.Internal.mergeA: floated out the missingSubtree progection of g1

3 years agoData.IntMap.Internal: cleaning up whitespace
wren gayle romano [Mon, 5 Sep 2016 21:33:04 +0000 (14:33 -0700)] 
Data.IntMap.Internal: cleaning up whitespace

3 years agoMerge pull request #335 from treeowl/move-merge
David Feuer [Mon, 5 Sep 2016 19:04:26 +0000 (15:04 -0400)] 
Merge pull request #335 from treeowl/move-merge

Rename merge modules

3 years agoRename merge modules
David Feuer [Mon, 5 Sep 2016 18:43:29 +0000 (14:43 -0400)] 
Rename merge modules

I think it's more consistent with the rest of the API to name
them `Data.Map.Merge.Lazy` and `Data.Map.Merge.Strict`. This also
gives us the option to add further merge-related modules in the
`Merge` hierarchy. The original names still work for now, but they
are deprecated and hidden from Haddock.

3 years agoMerge pull request #334 from treeowl/expose-patsyms
David Feuer [Mon, 5 Sep 2016 18:02:04 +0000 (14:02 -0400)] 
Merge pull request #334 from treeowl/expose-patsyms

Actually expose Data.Sequence pattern synonyms

3 years agoActually expose Data.Sequence pattern synonyms
David Feuer [Mon, 5 Sep 2016 16:14:51 +0000 (12:14 -0400)] 
Actually expose Data.Sequence pattern synonyms

* Expose `Data.Sequence` pattern synonyms for real.

* Add tests for the pattern synonyms.

* Kill a couple silly warnings in `Data.Map.Internal`.

3 years agoUpdate changelog.md
David Feuer [Mon, 5 Sep 2016 15:44:31 +0000 (11:44 -0400)] 
Update changelog.md

3 years agoMerge pull request #332 from treeowl/fromAscListWithout
David Feuer [Mon, 5 Sep 2016 01:15:33 +0000 (21:15 -0400)] 
Merge pull request #332 from treeowl/fromAscListWithout

Implement fromAscList independently

3 years agoImplement fromAscList independently
David Feuer [Sun, 4 Sep 2016 08:38:11 +0000 (04:38 -0400)] 
Implement fromAscList independently

Implementing the lazy version of `fromAscList` in terms of
`fromAscListWithKey` leaks memory if there are many repeated
keys. Inlining `fromAscListWithKey` into `fromAscList` manually
should fix this. The same goes for `fromDescList`.

3 years agoMerge pull request #331 from treeowl/map-fromAscList-strictify
David Feuer [Sun, 4 Sep 2016 08:31:35 +0000 (04:31 -0400)] 
Merge pull request #331 from treeowl/map-fromAscList-strictify

Make Data.Map.fromDistinct{Asc,Desc}List eager

3 years agoMake Data.Map.fromDistinct{Asc,Desc}List eager
David Feuer [Sun, 4 Sep 2016 07:28:39 +0000 (03:28 -0400)] 
Make Data.Map.fromDistinct{Asc,Desc}List eager

* `Data.Map.fromDistinctAscList` and `fromDistinctDescList`
were accumulating thunks for no good reason. Make them
build their structures eagerly. This cuts time by a good
bit (a third, maybe).

* Make the same functions in `Data.Set` just a tad more eager
as well.

3 years agoMerge pull request #329 from treeowl/rename-internals
David Feuer [Fri, 2 Sep 2016 16:02:59 +0000 (12:02 -0400)] 
Merge pull request #329 from treeowl/rename-internals

General package stuff, mostly

3 years agoGeneral package stuff, mostly
David Feuer [Fri, 2 Sep 2016 03:59:12 +0000 (23:59 -0400)] 
General package stuff, mostly

* Rename the internals again. I think they're getting close to
reasonable now. Get the cabal benchmarks running again. Deprecate
the "deprecated" `IntMap` stuff. Make a `Debug` module for the
`Data.Map` debugging functions.

* Rewrite `Data.Map.Internal.Debug.validSize` to use the
  `Monad Maybe` instance for clarity.

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)