Update Trac ticket URLs to point to GitLab
[ghc.git] / testsuite / tests / perf / compiler / T9872d.hs
1 {-# LANGUAGE DataKinds #-}
2 {-# LANGUAGE GADTs #-}
3 {-# LANGUAGE PolyKinds #-}
4 {-# LANGUAGE ScopedTypeVariables #-}
5 {-# LANGUAGE TypeFamilies #-}
6 {-# LANGUAGE TypeOperators #-}
7 {-# LANGUAGE UndecidableInstances #-}
8 {-# OPTIONS_GHC -freduction-depth=0 #-} -- this should terminate!
9
10 module T9872d where
11 -- Code from Jan Stolarek, labelled "exp-tyfams.hs" on #9872,
12 -- generated by a Template Haskell program
13
14
15 -- This file demonstrates exponential compile times with type
16 -- families. Code in this file was extracted from encoding generated
17 -- automatically with Template Haskell by singletons library.
18
19 import Data.Kind
20 import GHC.TypeLits
21
22 -- encoding of type-level partially applied functions
23 data TyFun :: Type -> Type -> Type
24 type family Apply (f :: TyFun k1 k2 -> Type) (x :: k1) :: k2
25 type a @@ b = Apply a b
26
27 -- some boilerplate
28 type family Error (a :: k) :: k1
29 type ErrorSym1 a = Error a
30 data ErrorSym0 :: TyFun a b -> Type
31 type instance Apply ErrorSym0 e = Error e
32 data Proxy a = Proxy
33 data KProxy (a :: Type) = KProxy
34 type KindOf (a :: k) = ('KProxy :: KProxy k)
35
36 -- type-level addition
37 type (:+$$$) (t1 :: Nat) (t2 :: Nat) = t1 + t2
38
39 data (:+$$) (l :: Nat) (tf :: TyFun Nat Nat)
40 = forall a. (KindOf (Apply ((:+$$) l) a)) ~ (KindOf ((:+$$$) l a)) =>
41 (:+$$###)
42 type instance Apply ((:+$$) l1) l2 = (:+$$$) l1 l2
43
44 data (:+$) (l :: TyFun Nat (TyFun Nat Nat -> Type))
45 = forall a. (KindOf (Apply (:+$) a)) ~ (KindOf ((:+$$) a)) => (:+$###)
46 type instance Apply (:+$) l = (:+$$) l
47
48 -- type-level lists
49 type NilSym0 = '[]
50
51 type ConsSym2 (x :: a) (xs :: [a]) = x ': xs
52
53 data ConsSym1 (x :: a) (l_a3t6 :: TyFun [a] [a])
54 = forall b. (KindOf (Apply (ConsSym1 x) b)) ~ (KindOf (ConsSym2 x b)) =>
55 (:$$###)
56 type instance Apply (ConsSym1 x) xs = ConsSym2 x xs
57
58 data ConsSym0 (l :: TyFun a (TyFun [a] [a] -> Type))
59 = forall a. (KindOf (Apply ConsSym0 a)) ~ (KindOf (ConsSym1 a)) => (:$###)
60 type instance Apply ConsSym0 l = ConsSym1 l
61
62 type Let_1627403919Scrutinee_1627403894Sym4 t1 t2 t3 t4 =
63 Let_1627403919Scrutinee_1627403894 t1 t2 t3 t4
64
65 data Let_1627403919Scrutinee_1627403894Sym3 l_a3Dx
66 l_a3Dy
67 l_a3Dz
68 l_a3Dw
69 = forall arg_a3DA. (KindOf (Apply (Let_1627403919Scrutinee_1627403894Sym3
70 l_a3Dx l_a3Dy l_a3Dz) arg_a3DA)) ~
71 (KindOf (Let_1627403919Scrutinee_1627403894Sym4
72 l_a3Dx l_a3Dy l_a3Dz arg_a3DA)) =>
73 Let_1627403919Scrutinee_1627403894Sym3KindInference
74 type instance Apply (Let_1627403919Scrutinee_1627403894Sym3
75 l_a3Dx l_a3Dy l_a3Dz) l_a3Dw =
76 Let_1627403919Scrutinee_1627403894Sym4 l_a3Dx l_a3Dy l_a3Dz l_a3Dw
77
78 data Let_1627403919Scrutinee_1627403894Sym2 l_a3Dt l_a3Du l_a3Ds
79 = forall arg_a3Dv. (KindOf (Apply (Let_1627403919Scrutinee_1627403894Sym2
80 l_a3Dt l_a3Du) arg_a3Dv)) ~
81 (KindOf (Let_1627403919Scrutinee_1627403894Sym3
82 l_a3Dt l_a3Du arg_a3Dv)) =>
83 Let_1627403919Scrutinee_1627403894Sym2KindInference
84 type instance Apply
85 (Let_1627403919Scrutinee_1627403894Sym2 l_a3Dt l_a3Du) l_a3Ds =
86 Let_1627403919Scrutinee_1627403894Sym3 l_a3Dt l_a3Du l_a3Ds
87 data Let_1627403919Scrutinee_1627403894Sym1 l_a3Dq l_a3Dp
88 = forall arg_a3Dr. (KindOf (Apply (Let_1627403919Scrutinee_1627403894Sym1
89 l_a3Dq) arg_a3Dr)) ~
90 (KindOf (Let_1627403919Scrutinee_1627403894Sym2
91 l_a3Dq arg_a3Dr)) =>
92 Let_1627403919Scrutinee_1627403894Sym1KindInference
93 type instance Apply (Let_1627403919Scrutinee_1627403894Sym1 l_a3Dq)
94 l_a3Dp
95 = Let_1627403919Scrutinee_1627403894Sym2 l_a3Dq l_a3Dp
96 data Let_1627403919Scrutinee_1627403894Sym0 l_a3Dn
97 = forall arg_a3Do. (KindOf (Apply Let_1627403919Scrutinee_1627403894Sym0
98 arg_a3Do)) ~
99 (KindOf (Let_1627403919Scrutinee_1627403894Sym1
100 arg_a3Do)) =>
101 Let_1627403919Scrutinee_1627403894Sym0KindInference
102 type instance Apply Let_1627403919Scrutinee_1627403894Sym0 l_a3Dn
103 = Let_1627403919Scrutinee_1627403894Sym1 l_a3Dn
104 type Let_1627403919Scrutinee_1627403894 f_a3Dd
105 q0_a3De
106 x_a3Df
107 xs_a3Dg =
108 Apply (Apply (Apply ScanrSym0 f_a3Dd) q0_a3De) xs_a3Dg
109
110 type family Case f q0 x xs t :: [k] where
111 Case f q0 x xs '[] = ErrorSym0 @@ "empty list"
112 Case f q0 x xs (q ': qs) = ConsSym0 @@ (f @@ x @@ q) @@ (ConsSym0 @@ q @@ qs)
113
114 -- type-level scanr
115 type ScanrSym3 (t1 :: TyFun a (TyFun b b -> Type) -> Type)
116 (t2 :: b)
117 (t3 :: [a]) =
118 Scanr t1 t2 t3
119
120 data ScanrSym2 (l1 :: TyFun a (TyFun b b -> Type) -> Type)
121 (l2 :: b)
122 (l3 :: TyFun [a] [b])
123 = forall a. (KindOf (Apply (ScanrSym2 l1 l2) a)) ~
124 (KindOf (ScanrSym3 l1 l2 a)) =>
125 ScanrSym2KindInference
126 type instance Apply (ScanrSym2 l1 l2) l3 = ScanrSym3 l1 l2 l3
127
128 data ScanrSym1 (l_a3D0 :: TyFun a_a3CJ (TyFun b_a3CK b_a3CK -> Type) -> Type)
129 (l_a3CZ :: TyFun b_a3CK (TyFun ([a_a3CJ]) ([b_a3CK])
130 -> Type))
131 = forall arg_a3D1. (KindOf (Apply (ScanrSym1 l_a3D0) arg_a3D1)) ~
132 (KindOf (ScanrSym2 l_a3D0 arg_a3D1)) =>
133 ScanrSym1KindInference
134 type instance Apply (ScanrSym1 l_a3D0) l_a3CZ = ScanrSym2 l_a3D0 l_a3CZ
135
136 data ScanrSym0 (l :: TyFun (TyFun a (TyFun b b -> Type) -> Type)
137 (TyFun b (TyFun [a] [b] -> Type) -> Type))
138 = forall a. (KindOf (Apply ScanrSym0 a)) ~ (KindOf (ScanrSym1 a)) =>
139 ScanrSym0KindInference
140 type instance Apply ScanrSym0 l1 = ScanrSym1 l1
141
142 type family Scanr (a_a3D6 :: TyFun a_a3CJ (TyFun b_a3CK b_a3CK -> Type) -> Type)
143 (a_a3D7 :: b_a3CK)
144 (a_a3D8 :: [a_a3CJ]) :: [b_a3CK] where
145 Scanr _z_1627403911_a3Db q0_a3Dc '[] = Apply (Apply ConsSym0 q0_a3Dc) NilSym0
146 Scanr f_a3Dd q0_a3De (x_a3Df ': xs_a3Dg) =
147 Case f_a3Dd q0_a3De x_a3Df xs_a3Dg (Let_1627403919Scrutinee_1627403894Sym4
148 f_a3Dd q0_a3De x_a3Df xs_a3Dg)
149
150
151 {-
152 foo32 :: Proxy ('[528,527,525,522,518,513,507,500,492,483,473,462,450,437,423,
153 408,392,375,357,338,318,297,275,252,228,203,177,150,122,93,
154 63,32,0])
155 foo32 = Proxy
156
157 bar32 :: Proxy (ScanrSym0 @@ (:+$) @@ 0 @@ '[1,2,3,4,5,6,7,8,9,10,11,12,13,14,
158 15,16,17,18,19,20,21,22,23,24,25,
159 26,27,28,29,30,31,32])
160 bar32 = foo32
161
162 -}
163 {-
164 foo64 :: Proxy ('[2080,2079,2077,2074,2070,2065,2059,2052,2044,2035,2025,2014,
165 2002,1989,1975,1960,1944,1927,1909,1890,1870,1849,1827,1804,
166 1780,1755,1729,1702,1674,1645,1615,1584,1552,1519,1485,1450,
167 1414,1377,1339,1300,1260,1219,1177,1134,1090,1045,999,952,904,
168 855,805,754,702,649,595,540,484,427,369,310,250,189,127,64,0])
169 foo64 = Proxy
170
171 bar64 :: Proxy (ScanrSym0 @@ (:+$) @@ 0 @@ '[1,2,3,4,5,6,7,8,9,10,11,12,13,14,
172 15,16,17,18,19,20,21,22,23,24,25,
173 26,27,28,29,30,31,32,33,34,35,36,
174 37,38,39,40,41,42,43,44,45,46,47,
175 48,49,50,51,52,53,54,55,56,57,58,
176 59,60,61,62,63,64])
177 bar64 = foo64
178
179
180 foo128 :: Proxy ('[8256,8255,8253,8250,8246,8241,8235,8228,8220,8211,8201,8190,
181 8178,8165,8151,8136,8120,8103,8085,8066,8046,8025,8003,7980,
182 7956,7931,7905,7878,7850,7821,7791,7760,7728,7695,7661,7626,
183 7590,7553,7515,7476,7436,7395,7353,7310,7266,7221,7175,7128,
184 7080,7031,6981,6930,6878,6825,6771,6716,6660,6603,6545,6486,
185 6426,6365,6303,6240,6176,6111,6045,5978,5910,5841,5771,5700,
186 5628,5555,5481,5406,5330,5253,5175,5096,5016,4935,4853,4770,
187 4686,4601,4515,4428,4340,4251,4161,4070,3978,3885,3791,3696,
188 3600,3503,3405,3306,3206,3105,3003,2900,2796,2691,2585,2478,
189 2370,2261,2151,2040,1928,1815,1701,1586,1470,1353,1235,1116,
190 996,875,753,630,506,381,255,128,0])
191 foo128 = Proxy
192
193 bar128 :: Proxy (ScanrSym0 @@ (:+$) @@ 0 @@ '[1,2,3,4,5,6,7,8,9,10,11,12,13,14,
194 15,16,17,18,19,20,21,22,23,24,25,
195 26,27,28,29,30,31,32,33,34,35,36,
196 37,38,39,40,41,42,43,44,45,46,47,
197 48,49,50,51,52,53,54,55,56,57,58,
198 59,60,61,62,63,64,65,66,67,68,69,
199 70,71,72,73,74,75,76,77,78,79,80,
200 81,82,83,84,85,86,87,88,89,90,91,
201 92,93,94,95,96,97,98,99,100,101,
202 102,103,104,105,106,107,108,109,
203 110,111,112,113,114,115,116,117,
204 118,119,120,121,122,123,124,125,
205 126,127,128])
206 bar128 = foo128
207 -}
208
209 foo256 :: Proxy ('[32896,32895,32893,32890,32886,32881,32875,32868,32860,32851,
210 32841,32830,32818,32805,32791,32776,32760,32743,32725,32706,
211 32686,32665,32643,32620,32596,32571,32545,32518,32490,32461,
212 32431,32400,32368,32335,32301,32266,32230,32193,32155,32116,
213 32076,32035,31993,31950,31906,31861,31815,31768,31720,31671,
214 31621,31570,31518,31465,31411,31356,31300,31243,31185,31126,
215 31066,31005,30943,30880,30816,30751,30685,30618,30550,30481,
216 30411,30340,30268,30195,30121,30046,29970,29893,29815,29736,
217 29656,29575,29493,29410,29326,29241,29155,29068,28980,28891,
218 28801,28710,28618,28525,28431,28336,28240,28143,28045,27946,
219 27846,27745,27643,27540,27436,27331,27225,27118,27010,26901,
220 26791,26680,26568,26455,26341,26226,26110,25993,25875,25756,
221 25636,25515,25393,25270,25146,25021,24895,24768,24640,24511,
222 24381,24250,24118,23985,23851,23716,23580,23443,23305,23166,
223 23026,22885,22743,22600,22456,22311,22165,22018,21870,21721,
224 21571,21420,21268,21115,20961,20806,20650,20493,20335,20176,
225 20016,19855,19693,19530,19366,19201,19035,18868,18700,18531,
226 18361,18190,18018,17845,17671,17496,17320,17143,16965,16786,
227 16606,16425,16243,16060,15876,15691,15505,15318,15130,14941,
228 14751,14560,14368,14175,13981,13786,13590,13393,13195,12996,
229 12796,12595,12393,12190,11986,11781,11575,11368,11160,10951,
230 10741,10530,10318,10105,9891,9676,9460,9243,9025,8806,
231 8586,8365,8143,7920,7696,7471,7245,7018,6790,6561,6331,6100,
232 5868,5635,5401,5166,4930,4693,4455,4216,3976,3735,3493,3250,
233 3006,2761,2515,2268,2020,1771,1521,1270,1018,765,511,256,0])
234 foo256 = Proxy
235
236 bar256 :: Proxy (ScanrSym0 @@ (:+$) @@ 0 @@ '[1,2,3,4,5,6,7,8,9,10,11,12,13,14,
237 15,16,17,18,19,20,21,22,23,24,25,
238 26,27,28,29,30,31,32,33,34,35,36,
239 37,38,39,40,41,42,43,44,45,46,47,
240 48,49,50,51,52,53,54,55,56,57,58,
241 59,60,61,62,63,64,65,66,67,68,69,
242 70,71,72,73,74,75,76,77,78,79,80,
243 81,82,83,84,85,86,87,88,89,90,91,
244 92,93,94,95,96,97,98,99,100,101,
245 102,103,104,105,106,107,108,109,
246 110,111,112,113,114,115,116,117,
247 118,119,120,121,122,123,124,125,
248 126,127,128,129,130,131,132,133,
249 134,135,136,137,138,139,140,141,
250 142,143,144,145,146,147,148,149,
251 150,151,152,153,154,155,156,157,
252 158,159,160,161,162,163,164,165,
253 166,167,168,169,170,171,172,173,
254 174,175,176,177,178,179,180,181,
255 182,183,184,185,186,187,188,189,
256 190,191,192,193,194,195,196,197,
257 198,199,200,201,202,203,204,205,
258 206,207,208,209,210,211,212,213,
259 214,215,216,217,218,219,220,221,
260 222,223,224,225,226,227,228,229,
261 230,231,232,233,234,235,236,237,
262 238,239,240,241,242,243,244,245,
263 246,247,248,249,250,251,252,253,
264 254,255,256])
265 bar256 = foo256