Warn about unused type variables in type families
[ghc.git] / libraries / base / GHC / Generics.hs
1 {-# LANGUAGE Trustworthy #-}
2 {-# LANGUAGE CPP #-}
3 {-# LANGUAGE NoImplicitPrelude #-}
4 {-# LANGUAGE FlexibleContexts #-}
5 {-# LANGUAGE FlexibleInstances #-}
6 {-# LANGUAGE TypeSynonymInstances #-}
7 {-# LANGUAGE TypeOperators #-}
8 {-# LANGUAGE MagicHash #-}
9 {-# LANGUAGE KindSignatures #-}
10 {-# LANGUAGE TypeFamilies #-}
11 {-# LANGUAGE GADTs #-}
12 {-# LANGUAGE DataKinds #-}
13 {-# LANGUAGE PolyKinds #-}
14 {-# LANGUAGE ScopedTypeVariables #-}
15 {-# LANGUAGE StandaloneDeriving #-}
16 {-# LANGUAGE DeriveGeneric #-}
17 {-# LANGUAGE PolyKinds #-}
18 {-# LANGUAGE MagicHash #-}
19
20 -----------------------------------------------------------------------------
21 -- |
22 -- Module : GHC.Generics
23 -- Copyright : (c) Universiteit Utrecht 2010-2011, University of Oxford 2012-2014
24 -- License : see libraries/base/LICENSE
25 --
26 -- Maintainer : libraries@haskell.org
27 -- Stability : internal
28 -- Portability : non-portable
29 --
30 -- @since 4.6.0.0
31 --
32 -- If you're using @GHC.Generics@, you should consider using the
33 -- <http://hackage.haskell.org/package/generic-deriving> package, which
34 -- contains many useful generic functions.
35
36 module GHC.Generics (
37 -- * Introduction
38 --
39 -- |
40 --
41 -- Datatype-generic functions are based on the idea of converting values of
42 -- a datatype @T@ into corresponding values of a (nearly) isomorphic type @'Rep' T@.
43 -- The type @'Rep' T@ is
44 -- built from a limited set of type constructors, all provided by this module. A
45 -- datatype-generic function is then an overloaded function with instances
46 -- for most of these type constructors, together with a wrapper that performs
47 -- the mapping between @T@ and @'Rep' T@. By using this technique, we merely need
48 -- a few generic instances in order to implement functionality that works for any
49 -- representable type.
50 --
51 -- Representable types are collected in the 'Generic' class, which defines the
52 -- associated type 'Rep' as well as conversion functions 'from' and 'to'.
53 -- Typically, you will not define 'Generic' instances by hand, but have the compiler
54 -- derive them for you.
55
56 -- ** Representing datatypes
57 --
58 -- |
59 --
60 -- The key to defining your own datatype-generic functions is to understand how to
61 -- represent datatypes using the given set of type constructors.
62 --
63 -- Let us look at an example first:
64 --
65 -- @
66 -- data Tree a = Leaf a | Node (Tree a) (Tree a)
67 -- deriving 'Generic'
68 -- @
69 --
70 -- The above declaration (which requires the language pragma @DeriveGeneric@)
71 -- causes the following representation to be generated:
72 --
73 -- @
74 -- instance 'Generic' (Tree a) where
75 -- type 'Rep' (Tree a) =
76 -- 'D1' ('MetaData \"Tree\" \"Main\" \"package-name\" 'False)
77 -- ('C1' ('MetaCons \"Leaf\" 'PrefixI 'False)
78 -- ('S1' 'MetaNoSel ('Rec0' a))
79 -- ':+:'
80 -- 'C1' ('MetaCons \"Node\" 'PrefixI 'False)
81 -- ('S1' 'MetaNoSel ('Rec0' (Tree a))
82 -- ':*:'
83 -- 'S1' 'MetaNoSel ('Rec0' (Tree a))))
84 -- ...
85 -- @
86 --
87 -- /Hint:/ You can obtain information about the code being generated from GHC by passing
88 -- the @-ddump-deriv@ flag. In GHCi, you can expand a type family such as 'Rep' using
89 -- the @:kind!@ command.
90 --
91 -- This is a lot of information! However, most of it is actually merely meta-information
92 -- that makes names of datatypes and constructors and more available on the type level.
93 --
94 -- Here is a reduced representation for 'Tree' with nearly all meta-information removed,
95 -- for now keeping only the most essential aspects:
96 --
97 -- @
98 -- instance 'Generic' (Tree a) where
99 -- type 'Rep' (Tree a) =
100 -- 'Rec0' a
101 -- ':+:'
102 -- ('Rec0' (Tree a) ':*:' 'Rec0' (Tree a))
103 -- @
104 --
105 -- The @Tree@ datatype has two constructors. The representation of individual constructors
106 -- is combined using the binary type constructor ':+:'.
107 --
108 -- The first constructor consists of a single field, which is the parameter @a@. This is
109 -- represented as @'Rec0' a@.
110 --
111 -- The second constructor consists of two fields. Each is a recursive field of type @Tree a@,
112 -- represented as @'Rec0' (Tree a)@. Representations of individual fields are combined using
113 -- the binary type constructor ':*:'.
114 --
115 -- Now let us explain the additional tags being used in the complete representation:
116 --
117 -- * The @'S1' 'MetaNoSel@ indicates that there is no record field selector
118 -- associated with this field of the constructor.
119 --
120 -- * The @'C1' ('MetaCons \"Leaf\" 'PrefixI 'False)@ and
121 -- @'C1' ('MetaCons \"Node\" 'PrefixI 'False)@ invocations indicate that the enclosed part is
122 -- the representation of the first and second constructor of datatype @Tree@, respectively.
123 -- Here, the meta-information regarding constructor names, fixity and whether
124 -- it has named fields or not is encoded at the type level. The @'MetaCons@
125 -- type is also an instance of the type class 'Constructor'. This type class can be used
126 -- to obtain information about the constructor at the value level.
127 --
128 -- * The @'D1' ('MetaData \"Tree\" \"Main\" \"package-name\" 'False)@ tag
129 -- indicates that the enclosed part is the representation of the
130 -- datatype @Tree@. Again, the meta-information is encoded at the type level.
131 -- The @'MetaData@ type is an instance of class 'Datatype', which
132 -- can be used to obtain the name of a datatype, the module it has been
133 -- defined in, the package it is located under, and whether it has been
134 -- defined using @data@ or @newtype@ at the value level.
135
136 -- ** Derived and fundamental representation types
137 --
138 -- |
139 --
140 -- There are many datatype-generic functions that do not distinguish between positions that
141 -- are parameters or positions that are recursive calls. There are also many datatype-generic
142 -- functions that do not care about the names of datatypes and constructors at all. To keep
143 -- the number of cases to consider in generic functions in such a situation to a minimum,
144 -- it turns out that many of the type constructors introduced above are actually synonyms,
145 -- defining them to be variants of a smaller set of constructors.
146
147 -- *** Individual fields of constructors: 'K1'
148 --
149 -- |
150 --
151 -- The type constructor 'Rec0' is a variant of 'K1':
152 --
153 -- @
154 -- type 'Rec0' = 'K1' 'R'
155 -- @
156 --
157 -- Here, 'R' is a type-level proxy that does not have any associated values.
158 --
159 -- There used to be another variant of 'K1' (namely 'Par0'), but it has since
160 -- been deprecated.
161
162 -- *** Meta information: 'M1'
163 --
164 -- |
165 --
166 -- The type constructors 'S1', 'C1' and 'D1' are all variants of 'M1':
167 --
168 -- @
169 -- type 'S1' = 'M1' 'S'
170 -- type 'C1' = 'M1' 'C'
171 -- type 'D1' = 'M1' 'D'
172 -- @
173 --
174 -- The types 'S', 'C' and 'D' are once again type-level proxies, just used to create
175 -- several variants of 'M1'.
176
177 -- *** Additional generic representation type constructors
178 --
179 -- |
180 --
181 -- Next to 'K1', 'M1', ':+:' and ':*:' there are a few more type constructors that occur
182 -- in the representations of other datatypes.
183
184 -- **** Empty datatypes: 'V1'
185 --
186 -- |
187 --
188 -- For empty datatypes, 'V1' is used as a representation. For example,
189 --
190 -- @
191 -- data Empty deriving 'Generic'
192 -- @
193 --
194 -- yields
195 --
196 -- @
197 -- instance 'Generic' Empty where
198 -- type 'Rep' Empty =
199 -- 'D1' ('MetaData \"Empty\" \"Main\" \"package-name\" 'False) 'V1'
200 -- @
201
202 -- **** Constructors without fields: 'U1'
203 --
204 -- |
205 --
206 -- If a constructor has no arguments, then 'U1' is used as its representation. For example
207 -- the representation of 'Bool' is
208 --
209 -- @
210 -- instance 'Generic' Bool where
211 -- type 'Rep' Bool =
212 -- 'D1' ('MetaData \"Bool\" \"Data.Bool\" \"package-name\" 'False)
213 -- ('C1' ('MetaCons \"False\" 'PrefixI 'False) 'U1' ':+:' 'C1' ('MetaCons \"True\" 'PrefixI 'False) 'U1')
214 -- @
215
216 -- *** Representation of types with many constructors or many fields
217 --
218 -- |
219 --
220 -- As ':+:' and ':*:' are just binary operators, one might ask what happens if the
221 -- datatype has more than two constructors, or a constructor with more than two
222 -- fields. The answer is simple: the operators are used several times, to combine
223 -- all the constructors and fields as needed. However, users /should not rely on
224 -- a specific nesting strategy/ for ':+:' and ':*:' being used. The compiler is
225 -- free to choose any nesting it prefers. (In practice, the current implementation
226 -- tries to produce a more or less balanced nesting, so that the traversal of the
227 -- structure of the datatype from the root to a particular component can be performed
228 -- in logarithmic rather than linear time.)
229
230 -- ** Defining datatype-generic functions
231 --
232 -- |
233 --
234 -- A datatype-generic function comprises two parts:
235 --
236 -- 1. /Generic instances/ for the function, implementing it for most of the representation
237 -- type constructors introduced above.
238 --
239 -- 2. A /wrapper/ that for any datatype that is in `Generic`, performs the conversion
240 -- between the original value and its `Rep`-based representation and then invokes the
241 -- generic instances.
242 --
243 -- As an example, let us look at a function 'encode' that produces a naive, but lossless
244 -- bit encoding of values of various datatypes. So we are aiming to define a function
245 --
246 -- @
247 -- encode :: 'Generic' a => a -> [Bool]
248 -- @
249 --
250 -- where we use 'Bool' as our datatype for bits.
251 --
252 -- For part 1, we define a class @Encode'@. Perhaps surprisingly, this class is parameterized
253 -- over a type constructor @f@ of kind @* -> *@. This is a technicality: all the representation
254 -- type constructors operate with kind @* -> *@ as base kind. But the type argument is never
255 -- being used. This may be changed at some point in the future. The class has a single method,
256 -- and we use the type we want our final function to have, but we replace the occurrences of
257 -- the generic type argument @a@ with @f p@ (where the @p@ is any argument; it will not be used).
258 --
259 -- > class Encode' f where
260 -- > encode' :: f p -> [Bool]
261 --
262 -- With the goal in mind to make @encode@ work on @Tree@ and other datatypes, we now define
263 -- instances for the representation type constructors 'V1', 'U1', ':+:', ':*:', 'K1', and 'M1'.
264
265 -- *** Definition of the generic representation types
266 --
267 -- |
268 --
269 -- In order to be able to do this, we need to know the actual definitions of these types:
270 --
271 -- @
272 -- data 'V1' p -- lifted version of Empty
273 -- data 'U1' p = 'U1' -- lifted version of ()
274 -- data (':+:') f g p = 'L1' (f p) | 'R1' (g p) -- lifted version of 'Either'
275 -- data (':*:') f g p = (f p) ':*:' (g p) -- lifted version of (,)
276 -- newtype 'K1' i c p = 'K1' { 'unK1' :: c } -- a container for a c
277 -- newtype 'M1' i t f p = 'M1' { 'unM1' :: f p } -- a wrapper
278 -- @
279 --
280 -- So, 'U1' is just the unit type, ':+:' is just a binary choice like 'Either',
281 -- ':*:' is a binary pair like the pair constructor @(,)@, and 'K1' is a value
282 -- of a specific type @c@, and 'M1' wraps a value of the generic type argument,
283 -- which in the lifted world is an @f p@ (where we do not care about @p@).
284
285 -- *** Generic instances
286 --
287 -- |
288 --
289 -- The instance for 'V1' is slightly awkward (but also rarely used):
290 --
291 -- @
292 -- instance Encode' 'V1' where
293 -- encode' x = undefined
294 -- @
295 --
296 -- There are no values of type @V1 p@ to pass (except undefined), so this is
297 -- actually impossible. One can ask why it is useful to define an instance for
298 -- 'V1' at all in this case? Well, an empty type can be used as an argument to
299 -- a non-empty type, and you might still want to encode the resulting type.
300 -- As a somewhat contrived example, consider @[Empty]@, which is not an empty
301 -- type, but contains just the empty list. The 'V1' instance ensures that we
302 -- can call the generic function on such types.
303 --
304 -- There is exactly one value of type 'U1', so encoding it requires no
305 -- knowledge, and we can use zero bits:
306 --
307 -- @
308 -- instance Encode' 'U1' where
309 -- encode' 'U1' = []
310 -- @
311 --
312 -- In the case for ':+:', we produce 'False' or 'True' depending on whether
313 -- the constructor of the value provided is located on the left or on the right:
314 --
315 -- @
316 -- instance (Encode' f, Encode' g) => Encode' (f ':+:' g) where
317 -- encode' ('L1' x) = False : encode' x
318 -- encode' ('R1' x) = True : encode' x
319 -- @
320 --
321 -- In the case for ':*:', we append the encodings of the two subcomponents:
322 --
323 -- @
324 -- instance (Encode' f, Encode' g) => Encode' (f ':*:' g) where
325 -- encode' (x ':*:' y) = encode' x ++ encode' y
326 -- @
327 --
328 -- The case for 'K1' is rather interesting. Here, we call the final function
329 -- 'encode' that we yet have to define, recursively. We will use another type
330 -- class 'Encode' for that function:
331 --
332 -- @
333 -- instance (Encode c) => Encode' ('K1' i c) where
334 -- encode' ('K1' x) = encode x
335 -- @
336 --
337 -- Note how 'Par0' and 'Rec0' both being mapped to 'K1' allows us to define
338 -- a uniform instance here.
339 --
340 -- Similarly, we can define a uniform instance for 'M1', because we completely
341 -- disregard all meta-information:
342 --
343 -- @
344 -- instance (Encode' f) => Encode' ('M1' i t f) where
345 -- encode' ('M1' x) = encode' x
346 -- @
347 --
348 -- Unlike in 'K1', the instance for 'M1' refers to 'encode'', not 'encode'.
349
350 -- *** The wrapper and generic default
351 --
352 -- |
353 --
354 -- We now define class 'Encode' for the actual 'encode' function:
355 --
356 -- @
357 -- class Encode a where
358 -- encode :: a -> [Bool]
359 -- default encode :: ('Generic' a) => a -> [Bool]
360 -- encode x = encode' ('from' x)
361 -- @
362 --
363 -- The incoming 'x' is converted using 'from', then we dispatch to the
364 -- generic instances using 'encode''. We use this as a default definition
365 -- for 'encode'. We need the 'default encode' signature because ordinary
366 -- Haskell default methods must not introduce additional class constraints,
367 -- but our generic default does.
368 --
369 -- Defining a particular instance is now as simple as saying
370 --
371 -- @
372 -- instance (Encode a) => Encode (Tree a)
373 -- @
374 --
375 #if 0
376 -- /TODO:/ Add usage example?
377 --
378 #endif
379 -- The generic default is being used. In the future, it will hopefully be
380 -- possible to use @deriving Encode@ as well, but GHC does not yet support
381 -- that syntax for this situation.
382 --
383 -- Having 'Encode' as a class has the advantage that we can define
384 -- non-generic special cases, which is particularly useful for abstract
385 -- datatypes that have no structural representation. For example, given
386 -- a suitable integer encoding function 'encodeInt', we can define
387 --
388 -- @
389 -- instance Encode Int where
390 -- encode = encodeInt
391 -- @
392
393 -- *** Omitting generic instances
394 --
395 -- |
396 --
397 -- It is not always required to provide instances for all the generic
398 -- representation types, but omitting instances restricts the set of
399 -- datatypes the functions will work for:
400 --
401 -- * If no ':+:' instance is given, the function may still work for
402 -- empty datatypes or datatypes that have a single constructor,
403 -- but will fail on datatypes with more than one constructor.
404 --
405 -- * If no ':*:' instance is given, the function may still work for
406 -- datatypes where each constructor has just zero or one field,
407 -- in particular for enumeration types.
408 --
409 -- * If no 'K1' instance is given, the function may still work for
410 -- enumeration types, where no constructor has any fields.
411 --
412 -- * If no 'V1' instance is given, the function may still work for
413 -- any datatype that is not empty.
414 --
415 -- * If no 'U1' instance is given, the function may still work for
416 -- any datatype where each constructor has at least one field.
417 --
418 -- An 'M1' instance is always required (but it can just ignore the
419 -- meta-information, as is the case for 'encode' above).
420 #if 0
421 -- *** Using meta-information
422 --
423 -- |
424 --
425 -- TODO
426 #endif
427 -- ** Generic constructor classes
428 --
429 -- |
430 --
431 -- Datatype-generic functions as defined above work for a large class
432 -- of datatypes, including parameterized datatypes. (We have used 'Tree'
433 -- as our example above, which is of kind @* -> *@.) However, the
434 -- 'Generic' class ranges over types of kind @*@, and therefore, the
435 -- resulting generic functions (such as 'encode') must be parameterized
436 -- by a generic type argument of kind @*@.
437 --
438 -- What if we want to define generic classes that range over type
439 -- constructors (such as 'Functor', 'Traversable', or 'Foldable')?
440
441 -- *** The 'Generic1' class
442 --
443 -- |
444 --
445 -- Like 'Generic', there is a class 'Generic1' that defines a
446 -- representation 'Rep1' and conversion functions 'from1' and 'to1',
447 -- only that 'Generic1' ranges over types of kind @* -> *@.
448 -- The 'Generic1' class is also derivable.
449 --
450 -- The representation 'Rep1' is ever so slightly different from 'Rep'.
451 -- Let us look at 'Tree' as an example again:
452 --
453 -- @
454 -- data Tree a = Leaf a | Node (Tree a) (Tree a)
455 -- deriving 'Generic1'
456 -- @
457 --
458 -- The above declaration causes the following representation to be generated:
459 --
460 -- @
461 -- instance 'Generic1' Tree where
462 -- type 'Rep1' Tree =
463 -- 'D1' ('MetaData \"Tree\" \"Main\" \"package-name\" 'False)
464 -- ('C1' ('MetaCons \"Leaf\" 'PrefixI 'False)
465 -- ('S1' 'MetaNoSel 'Par1')
466 -- ':+:'
467 -- 'C1' ('MetaCons \"Node\" 'PrefixI 'False)
468 -- ('S1' 'MetaNoSel ('Rec1' Tree)
469 -- ':*:'
470 -- 'S1' 'MetaNoSel ('Rec1' Tree)))
471 -- ...
472 -- @
473 --
474 -- The representation reuses 'D1', 'C1', 'S1' (and thereby 'M1') as well
475 -- as ':+:' and ':*:' from 'Rep'. (This reusability is the reason that we
476 -- carry around the dummy type argument for kind-@*@-types, but there are
477 -- already enough different names involved without duplicating each of
478 -- these.)
479 --
480 -- What's different is that we now use 'Par1' to refer to the parameter
481 -- (and that parameter, which used to be @a@), is not mentioned explicitly
482 -- by name anywhere; and we use 'Rec1' to refer to a recursive use of @Tree a@.
483
484 -- *** Representation of @* -> *@ types
485 --
486 -- |
487 --
488 -- Unlike 'Rec0', the 'Par1' and 'Rec1' type constructors do not
489 -- map to 'K1'. They are defined directly, as follows:
490 --
491 -- @
492 -- newtype 'Par1' p = 'Par1' { 'unPar1' :: p } -- gives access to parameter p
493 -- newtype 'Rec1' f p = 'Rec1' { 'unRec1' :: f p } -- a wrapper
494 -- @
495 --
496 -- In 'Par1', the parameter @p@ is used for the first time, whereas 'Rec1' simply
497 -- wraps an application of @f@ to @p@.
498 --
499 -- Note that 'K1' (in the guise of 'Rec0') can still occur in a 'Rep1' representation,
500 -- namely when the datatype has a field that does not mention the parameter.
501 --
502 -- The declaration
503 --
504 -- @
505 -- data WithInt a = WithInt Int a
506 -- deriving 'Generic1'
507 -- @
508 --
509 -- yields
510 --
511 -- @
512 -- class 'Rep1' WithInt where
513 -- type 'Rep1' WithInt =
514 -- 'D1' ('MetaData \"WithInt\" \"Main\" \"package-name\" 'False)
515 -- ('C1' ('MetaCons \"WithInt\" 'PrefixI 'False)
516 -- ('S1' 'MetaNoSel ('Rec0' Int)
517 -- ':*:'
518 -- 'S1' 'MetaNoSel 'Par1'))
519 -- @
520 --
521 -- If the parameter @a@ appears underneath a composition of other type constructors,
522 -- then the representation involves composition, too:
523 --
524 -- @
525 -- data Rose a = Fork a [Rose a]
526 -- @
527 --
528 -- yields
529 --
530 -- @
531 -- class 'Rep1' Rose where
532 -- type 'Rep1' Rose =
533 -- 'D1' ('MetaData \"Rose\" \"Main\" \"package-name\" 'False)
534 -- ('C1' ('MetaCons \"Fork\" 'PrefixI 'False)
535 -- ('S1' 'MetaNoSel 'Par1'
536 -- ':*:'
537 -- 'S1' 'MetaNoSel ([] ':.:' 'Rec1' Rose)
538 -- @
539 --
540 -- where
541 --
542 -- @
543 -- newtype (':.:') f g p = 'Comp1' { 'unComp1' :: f (g p) }
544 -- @
545
546 -- *** Representation of unlifted types
547 --
548 -- |
549 --
550 -- If one were to attempt to derive a Generic instance for a datatype with an
551 -- unlifted argument (for example, 'Int#'), one might expect the occurrence of
552 -- the 'Int#' argument to be marked with @'Rec0' 'Int#'@. This won't work,
553 -- though, since 'Int#' is of kind @#@ and 'Rec0' expects a type of kind @*@.
554 -- In fact, polymorphism over unlifted types is disallowed completely.
555 --
556 -- One solution would be to represent an occurrence of 'Int#' with 'Rec0 Int'
557 -- instead. With this approach, however, the programmer has no way of knowing
558 -- whether the 'Int' is actually an 'Int#' in disguise.
559 --
560 -- Instead of reusing 'Rec0', a separate data family 'URec' is used to mark
561 -- occurrences of common unlifted types:
562 --
563 -- @
564 -- data family URec a p
565 --
566 -- data instance 'URec' ('Ptr' ()) p = 'UAddr' { 'uAddr#' :: 'Addr#' }
567 -- data instance 'URec' 'Char' p = 'UChar' { 'uChar#' :: 'Char#' }
568 -- data instance 'URec' 'Double' p = 'UDouble' { 'uDouble#' :: 'Double#' }
569 -- data instance 'URec' 'Int' p = 'UFloat' { 'uFloat#' :: 'Float#' }
570 -- data instance 'URec' 'Float' p = 'UInt' { 'uInt#' :: 'Int#' }
571 -- data instance 'URec' 'Word' p = 'UWord' { 'uWord#' :: 'Word#' }
572 -- @
573 --
574 -- Several type synonyms are provided for convenience:
575 --
576 -- @
577 -- type 'UAddr' = 'URec' ('Ptr' ())
578 -- type 'UChar' = 'URec' 'Char'
579 -- type 'UDouble' = 'URec' 'Double'
580 -- type 'UFloat' = 'URec' 'Float'
581 -- type 'UInt' = 'URec' 'Int'
582 -- type 'UWord' = 'URec' 'Word'
583 -- @
584 --
585 -- The declaration
586 --
587 -- @
588 -- data IntHash = IntHash Int#
589 -- deriving 'Generic'
590 -- @
591 --
592 -- yields
593 --
594 -- @
595 -- instance 'Generic' IntHash where
596 -- type 'Rep' IntHash =
597 -- 'D1' ('MetaData \"IntHash\" \"Main\" \"package-name\" 'False)
598 -- ('C1' ('MetaCons \"IntHash\" 'PrefixI 'False)
599 -- ('S1' 'MetaNoSel 'UInt'))
600 -- @
601 --
602 -- Currently, only the six unlifted types listed above are generated, but this
603 -- may be extended to encompass more unlifted types in the future.
604 #if 0
605 -- *** Limitations
606 --
607 -- |
608 --
609 -- /TODO/
610 --
611 -- /TODO:/ Also clear up confusion about 'Rec0' and 'Rec1' not really indicating recursion.
612 --
613 #endif
614 -----------------------------------------------------------------------------
615
616 -- * Generic representation types
617 V1, U1(..), Par1(..), Rec1(..), K1(..), M1(..)
618 , (:+:)(..), (:*:)(..), (:.:)(..)
619
620 -- ** Unboxed representation types
621 , URec(..)
622 , type UAddr, type UChar, type UDouble
623 , type UFloat, type UInt, type UWord
624
625 -- ** Synonyms for convenience
626 , Rec0, R
627 , D1, C1, S1, D, C, S
628
629 -- * Meta-information
630 , Datatype(..), Constructor(..), Selector(..), NoSelector
631 , Fixity(..), FixityI(..), Associativity(..), prec
632 , Meta(..)
633
634 -- * Generic type classes
635 , Generic(..), Generic1(..)
636
637 ) where
638
639 -- We use some base types
640 import GHC.Integer ( Integer, integerToInt )
641 import GHC.Prim ( Addr#, Char#, Double#, Float#, Int#, Word# )
642 import GHC.Ptr ( Ptr )
643 import GHC.Types
644 import Data.Maybe ( Maybe(..) )
645 import Data.Either ( Either(..) )
646
647 -- Needed for instances
648 import GHC.Classes ( Eq, Ord )
649 import GHC.Read ( Read )
650 import GHC.Show ( Show )
651
652 -- Needed for metadata
653 import Data.Proxy ( Proxy(..), KProxy(..) )
654 import GHC.TypeLits ( Nat, Symbol, KnownSymbol, KnownNat, symbolVal, natVal )
655
656 --------------------------------------------------------------------------------
657 -- Representation types
658 --------------------------------------------------------------------------------
659
660 -- | Void: used for datatypes without constructors
661 data V1 (p :: *)
662
663 -- | Unit: used for constructors without arguments
664 data U1 (p :: *) = U1
665 deriving (Eq, Ord, Read, Show, Generic)
666
667 -- | Used for marking occurrences of the parameter
668 newtype Par1 p = Par1 { unPar1 :: p }
669 deriving (Eq, Ord, Read, Show, Generic)
670
671 -- | Recursive calls of kind * -> *
672 newtype Rec1 f (p :: *) = Rec1 { unRec1 :: f p }
673 deriving (Eq, Ord, Read, Show, Generic)
674
675 -- | Constants, additional parameters and recursion of kind *
676 newtype K1 (i :: *) c (p :: *) = K1 { unK1 :: c }
677 deriving (Eq, Ord, Read, Show, Generic)
678
679 -- | Meta-information (constructor names, etc.)
680 newtype M1 (i :: *) (c :: Meta) f (p :: *) = M1 { unM1 :: f p }
681 deriving (Eq, Ord, Read, Show, Generic)
682
683 -- | Sums: encode choice between constructors
684 infixr 5 :+:
685 data (:+:) f g (p :: *) = L1 (f p) | R1 (g p)
686 deriving (Eq, Ord, Read, Show, Generic)
687
688 -- | Products: encode multiple arguments to constructors
689 infixr 6 :*:
690 data (:*:) f g (p :: *) = f p :*: g p
691 deriving (Eq, Ord, Read, Show, Generic)
692
693 -- | Composition of functors
694 infixr 7 :.:
695 newtype (:.:) f (g :: * -> *) (p :: *) = Comp1 { unComp1 :: f (g p) }
696 deriving (Eq, Ord, Read, Show, Generic)
697
698 -- | Constants of kind @#@
699 data family URec (a :: *) (p :: *)
700
701 -- | Used for marking occurrences of 'Addr#'
702 data instance URec (Ptr ()) _p = UAddr { uAddr# :: Addr# }
703 deriving (Eq, Ord, Generic)
704
705 -- | Used for marking occurrences of 'Char#'
706 data instance URec Char _p = UChar { uChar# :: Char# }
707 deriving (Eq, Ord, Show, Generic)
708
709 -- | Used for marking occurrences of 'Double#'
710 data instance URec Double _p = UDouble { uDouble# :: Double# }
711 deriving (Eq, Ord, Show, Generic)
712
713 -- | Used for marking occurrences of 'Float#'
714 data instance URec Float _p = UFloat { uFloat# :: Float# }
715 deriving (Eq, Ord, Show, Generic)
716
717 -- | Used for marking occurrences of 'Int#'
718 data instance URec Int _p = UInt { uInt# :: Int# }
719 deriving (Eq, Ord, Show, Generic)
720
721 -- | Used for marking occurrences of 'Word#'
722 data instance URec Word _p = UWord { uWord# :: Word# }
723 deriving (Eq, Ord, Show, Generic)
724
725 -- | Type synonym for 'URec': 'Addr#'
726 type UAddr = URec (Ptr ())
727 -- | Type synonym for 'URec': 'Char#'
728 type UChar = URec Char
729 -- | Type synonym for 'URec': 'Double#'
730 type UDouble = URec Double
731 -- | Type synonym for 'URec': 'Float#'
732 type UFloat = URec Float
733 -- | Type synonym for 'URec': 'Int#'
734 type UInt = URec Int
735 -- | Type synonym for 'URec': 'Word#'
736 type UWord = URec Word
737
738 -- | Tag for K1: recursion (of kind *)
739 data R
740
741 -- | Type synonym for encoding recursion (of kind *)
742 type Rec0 = K1 R
743
744 -- | Tag for M1: datatype
745 data D
746 -- | Tag for M1: constructor
747 data C
748 -- | Tag for M1: record selector
749 data S
750
751 -- | Type synonym for encoding meta-information for datatypes
752 type D1 = M1 D
753
754 -- | Type synonym for encoding meta-information for constructors
755 type C1 = M1 C
756
757 -- | Type synonym for encoding meta-information for record selectors
758 type S1 = M1 S
759
760 -- | Class for datatypes that represent datatypes
761 class Datatype d where
762 -- | The name of the datatype (unqualified)
763 datatypeName :: t d (f :: * -> *) a -> [Char]
764 -- | The fully-qualified name of the module where the type is declared
765 moduleName :: t d (f :: * -> *) a -> [Char]
766 -- | The package name of the module where the type is declared
767 packageName :: t d (f :: * -> *) a -> [Char]
768 -- | Marks if the datatype is actually a newtype
769 isNewtype :: t d (f :: * -> *) a -> Bool
770 isNewtype _ = False
771
772 instance (KnownSymbol n, KnownSymbol m, KnownSymbol p, SingI nt)
773 => Datatype ('MetaData n m p nt) where
774 datatypeName _ = symbolVal (Proxy :: Proxy n)
775 moduleName _ = symbolVal (Proxy :: Proxy m)
776 packageName _ = symbolVal (Proxy :: Proxy p)
777 isNewtype _ = fromSing (sing :: Sing nt)
778
779 -- | Class for datatypes that represent data constructors
780 class Constructor c where
781 -- | The name of the constructor
782 conName :: t c (f :: * -> *) a -> [Char]
783
784 -- | The fixity of the constructor
785 conFixity :: t c (f :: * -> *) a -> Fixity
786 conFixity _ = Prefix
787
788 -- | Marks if this constructor is a record
789 conIsRecord :: t c (f :: * -> *) a -> Bool
790 conIsRecord _ = False
791
792 instance (KnownSymbol n, SingI f, SingI r)
793 => Constructor ('MetaCons n f r) where
794 conName _ = symbolVal (Proxy :: Proxy n)
795 conFixity _ = fromSing (sing :: Sing f)
796 conIsRecord _ = fromSing (sing :: Sing r)
797
798 -- | Datatype to represent the fixity of a constructor. An infix
799 -- | declaration directly corresponds to an application of 'Infix'.
800 data Fixity = Prefix | Infix Associativity Int
801 deriving (Eq, Show, Ord, Read, Generic)
802
803 -- | This variant of 'Fixity' appears at the type level.
804 data FixityI = PrefixI | InfixI Associativity Nat
805
806 -- | Get the precedence of a fixity value.
807 prec :: Fixity -> Int
808 prec Prefix = 10
809 prec (Infix _ n) = n
810
811 -- | Datatype to represent the associativity of a constructor
812 data Associativity = LeftAssociative
813 | RightAssociative
814 | NotAssociative
815 deriving (Eq, Show, Ord, Read, Generic)
816
817 -- | Class for datatypes that represent records
818 class Selector s where
819 -- | The name of the selector
820 selName :: t s (f :: * -> *) a -> [Char]
821
822 -- | Used for constructor fields without a name
823 -- Deprecated in 7.9
824 {-# DEPRECATED NoSelector "'NoSelector' is no longer used" #-}
825 data NoSelector
826 instance Selector NoSelector where selName _ = ""
827
828 instance (KnownSymbol s) => Selector ('MetaSel s) where
829 selName _ = symbolVal (Proxy :: Proxy s)
830
831 instance Selector 'MetaNoSel where
832 selName _ = ""
833
834 -- | Representable types of kind *.
835 -- This class is derivable in GHC with the DeriveGeneric flag on.
836 class Generic a where
837 -- | Generic representation type
838 type Rep a :: * -> *
839 -- | Convert from the datatype to its representation
840 from :: a -> (Rep a) x
841 -- | Convert from the representation to the datatype
842 to :: (Rep a) x -> a
843
844
845 -- | Representable types of kind * -> *.
846 -- This class is derivable in GHC with the DeriveGeneric flag on.
847 class Generic1 f where
848 -- | Generic representation type
849 type Rep1 f :: * -> *
850 -- | Convert from the datatype to its representation
851 from1 :: f a -> (Rep1 f) a
852 -- | Convert from the representation to the datatype
853 to1 :: (Rep1 f) a -> f a
854
855 --------------------------------------------------------------------------------
856 -- Meta-data
857 --------------------------------------------------------------------------------
858
859 -- | Datatype to represent metadata associated with a datatype (@MetaData@),
860 -- constructor (@MetaCons@), or field (@MetaSel@ and @MetaNoSel@).
861 --
862 -- * In @MetaData n m p nt@, @n@ is the datatype's name, @m@ is the module in
863 -- which the datatype is defined, @p@ is the package in which the datatype
864 -- is defined, and @nt@ is @'True@ if the datatype is a @newtype@.
865 --
866 -- * In @MetaCons n f s@, @n@ is the constructor's name, @f@ is its fixity,
867 -- and @s@ is @'True@ if the constructor contains record selectors.
868 --
869 -- * Fields with record selectors are tagged with @MetaSel s@, where @s@ is
870 -- the record selector name.
871 --
872 -- * Fields without record selectors are tagged with @MetaNoSel@.
873 data Meta = MetaData Symbol Symbol Symbol Bool
874 | MetaCons Symbol FixityI Bool
875 | MetaSel Symbol
876 | MetaNoSel
877
878 --------------------------------------------------------------------------------
879 -- Derived instances
880 --------------------------------------------------------------------------------
881
882 deriving instance Generic [a]
883 deriving instance Generic (Maybe a)
884 deriving instance Generic (Either a b)
885 deriving instance Generic Bool
886 deriving instance Generic Ordering
887 deriving instance Generic (Proxy t)
888 deriving instance Generic ()
889 deriving instance Generic ((,) a b)
890 deriving instance Generic ((,,) a b c)
891 deriving instance Generic ((,,,) a b c d)
892 deriving instance Generic ((,,,,) a b c d e)
893 deriving instance Generic ((,,,,,) a b c d e f)
894 deriving instance Generic ((,,,,,,) a b c d e f g)
895
896 deriving instance Generic1 []
897 deriving instance Generic1 Maybe
898 deriving instance Generic1 (Either a)
899 deriving instance Generic1 Proxy
900 deriving instance Generic1 ((,) a)
901 deriving instance Generic1 ((,,) a b)
902 deriving instance Generic1 ((,,,) a b c)
903 deriving instance Generic1 ((,,,,) a b c d)
904 deriving instance Generic1 ((,,,,,) a b c d e)
905 deriving instance Generic1 ((,,,,,,) a b c d e f)
906
907 --------------------------------------------------------------------------------
908 -- Copied from the singletons package
909 --------------------------------------------------------------------------------
910
911 -- | The singleton kind-indexed data family.
912 data family Sing (a :: k)
913
914 -- | A 'SingI' constraint is essentially an implicitly-passed singleton.
915 -- If you need to satisfy this constraint with an explicit singleton, please
916 -- see 'withSingI'.
917 class SingI (a :: k) where
918 -- | Produce the singleton explicitly. You will likely need the @ScopedTypeVariables@
919 -- extension to use this method the way you want.
920 sing :: Sing a
921
922 -- | The 'SingKind' class is essentially a /kind/ class. It classifies all kinds
923 -- for which singletons are defined. The class supports converting between a singleton
924 -- type and the base (unrefined) type which it is built from.
925 class (kparam ~ 'KProxy) => SingKind (kparam :: KProxy k) where
926 -- | Get a base type from a proxy for the promoted kind. For example,
927 -- @DemoteRep ('KProxy :: KProxy Bool)@ will be the type @Bool@.
928 type DemoteRep kparam :: *
929
930 -- | Convert a singleton to its unrefined version.
931 fromSing :: Sing (a :: k) -> DemoteRep kparam
932
933 -- Singleton booleans
934 data instance Sing (_a :: Bool) where
935 STrue :: Sing 'True
936 SFalse :: Sing 'False
937
938 instance SingI 'True where sing = STrue
939 instance SingI 'False where sing = SFalse
940
941 instance SingKind ('KProxy :: KProxy Bool) where
942 type DemoteRep ('KProxy :: KProxy Bool) = Bool
943 fromSing STrue = True
944 fromSing SFalse = False
945
946 -- Singleton Fixity
947 data instance Sing (_a :: FixityI) where
948 SPrefix :: Sing 'PrefixI
949 SInfix :: Sing a -> Integer -> Sing ('InfixI a n)
950
951 instance SingI 'PrefixI where sing = SPrefix
952 instance (SingI a, KnownNat n) => SingI ('InfixI a n) where
953 sing = SInfix (sing :: Sing a) (natVal (Proxy :: Proxy n))
954
955 instance SingKind ('KProxy :: KProxy FixityI) where
956 type DemoteRep ('KProxy :: KProxy FixityI) = Fixity
957 fromSing SPrefix = Prefix
958 fromSing (SInfix a n) = Infix (fromSing a) (I# (integerToInt n))
959
960 -- Singleton Associativity
961 data instance Sing (_a :: Associativity) where
962 SLeftAssociative :: Sing 'LeftAssociative
963 SRightAssociative :: Sing 'RightAssociative
964 SNotAssociative :: Sing 'NotAssociative
965
966 instance SingI 'LeftAssociative where sing = SLeftAssociative
967 instance SingI 'RightAssociative where sing = SRightAssociative
968 instance SingI 'NotAssociative where sing = SNotAssociative
969
970 instance SingKind ('KProxy :: KProxy Associativity) where
971 type DemoteRep ('KProxy :: KProxy Associativity) = Associativity
972 fromSing SLeftAssociative = LeftAssociative
973 fromSing SRightAssociative = RightAssociative
974 fromSing SNotAssociative = NotAssociative