Create a deterministic version of tyVarsOfType

I've run into situations where I need deterministic `tyVarsOfType` and
this implementation achieves that and also brings an algorithmic
improvement.  Union of two `VarSet`s takes linear time the size of the
sets and in the worst case we can have `n` unions of sets of sizes
`(n-1, 1), (n-2, 1)...` making it quadratic.

One reason why we need deterministic `tyVarsOfType` is in `abstractVars`
in `SetLevels`. When we abstract type variables when floating we want
them to be abstracted in deterministic order.

Test Plan: harbormaster

Reviewers: simonpj, goldfire, austin, hvr, simonmar, bgamari

Reviewed By: simonmar

Subscribers: thomie

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

GHC Trac Issues: #4012

1 files changed, 39 insertions, 39 deletions

diff --git a/testsuite/tests/partial-sigs/should_compile/T10403.stderr b/testsuite/tests/partial-sigs/should_compile/T10403.stderr
index 8af7da3d81..bfd5367bcd 100644
--- a/testsuite/tests/partial-sigs/should_compile/T10403.stderr
+++ b/testsuite/tests/partial-sigs/should_compile/T10403.stderr
@@ -1,39 +1,39 @@
-

-T10403.hs:15:7: warning:

-    Found hole ‘_’ with inferred constraints: Functor f

-    In the type signature for:

-      h1 :: _ => _

-

-T10403.hs:15:12: warning:

-    Found type wildcard ‘_’ standing for ‘(a -> b) -> f a -> H f’

-    Where: ‘f’ is a rigid type variable bound by

-               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:17:1

-           ‘b’ is a rigid type variable bound by

-               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:17:1

-           ‘a’ is a rigid type variable bound by

-               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:17:1

-    In the type signature for:

-      h1 :: _ => _

-

-T10403.hs:19:7: warning:

-    Found type wildcard ‘_’ standing for ‘(a -> b) -> f a -> H f’

-    Where: ‘f’ is a rigid type variable bound by

-               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:21:1

-           ‘b’ is a rigid type variable bound by

-               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:21:1

-           ‘a’ is a rigid type variable bound by

-               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:21:1

-    In the type signature for:

-      h2 :: _

-

-T10403.hs:21:1: warning:

-    No instance for (Functor f)

-    When checking that ‘h2’ has the inferred type

-      h2 :: forall (f :: * -> *) b a. (a -> b) -> f a -> H f

-    Probable cause: the inferred type is ambiguous

+
+T10403.hs:15:7: warning:
+    Found hole ‘_’ with inferred constraints: Functor f
+    In the type signature for:
+      h1 :: _ => _
+
+T10403.hs:15:12: warning:
+    Found type wildcard ‘_’ standing for ‘(a -> b) -> f a -> H f’
+    Where: ‘b’ is a rigid type variable bound by
+               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:17:1
+           ‘a’ is a rigid type variable bound by
+               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:17:1
+           ‘f’ is a rigid type variable bound by
+               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:17:1
+    In the type signature for:
+      h1 :: _ => _
+
+T10403.hs:19:7: warning:
+    Found type wildcard ‘_’ standing for ‘(a -> b) -> f a -> H f’
+    Where: ‘b’ is a rigid type variable bound by
+               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:21:1
+           ‘a’ is a rigid type variable bound by
+               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:21:1
+           ‘f’ is a rigid type variable bound by
+               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:21:1
+    In the type signature for:
+      h2 :: _
+
+T10403.hs:21:1: warning:
+    No instance for (Functor f)
+    When checking that ‘h2’ has the inferred type
+      h2 :: forall (f :: * -> *) b a. (a -> b) -> f a -> H f
+    Probable cause: the inferred type is ambiguous