Add Bifoldable and Bitraversable to base

This adds `Data.Bifoldable` and `Data.Bitraversable` from the
`bifunctors` package to `base`, completing the migration started in
D336.  This is fairly straightforward, although there were a suprising
amount of reinternal organization in `base` that was needed for this to
happen:

* `Data.Foldable`, `Data.Traversable`, `Data.Bifoldable`, and
  `Data.Bitraversable` share some nonexported datatypes (e.g., `StateL`,
  `StateR`, `Min`, `Max`, etc.) to implement some instances. To avoid
  code duplication, I migrated this internal code to a new hidden
  module, `Data.Functor.Utils` (better naming suggestions welcome).

* `Data.Traversable` and `Data.Bitraversable` also make use of an
  identity newtype, so I modified them to use
  `Data.Functor.Identity.Identity`. This has a ripple effect on several
  other modules, since I had to move instances around in order to avoid
  dependency cycles.

Fixes #10448.

Reviewers: ekmett, hvr, austin, bgamari

Reviewed By: bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D2284

GHC Trac Issues: #9682, #10448

3 files changed, 8 insertions, 7 deletions

diff --git a/testsuite/tests/annotations/should_fail/annfail10.stderr b/testsuite/tests/annotations/should_fail/annfail10.stderr
index b5f5a16fdf..6782f27228 100644
--- a/testsuite/tests/annotations/should_fail/annfail10.stderr
+++ b/testsuite/tests/annotations/should_fail/annfail10.stderr
@@ -10,7 +10,7 @@ annfail10.hs:9:1: error:
         instance Data.Data.Data Ordering -- Defined in ‘Data.Data’
         instance Data.Data.Data Integer -- Defined in ‘Data.Data’
         ...plus 15 others
-        ...plus 38 instances involving out-of-scope types
+        ...plus 39 instances involving out-of-scope types
         (use -fprint-potential-instances to see them all)
     • In the annotation: {-# ANN f 1 #-}
 
@@ -23,6 +23,6 @@ annfail10.hs:9:11: error:
         instance Num Double -- Defined in ‘GHC.Float’
         instance Num Float -- Defined in ‘GHC.Float’
         ...plus two others
-        ...plus 12 instances involving out-of-scope types
+        ...plus 13 instances involving out-of-scope types
         (use -fprint-potential-instances to see them all)
     • In the annotation: {-# ANN f 1 #-}
diff --git a/testsuite/tests/perf/compiler/all.T b/testsuite/tests/perf/compiler/all.T
index 7435a3330f..a09499915a 100644
--- a/testsuite/tests/perf/compiler/all.T
+++ b/testsuite/tests/perf/compiler/all.T
@@ -776,9 +776,10 @@ test('T9961',
 test('T9233',
     [ only_ways(['normal']),
       compiler_stats_num_field('bytes allocated',
-        [(wordsize(64), 1066246248, 5),
+        [(wordsize(64), 984268712, 5),
          # 2015-08-04    999826288     initial value
          # 2016-04-14   1066246248     Final demand analyzer run
+         # 2016-06-18    984268712     shuffling around of Data.Functor.Identity
          (wordsize(32),  515672240, 5)   # Put in your value here if you hit this
          # 2016-04-06    515672240     (x86/Linux) initial value
         ]),
diff --git a/testsuite/tests/typecheck/should_fail/T10971b.stderr b/testsuite/tests/typecheck/should_fail/T10971b.stderr
index d072c2552b..2e63617464 100644
--- a/testsuite/tests/typecheck/should_fail/T10971b.stderr
+++ b/testsuite/tests/typecheck/should_fail/T10971b.stderr
@@ -11,7 +11,7 @@ T10971b.hs:4:11: error:
         instance Foldable Maybe -- Defined in ‘Data.Foldable’
         instance Foldable ((,) a) -- Defined in ‘Data.Foldable’
         ...plus one other
-        ...plus 24 instances involving out-of-scope types
+        ...plus 25 instances involving out-of-scope types
         (use -fprint-potential-instances to see them all)
     • In the expression: length x
       In the expression: \ x -> length x
@@ -29,7 +29,7 @@ T10971b.hs:5:13: error:
         instance Traversable Maybe -- Defined in ‘Data.Traversable’
         instance Traversable ((,) a) -- Defined in ‘Data.Traversable’
         ...plus one other
-        ...plus 24 instances involving out-of-scope types
+        ...plus 25 instances involving out-of-scope types
         (use -fprint-potential-instances to see them all)
     • In the expression: fmapDefault f x
       In the expression: \ f x -> fmapDefault f x
@@ -47,7 +47,7 @@ T10971b.hs:6:14: error:
         instance Traversable Maybe -- Defined in ‘Data.Traversable’
         instance Traversable ((,) a) -- Defined in ‘Data.Traversable’
         ...plus one other
-        ...plus 24 instances involving out-of-scope types
+        ...plus 25 instances involving out-of-scope types
         (use -fprint-potential-instances to see them all)
     • In the expression: fmapDefault f x
       In the expression: (fmapDefault f x, length x)
@@ -65,7 +65,7 @@ T10971b.hs:6:31: error:
         instance Foldable Maybe -- Defined in ‘Data.Foldable’
         instance Foldable ((,) a) -- Defined in ‘Data.Foldable’
         ...plus one other
-        ...plus 24 instances involving out-of-scope types
+        ...plus 25 instances involving out-of-scope types
         (use -fprint-potential-instances to see them all)
     • In the expression: length x
       In the expression: (fmapDefault f x, length x)