COMPLETE pragmas for enhanced pattern exhaustiveness checking
[ghc.git] / docs / users_guide / glasgow_exts.rst
1 .. index::
2    single: language, GHC extensions
3
4 As with all known Haskell systems, GHC implements some extensions to the
5 standard Haskell language. They can all be enabled or disabled by command line
6 flags or language pragmas. By default GHC understands the most recent Haskell
7 version it supports, plus a handful of extensions.
8
9 Some of the Glasgow extensions serve to give you access to the
10 underlying facilities with which we implement Haskell. Thus, you can get
11 at the Raw Iron, if you are willing to write some non-portable code at a
12 more primitive level. You need not be “stuck” on performance because of
13 the implementation costs of Haskell's "high-level" features—you can
14 always code "under" them. In an extreme case, you can write all your
15 time-critical code in C, and then just glue it together with Haskell!
16
17 Before you get too carried away working at the lowest level (e.g.,
18 sloshing ``MutableByteArray#``\ s around your program), you may wish to
19 check if there are libraries that provide a "Haskellised veneer" over
20 the features you want. The separate
21 `libraries documentation <../libraries/index.html>`__ describes all the
22 libraries that come with GHC.
23
24 .. _options-language:
25
26 Language options
27 ================
28
29 .. index::
30    single: language; option
31    single: options; language
32    single: extensions; options controlling
33
34 The language option flags control what variation of the language are
35 permitted.
36
37 Language options can be controlled in two ways:
38
39 -  Every language option can switched on by a command-line flag
40    "``-X...``" (e.g. ``-XTemplateHaskell``), and switched off by the
41    flag "``-XNo...``"; (e.g. ``-XNoTemplateHaskell``).
42
43 -  Language options recognised by Cabal can also be enabled using the
44    ``LANGUAGE`` pragma, thus ``{-# LANGUAGE TemplateHaskell #-}`` (see
45    :ref:`language-pragma`).
46
47
48 Although not recommended, the deprecated :ghc-flag:`-fglasgow-exts` flag enables
49 a large swath of the extensions supported by GHC at once.
50
51 .. ghc-flag:: -fglasgow-exts
52
53     The flag ``-fglasgow-exts`` is equivalent to enabling the following extensions:
54
55     .. include:: what_glasgow_exts_does.gen.rst
56
57     Enabling these options is the *only* effect of ``-fglasgow-exts``. We are trying
58     to move away from this portmanteau flag, and towards enabling features
59     individually.
60
61 .. _primitives:
62
63 Unboxed types and primitive operations
64 ======================================
65
66 GHC is built on a raft of primitive data types and operations;
67 "primitive" in the sense that they cannot be defined in Haskell itself.
68 While you really can use this stuff to write fast code, we generally
69 find it a lot less painful, and more satisfying in the long run, to use
70 higher-level language features and libraries. With any luck, the code
71 you write will be optimised to the efficient unboxed version in any
72 case. And if it isn't, we'd like to know about it.
73
74 All these primitive data types and operations are exported by the
75 library ``GHC.Prim``, for which there is
76 :ghc-prim-ref:`detailed online documentation <GHC-Prim.html>`. (This
77 documentation is generated from the file ``compiler/prelude/primops.txt.pp``.)
78
79 If you want to mention any of the primitive data types or operations in
80 your program, you must first import ``GHC.Prim`` to bring them into
81 scope. Many of them have names ending in ``#``, and to mention such names
82 you need the :ghc-flag:`-XMagicHash` extension (:ref:`magic-hash`).
83
84 The primops make extensive use of `unboxed types <#glasgow-unboxed>`__
85 and `unboxed tuples <#unboxed-tuples>`__, which we briefly summarise
86 here.
87
88 .. _glasgow-unboxed:
89
90 Unboxed types
91 -------------
92
93 Most types in GHC are boxed, which means that values of that type are
94 represented by a pointer to a heap object. The representation of a
95 Haskell ``Int``, for example, is a two-word heap object. An unboxed
96 type, however, is represented by the value itself, no pointers or heap
97 allocation are involved.
98
99 Unboxed types correspond to the “raw machine” types you would use in C:
100 ``Int#`` (long int), ``Double#`` (double), ``Addr#`` (void \*), etc. The
101 *primitive operations* (PrimOps) on these types are what you might
102 expect; e.g., ``(+#)`` is addition on ``Int#``\ s, and is the
103 machine-addition that we all know and love—usually one instruction.
104
105 Primitive (unboxed) types cannot be defined in Haskell, and are
106 therefore built into the language and compiler. Primitive types are
107 always unlifted; that is, a value of a primitive type cannot be bottom.
108 (Note: a "boxed" type means that a value is represented by a pointer to a heap
109 object; a "lifted" type means that terms of that type may be bottom. See
110 the next paragraph for an example.)
111 We use the convention (but it is only a convention) that primitive
112 types, values, and operations have a ``#`` suffix (see
113 :ref:`magic-hash`). For some primitive types we have special syntax for
114 literals, also described in the `same section <#magic-hash>`__.
115
116 Primitive values are often represented by a simple bit-pattern, such as
117 ``Int#``, ``Float#``, ``Double#``. But this is not necessarily the case:
118 a primitive value might be represented by a pointer to a heap-allocated
119 object. Examples include ``Array#``, the type of primitive arrays. Thus,
120 ``Array#`` is an unlifted, boxed type. A
121 primitive array is heap-allocated because it is too big a value to fit
122 in a register, and would be too expensive to copy around; in a sense, it
123 is accidental that it is represented by a pointer. If a pointer
124 represents a primitive value, then it really does point to that value:
125 no unevaluated thunks, no indirections. Nothing can be at the other end
126 of the pointer than the primitive value. A numerically-intensive program
127 using unboxed types can go a *lot* faster than its “standard”
128 counterpart—we saw a threefold speedup on one example.
129
130 Unboxed type kinds
131 ------------------
132
133 Because unboxed types are represented without the use of pointers, we
134 cannot store them in use a polymorphic datatype at an unboxed type.
135 For example, the ``Just`` node
136 of ``Just 42#`` would have to be different from the ``Just`` node of
137 ``Just 42``; the former stores an integer directly, while the latter
138 stores a pointer. GHC currently does not support this variety of ``Just``
139 nodes (nor for any other datatype). Accordingly, the *kind* of an unboxed
140 type is different from the kind of a boxed type.
141
142 The Haskell Report describes that ``*`` is the kind of ordinary datatypes,
143 such as ``Int``. Furthermore, type constructors can have kinds with arrows;
144 for example, ``Maybe`` has kind ``* -> *``. Unboxed types have a kind that
145 specifies their runtime representation. For example, the type ``Int#`` has
146 kind ``TYPE 'IntRep`` and ``Double#`` has kind ``TYPE 'DoubleRep``. These
147 kinds say that the runtime representation of an ``Int#`` is a machine integer,
148 and the runtime representation of a ``Double#`` is a machine double-precision
149 floating point. In constrast, the kind ``*`` is actually just a synonym
150 for ``TYPE 'PtrRepLifted``. More details of the ``TYPE`` mechanisms appear in
151 the `section on runtime representation polymorphism <#runtime-rep>`__.
152
153 Given that ``Int#``'s kind is not ``*``, it then it follows that
154 ``Maybe Int#`` is disallowed. Similarly, because type variables tend
155 to be of kind ``*`` (for example, in ``(.) :: (b -> c) -> (a -> b) -> a -> c``,
156 all the type variables have kind ``*``), polymorphism tends not to work
157 over primitive types. Stepping back, this makes some sense, because
158 a polymorphic function needs to manipulate the pointers to its data,
159 and most primitive types are unboxed.
160
161 There are some restrictions on the use of primitive types:
162
163 -  You cannot define a newtype whose representation type (the argument
164    type of the data constructor) is an unboxed type. Thus, this is
165    illegal:
166
167    ::
168
169          newtype A = MkA Int#
170
171 -  You cannot bind a variable with an unboxed type in a *top-level*
172    binding.
173
174 -  You cannot bind a variable with an unboxed type in a *recursive*
175    binding.
176
177 -  You may bind unboxed variables in a (non-recursive, non-top-level)
178    pattern binding, but you must make any such pattern-match strict.
179    (Failing to do so emits a warning :ghc-flag:`-Wunbanged-strict-patterns`.)
180    For example, rather than:
181
182    ::
183
184          data Foo = Foo Int Int#
185
186          f x = let (Foo a b, w) = ..rhs.. in ..body..
187
188    you must write:
189
190    ::
191
192          data Foo = Foo Int Int#
193
194          f x = let !(Foo a b, w) = ..rhs.. in ..body..
195
196    since ``b`` has type ``Int#``.
197
198 .. _unboxed-tuples:
199
200 Unboxed tuples
201 --------------
202
203 .. ghc-flag:: -XUnboxedTuples
204
205     Enable the use of unboxed tuple syntax.
206
207 Unboxed tuples aren't really exported by ``GHC.Exts``; they are a
208 syntactic extension enabled by the language flag :ghc-flag:`-XUnboxedTuples`. An
209 unboxed tuple looks like this: ::
210
211     (# e_1, ..., e_n #)
212
213 where ``e_1..e_n`` are expressions of any type (primitive or
214 non-primitive). The type of an unboxed tuple looks the same.
215
216 Note that when unboxed tuples are enabled, ``(#`` is a single lexeme, so
217 for example when using operators like ``#`` and ``#-`` you need to write
218 ``( # )`` and ``( #- )`` rather than ``(#)`` and ``(#-)``.
219
220 Unboxed tuples are used for functions that need to return multiple
221 values, but they avoid the heap allocation normally associated with
222 using fully-fledged tuples. When an unboxed tuple is returned, the
223 components are put directly into registers or on the stack; the unboxed
224 tuple itself does not have a composite representation. Many of the
225 primitive operations listed in ``primops.txt.pp`` return unboxed tuples.
226 In particular, the ``IO`` and ``ST`` monads use unboxed tuples to avoid
227 unnecessary allocation during sequences of operations.
228
229 There are some restrictions on the use of unboxed tuples:
230
231 -  The typical use of unboxed tuples is simply to return multiple
232    values, binding those multiple results with a ``case`` expression,
233    thus:
234
235    ::
236
237          f x y = (# x+1, y-1 #)
238          g x = case f x x of { (# a, b #) -> a + b }
239
240    You can have an unboxed tuple in a pattern binding, thus
241
242    ::
243
244          f x = let (# p,q #) = h x in ..body..
245
246    If the types of ``p`` and ``q`` are not unboxed, the resulting
247    binding is lazy like any other Haskell pattern binding. The above
248    example desugars like this:
249
250    ::
251
252          f x = let t = case h x of { (# p,q #) -> (p,q) }
253                    p = fst t
254                    q = snd t
255                in ..body..
256
257    Indeed, the bindings can even be recursive.
258
259 .. _unboxed-sums:
260
261 Unboxed sums
262 ------------
263
264 .. ghc-flag:: -XUnboxedSums
265
266     Enable the use of unboxed sum syntax.
267
268 `-XUnboxedSums` enables new syntax for anonymous, unboxed sum types. The syntax
269 for an unboxed sum type with N alternatives is ::
270
271     (# t_1 | t_2 | ... | t_N #)
272
273 where `t_1` ... `t_N` are types (which can be unlifted, including unboxed tuple
274 and sums).
275
276 Unboxed tuples can be used for multi-arity alternatives. For example: ::
277
278     (# (# Int, String #) | Bool #)
279
280 Term level syntax is similar. Leading and preceding bars (`|`) indicate which
281 alternative it is. Here is two terms of the type shown above: ::
282
283     (# (# 1, "foo" #) | #) -- first alternative
284
285     (# | True #) -- second alternative
286
287 Pattern syntax reflects the term syntax: ::
288
289     case x of
290       (# (# i, str #) | #) -> ...
291       (# | bool #) -> ...
292
293 Unboxed sums are "unboxed" in the sense that, instead of allocating sums in the
294 heap and representing values as pointers, unboxed sums are represented as their
295 components, just like unboxed tuples. These "components" depend on alternatives
296 of a sum type. Code generator tries to generate as compact layout as possible.
297 In the best case, size of an unboxed sum is size of its biggest alternative +
298 one word (for tag). The algorithm for generating memory layout for a sum type
299 works like this:
300
301 - All types are classified as one of these classes: 32bit word, 64bit word,
302   32bit float, 64bit float, pointer.
303
304 - For each alternative of the sum type, a layout that consists of these fields
305   is generated. For example, if an alternative has `Int`, `Float#` and `String`
306   fields, the layout will have an 32bit word, 32bit float and pointer fields.
307
308 - Layout fields are then overlapped so that the final layout will be as compact
309   as possible. E.g. say two alternatives have these fields: ::
310
311     Word32, String, Float#
312     Float#, Float#, Maybe Int
313
314   Final layout will be something like ::
315
316     Int32, Float32, Float32, Word32, Pointer
317
318   First `Int32` is for the tag. It has two `Float32` fields because floating
319   point types can't overlap with other types, because of limitations of the code
320   generator that we're hoping to overcome in the future, and second alternative
321   needs two `Float32` fields. `Word32` field is for the `Word32` in the first
322   alternative. `Pointer` field is shared between `String` and `Maybe Int` values
323   of the alternatives.
324
325   In the case of enumeration types (like `Bool`), the unboxed sum layout only
326   has an `Int32` field (i.e. the whole thing is represented by an integer).
327
328 In the example above, a value of this type is thus represented as 5 values. As
329 an another example, this is the layout for unboxed version of `Maybe a` type: ::
330
331     Int32, Pointer
332
333 The `Pointer` field is not used when tag says that it's `Nothing`. Otherwise
334 `Pointer` points to the value in `Just`.
335
336 .. _syntax-extns:
337
338 Syntactic extensions
339 ====================
340
341 .. _unicode-syntax:
342
343 Unicode syntax
344 --------------
345
346 .. ghc-flag:: -XUnicodeSyntax
347
348     Enable the use of Unicode characters in place of their equivalent ASCII
349     sequences.
350
351 The language extension :ghc-flag:`-XUnicodeSyntax` enables
352 Unicode characters to be used to stand for certain ASCII character
353 sequences. The following alternatives are provided:
354
355 +--------------+---------------+-------------+-----------------------------------------+
356 | ASCII        | Unicode       | Code point  | Name                                    |
357 |              | alternative   |             |                                         |
358 +==============+===============+=============+=========================================+
359 | ``::``       | ∷             | 0x2237      | PROPORTION                              |
360 +--------------+---------------+-------------+-----------------------------------------+
361 | ``=>``       | ⇒             | 0x21D2      | RIGHTWARDS DOUBLE ARROW                 |
362 +--------------+---------------+-------------+-----------------------------------------+
363 | ``->``       | →             | 0x2192      | RIGHTWARDS ARROW                        |
364 +--------------+---------------+-------------+-----------------------------------------+
365 | ``<-``       | ←             | 0x2190      | LEFTWARDS ARROW                         |
366 +--------------+---------------+-------------+-----------------------------------------+
367 | ``>-``       | ⤚             | 0x291a      | RIGHTWARDS ARROW-TAIL                   |
368 +--------------+---------------+-------------+-----------------------------------------+
369 | ``-<``       | ⤙             | 0x2919      | LEFTWARDS ARROW-TAIL                    |
370 +--------------+---------------+-------------+-----------------------------------------+
371 | ``>>-``      | ⤜             | 0x291C      | RIGHTWARDS DOUBLE ARROW-TAIL            |
372 +--------------+---------------+-------------+-----------------------------------------+
373 | ``-<<``      | ⤛             | 0x291B      | LEFTWARDS DOUBLE ARROW-TAIL             |
374 +--------------+---------------+-------------+-----------------------------------------+
375 | ``*``        | ★             | 0x2605      | BLACK STAR                              |
376 +--------------+---------------+-------------+-----------------------------------------+
377 | ``forall``   | ∀             | 0x2200      | FOR ALL                                 |
378 +--------------+---------------+-------------+-----------------------------------------+
379 | ``(|``       | ⦇             | 0x2987      | Z NOTATION LEFT IMAGE BRACKET           |
380 +--------------+---------------+-------------+-----------------------------------------+
381 | ``|)``       | ⦈             | 0x2988      | Z NOTATION RIGHT IMAGE BRACKET          |
382 +--------------+---------------+-------------+-----------------------------------------+
383 | ``[|``       | ⟦             | 0x27E6      | MATHEMATICAL LEFT WHITE SQUARE BRACKET  |
384 +--------------+---------------+-------------+-----------------------------------------+
385 | ``|]``       | ⟧             | 0x27E7      | MATHEMATICAL RIGHT WHITE SQUARE BRACKET |
386 +--------------+---------------+-------------+-----------------------------------------+
387
388 .. _magic-hash:
389
390 The magic hash
391 --------------
392
393 .. ghc-flag:: -XMagicHash
394
395     Enable the use of the hash character (``#``) as an identifier suffix.
396
397 The language extension :ghc-flag:`-XMagicHash` allows ``#`` as a postfix modifier
398 to identifiers. Thus, ``x#`` is a valid variable, and ``T#`` is a valid type
399 constructor or data constructor.
400
401 The hash sign does not change semantics at all. We tend to use variable
402 names ending in "#" for unboxed values or types (e.g. ``Int#``), but
403 there is no requirement to do so; they are just plain ordinary
404 variables. Nor does the :ghc-flag:`-XMagicHash` extension bring anything into
405 scope. For example, to bring ``Int#`` into scope you must import
406 ``GHC.Prim`` (see :ref:`primitives`); the :ghc-flag:`-XMagicHash` extension then
407 allows you to *refer* to the ``Int#`` that is now in scope. Note that
408 with this option, the meaning of ``x#y = 0`` is changed: it defines a
409 function ``x#`` taking a single argument ``y``; to define the operator
410 ``#``, put a space: ``x # y = 0``.
411
412 The :ghc-flag:`-XMagicHash` also enables some new forms of literals (see
413 :ref:`glasgow-unboxed`):
414
415 -  ``'x'#`` has type ``Char#``
416
417 -  ``"foo"#`` has type ``Addr#``
418
419 -  ``3#`` has type ``Int#``. In general, any Haskell integer lexeme
420    followed by a ``#`` is an ``Int#`` literal, e.g. ``-0x3A#`` as well as
421    ``32#``.
422
423 -  ``3##`` has type ``Word#``. In general, any non-negative Haskell
424    integer lexeme followed by ``##`` is a ``Word#``.
425
426 -  ``3.2#`` has type ``Float#``.
427
428 -  ``3.2##`` has type ``Double#``
429
430 .. _negative-literals:
431
432 Negative literals
433 -----------------
434
435 .. ghc-flag:: -XNegativeLiterals
436
437     :since: 7.8.1
438
439     Enable the use of un-parenthesized negative numeric literals.
440
441 The literal ``-123`` is, according to Haskell98 and Haskell 2010,
442 desugared as ``negate (fromInteger 123)``. The language extension
443 :ghc-flag:`-XNegativeLiterals` means that it is instead desugared as
444 ``fromInteger (-123)``.
445
446 This can make a difference when the positive and negative range of a
447 numeric data type don't match up. For example, in 8-bit arithmetic -128
448 is representable, but +128 is not. So ``negate (fromInteger 128)`` will
449 elicit an unexpected integer-literal-overflow message.
450
451 .. _num-decimals:
452
453 Fractional looking integer literals
454 -----------------------------------
455
456 .. ghc-flag:: -XNumDecimals
457
458     :since: 7.8.1
459
460     Allow the use of floating-point literal syntax for integral types.
461
462 Haskell 2010 and Haskell 98 define floating literals with the syntax
463 ``1.2e6``. These literals have the type ``Fractional a => a``.
464
465 The language extension :ghc-flag:`-XNumDecimals` allows you to also use the
466 floating literal syntax for instances of ``Integral``, and have values
467 like ``(1.2e6 :: Num a => a)``
468
469 .. _binary-literals:
470
471 Binary integer literals
472 -----------------------
473
474 .. ghc-flag:: -XBinaryLiterals
475
476     :since: 7.10.1
477
478     Allow the use of binary notation in integer literals.
479
480 Haskell 2010 and Haskell 98 allows for integer literals to be given in
481 decimal, octal (prefixed by ``0o`` or ``0O``), or hexadecimal notation
482 (prefixed by ``0x`` or ``0X``).
483
484 The language extension :ghc-flag:`-XBinaryLiterals` adds support for expressing
485 integer literals in binary notation with the prefix ``0b`` or ``0B``. For
486 instance, the binary integer literal ``0b11001001`` will be desugared into
487 ``fromInteger 201`` when :ghc-flag:`-XBinaryLiterals` is enabled.
488
489 .. _pattern-guards:
490
491 Pattern guards
492 --------------
493
494 .. ghc-flag:: -XNoPatternGuards
495
496     :implied by: :ghc-flag:`-XHaskell98`
497     :since: 6.8.1
498
499 Disable `pattern guards
500 <http://www.haskell.org/onlinereport/haskell2010/haskellch3.html#x8-460003.13>`__.
501
502 .. _view-patterns:
503
504 View patterns
505 -------------
506
507 .. ghc-flag:: -XViewPatterns
508
509     Allow use of view pattern syntax.
510
511 View patterns are enabled by the flag :ghc-flag:`-XViewPatterns`. More
512 information and examples of view patterns can be found on the
513 :ghc-wiki:`Wiki page <ViewPatterns>`.
514
515 View patterns are somewhat like pattern guards that can be nested inside
516 of other patterns. They are a convenient way of pattern-matching against
517 values of abstract types. For example, in a programming language
518 implementation, we might represent the syntax of the types of the
519 language as follows: ::
520
521     type Typ
522
523     data TypView = Unit
524                  | Arrow Typ Typ
525
526     view :: Typ -> TypView
527
528     -- additional operations for constructing Typ's ...
529
530 The representation of Typ is held abstract, permitting implementations
531 to use a fancy representation (e.g., hash-consing to manage sharing).
532 Without view patterns, using this signature is a little inconvenient: ::
533
534     size :: Typ -> Integer
535     size t = case view t of
536       Unit -> 1
537       Arrow t1 t2 -> size t1 + size t2
538
539 It is necessary to iterate the case, rather than using an equational
540 function definition. And the situation is even worse when the matching
541 against ``t`` is buried deep inside another pattern.
542
543 View patterns permit calling the view function inside the pattern and
544 matching against the result: ::
545
546     size (view -> Unit) = 1
547     size (view -> Arrow t1 t2) = size t1 + size t2
548
549 That is, we add a new form of pattern, written ⟨expression⟩ ``->``
550 ⟨pattern⟩ that means "apply the expression to whatever we're trying to
551 match against, and then match the result of that application against the
552 pattern". The expression can be any Haskell expression of function type,
553 and view patterns can be used wherever patterns are used.
554
555 The semantics of a pattern ``(`` ⟨exp⟩ ``->`` ⟨pat⟩ ``)`` are as
556 follows:
557
558 -  Scoping:
559    The variables bound by the view pattern are the variables bound by
560    ⟨pat⟩.
561
562    Any variables in ⟨exp⟩ are bound occurrences, but variables bound "to
563    the left" in a pattern are in scope. This feature permits, for
564    example, one argument to a function to be used in the view of another
565    argument. For example, the function ``clunky`` from
566    :ref:`pattern-guards` can be written using view patterns as follows: ::
567
568        clunky env (lookup env -> Just val1) (lookup env -> Just val2) = val1 + val2
569        ...other equations for clunky...
570
571    More precisely, the scoping rules are:
572
573    -  In a single pattern, variables bound by patterns to the left of a
574       view pattern expression are in scope. For example: ::
575
576           example :: Maybe ((String -> Integer,Integer), String) -> Bool
577           example Just ((f,_), f -> 4) = True
578
579       Additionally, in function definitions, variables bound by matching
580       earlier curried arguments may be used in view pattern expressions
581       in later arguments: ::
582
583           example :: (String -> Integer) -> String -> Bool
584           example f (f -> 4) = True
585
586       That is, the scoping is the same as it would be if the curried
587       arguments were collected into a tuple.
588
589    -  In mutually recursive bindings, such as ``let``, ``where``, or the
590       top level, view patterns in one declaration may not mention
591       variables bound by other declarations. That is, each declaration
592       must be self-contained. For example, the following program is not
593       allowed: ::
594
595           let {(x -> y) = e1 ;
596                (y -> x) = e2 } in x
597
598    (For some amplification on this design choice see :ghc-ticket:`4061`.
599
600 -  Typing: If ⟨exp⟩ has type ⟨T1⟩ ``->`` ⟨T2⟩ and ⟨pat⟩ matches a ⟨T2⟩,
601    then the whole view pattern matches a ⟨T1⟩.
602
603 -  Matching: To the equations in Section 3.17.3 of the `Haskell 98
604    Report <http://www.haskell.org/onlinereport/>`__, add the following: ::
605
606        case v of { (e -> p) -> e1 ; _ -> e2 }
607         =
608        case (e v) of { p -> e1 ; _ -> e2 }
609
610    That is, to match a variable ⟨v⟩ against a pattern ``(`` ⟨exp⟩ ``->``
611    ⟨pat⟩ ``)``, evaluate ``(`` ⟨exp⟩ ⟨v⟩ ``)`` and match the result
612    against ⟨pat⟩.
613
614 -  Efficiency: When the same view function is applied in multiple
615    branches of a function definition or a case expression (e.g., in
616    ``size`` above), GHC makes an attempt to collect these applications
617    into a single nested case expression, so that the view function is
618    only applied once. Pattern compilation in GHC follows the matrix
619    algorithm described in Chapter 4 of `The Implementation of Functional
620    Programming
621    Languages <http://research.microsoft.com/~simonpj/Papers/slpj-book-1987/>`__.
622    When the top rows of the first column of a matrix are all view
623    patterns with the "same" expression, these patterns are transformed
624    into a single nested case. This includes, for example, adjacent view
625    patterns that line up in a tuple, as in
626
627    ::
628
629        f ((view -> A, p1), p2) = e1
630        f ((view -> B, p3), p4) = e2
631
632    The current notion of when two view pattern expressions are "the
633    same" is very restricted: it is not even full syntactic equality.
634    However, it does include variables, literals, applications, and
635    tuples; e.g., two instances of ``view ("hi", "there")`` will be
636    collected. However, the current implementation does not compare up to
637    alpha-equivalence, so two instances of ``(x, view x -> y)`` will not
638    be coalesced.
639
640 .. _n-k-patterns:
641
642 n+k patterns
643 ------------
644
645 .. ghc-flag:: -XNPlusKPatterns
646
647     :implied by: :ghc-flag:`-XHaskell98`
648     :since: 6.12
649
650     Enable use of ``n+k`` patterns.
651
652 .. _recursive-do-notation:
653
654 The recursive do-notation
655 -------------------------
656
657 .. ghc-flag:: -XRecursiveDo
658
659     Allow the use of recursive ``do`` notation.
660
661 The do-notation of Haskell 98 does not allow *recursive bindings*, that
662 is, the variables bound in a do-expression are visible only in the
663 textually following code block. Compare this to a let-expression, where
664 bound variables are visible in the entire binding group.
665
666 It turns out that such recursive bindings do indeed make sense for a
667 variety of monads, but not all. In particular, recursion in this sense
668 requires a fixed-point operator for the underlying monad, captured by
669 the ``mfix`` method of the ``MonadFix`` class, defined in
670 ``Control.Monad.Fix`` as follows: ::
671
672     class Monad m => MonadFix m where
673        mfix :: (a -> m a) -> m a
674
675 Haskell's ``Maybe``, ``[]`` (list), ``ST`` (both strict and lazy
676 versions), ``IO``, and many other monads have ``MonadFix`` instances. On
677 the negative side, the continuation monad, with the signature
678 ``(a -> r) -> r``, does not.
679
680 For monads that do belong to the ``MonadFix`` class, GHC provides an
681 extended version of the do-notation that allows recursive bindings. The
682 :ghc-flag:`-XRecursiveDo` (language pragma: ``RecursiveDo``) provides the
683 necessary syntactic support, introducing the keywords ``mdo`` and
684 ``rec`` for higher and lower levels of the notation respectively. Unlike
685 bindings in a ``do`` expression, those introduced by ``mdo`` and ``rec``
686 are recursively defined, much like in an ordinary let-expression. Due to
687 the new keyword ``mdo``, we also call this notation the *mdo-notation*.
688
689 Here is a simple (albeit contrived) example:
690
691 ::
692
693     {-# LANGUAGE RecursiveDo #-}
694     justOnes = mdo { xs <- Just (1:xs)
695                    ; return (map negate xs) }
696
697 or equivalently
698
699 ::
700
701     {-# LANGUAGE RecursiveDo #-}
702     justOnes = do { rec { xs <- Just (1:xs) }
703                   ; return (map negate xs) }
704
705 As you can guess ``justOnes`` will evaluate to ``Just [-1,-1,-1,...``.
706
707 GHC's implementation the mdo-notation closely follows the original
708 translation as described in the paper `A recursive do for
709 Haskell <http://leventerkok.github.io/papers/recdo.pdf>`__, which
710 in turn is based on the work `Value Recursion in Monadic
711 Computations <http://leventerkok.github.io/papers/erkok-thesis.pdf>`__.
712 Furthermore, GHC extends the syntax described in the former paper with a
713 lower level syntax flagged by the ``rec`` keyword, as we describe next.
714
715 Recursive binding groups
716 ~~~~~~~~~~~~~~~~~~~~~~~~
717
718 The flag :ghc-flag:`-XRecursiveDo` also introduces a new keyword ``rec``, which
719 wraps a mutually-recursive group of monadic statements inside a ``do``
720 expression, producing a single statement. Similar to a ``let`` statement
721 inside a ``do``, variables bound in the ``rec`` are visible throughout
722 the ``rec`` group, and below it. For example, compare
723
724 ::
725
726         do { a <- getChar            do { a <- getChar
727            ; let { r1 = f a r2          ; rec { r1 <- f a r2
728            ;     ; r2 = g r1 }          ;     ; r2 <- g r1 }
729            ; return (r1 ++ r2) }        ; return (r1 ++ r2) }
730
731 In both cases, ``r1`` and ``r2`` are available both throughout the
732 ``let`` or ``rec`` block, and in the statements that follow it. The
733 difference is that ``let`` is non-monadic, while ``rec`` is monadic. (In
734 Haskell ``let`` is really ``letrec``, of course.)
735
736 The semantics of ``rec`` is fairly straightforward. Whenever GHC finds a
737 ``rec`` group, it will compute its set of bound variables, and will
738 introduce an appropriate call to the underlying monadic value-recursion
739 operator ``mfix``, belonging to the ``MonadFix`` class. Here is an
740 example:
741
742 ::
743
744     rec { b <- f a c     ===>    (b,c) <- mfix (\ ~(b,c) -> do { b <- f a c
745         ; c <- f b a }                                         ; c <- f b a
746                                                                ; return (b,c) })
747
748 As usual, the meta-variables ``b``, ``c`` etc., can be arbitrary
749 patterns. In general, the statement ``rec ss`` is desugared to the
750 statement
751
752 ::
753
754     vs <- mfix (\ ~vs -> do { ss; return vs })
755
756 where ``vs`` is a tuple of the variables bound by ``ss``.
757
758 Note in particular that the translation for a ``rec`` block only
759 involves wrapping a call to ``mfix``: it performs no other analysis on
760 the bindings. The latter is the task for the ``mdo`` notation, which is
761 described next.
762
763 The ``mdo`` notation
764 ~~~~~~~~~~~~~~~~~~~~
765
766 A ``rec``-block tells the compiler where precisely the recursive knot
767 should be tied. It turns out that the placement of the recursive knots
768 can be rather delicate: in particular, we would like the knots to be
769 wrapped around as minimal groups as possible. This process is known as
770 *segmentation*, and is described in detail in Section 3.2 of `A
771 recursive do for
772 Haskell <http://leventerkok.github.io/papers/recdo.pdf>`__.
773 Segmentation improves polymorphism and reduces the size of the recursive
774 knot. Most importantly, it avoids unnecessary interference caused by a
775 fundamental issue with the so-called *right-shrinking* axiom for monadic
776 recursion. In brief, most monads of interest (IO, strict state, etc.) do
777 *not* have recursion operators that satisfy this axiom, and thus not
778 performing segmentation can cause unnecessary interference, changing the
779 termination behavior of the resulting translation. (Details can be found
780 in Sections 3.1 and 7.2.2 of `Value Recursion in Monadic
781 Computations <http://leventerkok.github.io/papers/erkok-thesis.pdf>`__.)
782
783 The ``mdo`` notation removes the burden of placing explicit ``rec``
784 blocks in the code. Unlike an ordinary ``do`` expression, in which
785 variables bound by statements are only in scope for later statements,
786 variables bound in an ``mdo`` expression are in scope for all statements
787 of the expression. The compiler then automatically identifies minimal
788 mutually recursively dependent segments of statements, treating them as
789 if the user had wrapped a ``rec`` qualifier around them.
790
791 The definition is syntactic:
792
793 -  A generator ⟨g⟩ *depends* on a textually following generator ⟨g'⟩, if
794
795    -  ⟨g'⟩ defines a variable that is used by ⟨g⟩, or
796
797    -  ⟨g'⟩ textually appears between ⟨g⟩ and ⟨g''⟩, where ⟨g⟩ depends on
798       ⟨g''⟩.
799
800 -  A *segment* of a given ``mdo``-expression is a minimal sequence of
801    generators such that no generator of the sequence depends on an
802    outside generator. As a special case, although it is not a generator,
803    the final expression in an ``mdo``-expression is considered to form a
804    segment by itself.
805
806 Segments in this sense are related to *strongly-connected components*
807 analysis, with the exception that bindings in a segment cannot be
808 reordered and must be contiguous.
809
810 Here is an example ``mdo``-expression, and its translation to ``rec``
811 blocks:
812
813 ::
814
815     mdo { a <- getChar      ===> do { a <- getChar
816         ; b <- f a c                ; rec { b <- f a c
817         ; c <- f b a                ;     ; c <- f b a }
818         ; z <- h a b                ; z <- h a b
819         ; d <- g d e                ; rec { d <- g d e
820         ; e <- g a z                ;     ; e <- g a z }
821         ; putChar c }               ; putChar c }
822
823 Note that a given ``mdo`` expression can cause the creation of multiple
824 ``rec`` blocks. If there are no recursive dependencies, ``mdo`` will
825 introduce no ``rec`` blocks. In this latter case an ``mdo`` expression
826 is precisely the same as a ``do`` expression, as one would expect.
827
828 In summary, given an ``mdo`` expression, GHC first performs
829 segmentation, introducing ``rec`` blocks to wrap over minimal recursive
830 groups. Then, each resulting ``rec`` is desugared, using a call to
831 ``Control.Monad.Fix.mfix`` as described in the previous section. The
832 original ``mdo``-expression typechecks exactly when the desugared
833 version would do so.
834
835 Here are some other important points in using the recursive-do notation:
836
837 -  It is enabled with the flag :ghc-flag:`-XRecursiveDo`, or the
838    ``LANGUAGE RecursiveDo`` pragma. (The same flag enables both
839    ``mdo``-notation, and the use of ``rec`` blocks inside ``do``
840    expressions.)
841
842 -  ``rec`` blocks can also be used inside ``mdo``-expressions, which
843    will be treated as a single statement. However, it is good style to
844    either use ``mdo`` or ``rec`` blocks in a single expression.
845
846 -  If recursive bindings are required for a monad, then that monad must
847    be declared an instance of the ``MonadFix`` class.
848
849 -  The following instances of ``MonadFix`` are automatically provided:
850    List, Maybe, IO. Furthermore, the ``Control.Monad.ST`` and
851    ``Control.Monad.ST.Lazy`` modules provide the instances of the
852    ``MonadFix`` class for Haskell's internal state monad (strict and
853    lazy, respectively).
854
855 -  Like ``let`` and ``where`` bindings, name shadowing is not allowed
856    within an ``mdo``-expression or a ``rec``-block; that is, all the
857    names bound in a single ``rec`` must be distinct. (GHC will complain
858    if this is not the case.)
859
860 .. _applicative-do:
861
862 Applicative do-notation
863 -----------------------
864
865 .. index::
866    single: Applicative do-notation
867    single: do-notation; Applicative
868
869 .. ghc-flag:: -XApplicativeDo
870
871     :since: 8.0.1
872
873     Allow use of ``Applicative`` ``do`` notation.
874
875 The language option :ghc-flag:`-XApplicativeDo` enables an alternative translation for
876 the do-notation, which uses the operators ``<$>``, ``<*>``, along with ``join``
877 as far as possible. There are two main reasons for wanting to do this:
878
879 -  We can use do-notation with types that are an instance of ``Applicative`` and
880    ``Functor``, but not ``Monad``
881 -  In some monads, using the applicative operators is more efficient than monadic
882    bind. For example, it may enable more parallelism.
883
884 Applicative do-notation desugaring preserves the original semantics, provided
885 that the ``Applicative`` instance satisfies ``<*> = ap`` and ``pure = return``
886 (these are true of all the common monadic types). Thus, you can normally turn on
887 :ghc-flag:`-XApplicativeDo` without fear of breaking your program. There is one pitfall
888 to watch out for; see :ref:`applicative-do-pitfall`.
889
890 There are no syntactic changes with :ghc-flag:`-XApplicativeDo`. The only way it shows
891 up at the source level is that you can have a ``do`` expression that doesn't
892 require a ``Monad`` constraint. For example, in GHCi: ::
893
894     Prelude> :set -XApplicativeDo
895     Prelude> :t \m -> do { x <- m; return (not x) }
896     \m -> do { x <- m; return (not x) }
897       :: Functor f => f Bool -> f Bool
898
899 This example only requires ``Functor``, because it is translated into ``(\x ->
900 not x) <$> m``. A more complex example requires ``Applicative``, ::
901
902     Prelude> :t \m -> do { x <- m 'a'; y <- m 'b'; return (x || y) }
903     \m -> do { x <- m 'a'; y <- m 'b'; return (x || y) }
904       :: Applicative f => (Char -> f Bool) -> f Bool
905
906 Here GHC has translated the expression into ::
907
908     (\x y -> x || y) <$> m 'a' <*> m 'b'
909
910 It is possible to see the actual translation by using :ghc-flag:`-ddump-ds`, but be
911 warned, the output is quite verbose.
912
913 Note that if the expression can't be translated into uses of ``<$>``, ``<*>``
914 only, then it will incur a ``Monad`` constraint as usual. This happens when
915 there is a dependency on a value produced by an earlier statement in the
916 ``do``-block: ::
917
918     Prelude> :t \m -> do { x <- m True; y <- m x; return (x || y) }
919     \m -> do { x <- m True; y <- m x; return (x || y) }
920       :: Monad m => (Bool -> m Bool) -> m Bool
921
922 Here, ``m x`` depends on the value of ``x`` produced by the first statement, so
923 the expression cannot be translated using ``<*>``.
924
925 In general, the rule for when a ``do`` statement incurs a ``Monad`` constraint
926 is as follows. If the do-expression has the following form: ::
927
928     do p1 <- E1; ...; pn <- En; return E
929
930 where none of the variables defined by ``p1...pn`` are mentioned in ``E1...En``,
931 then the expression will only require ``Applicative``. Otherwise, the expression
932 will require ``Monad``. The block may return a pure expression ``E`` depending
933 upon the results ``p1...pn`` with either ``return`` or ``pure``.
934
935 Note: the final statement must match one of these patterns exactly:
936
937 - ``return E``
938 - ``return $ E``
939 - ``pure E``
940 - ``pure $ E``
941
942 otherwise GHC cannot recognise it as a ``return`` statement, and the
943 transformation to use ``<$>`` that we saw above does not apply.  In
944 particular, slight variations such as ``return . Just $ x`` or ``let x
945 = e in return x`` would not be recognised.
946
947 If the final statement is not of one of these forms, GHC falls back to
948 standard ``do`` desugaring, and the expression will require a
949 ``Monad`` constraint.
950
951 When the statements of a ``do`` expression have dependencies between
952 them, and ``ApplicativeDo`` cannot infer an ``Applicative`` type, it
953 uses a heuristic algorithm to try to use ``<*>`` as much as possible.
954 This algorithm usually finds the best solution, but in rare complex
955 cases it might miss an opportunity.  There is an algorithm that finds
956 the optimal solution, provided as an option:
957
958 .. ghc-flag:: -foptimal-applicative-do
959
960     :since: 8.0.1
961
962     Enables an alternative algorithm for choosing where to use ``<*>``
963     in conjunction with the ``ApplicativeDo`` language extension.
964     This algorithm always finds the optimal solution, but it is
965     expensive: ``O(n^3)``, so this option can lead to long compile
966     times when there are very large ``do`` expressions (over 100
967     statements).  The default ``ApplicativeDo`` algorithm is ``O(n^2)``.
968
969 .. _applicative-do-pitfall:
970
971 Things to watch out for
972 ~~~~~~~~~~~~~~~~~~~~~~~
973
974 Your code should just work as before when :ghc-flag:`-XApplicativeDo` is enabled,
975 provided you use conventional ``Applicative`` instances. However, if you define
976 a ``Functor`` or ``Applicative`` instance using do-notation, then it will likely
977 get turned into an infinite loop by GHC. For example, if you do this: ::
978
979     instance Functor MyType where
980         fmap f m = do x <- m; return (f x)
981
982 Then applicative desugaring will turn it into ::
983
984     instance Functor MyType where
985         fmap f m = fmap (\x -> f x) m
986
987 And the program will loop at runtime. Similarly, an ``Applicative`` instance
988 like this ::
989
990     instance Applicative MyType where
991         pure = return
992         x <*> y = do f <- x; a <- y; return (f a)
993
994 will result in an infinte loop when ``<*>`` is called.
995
996 Just as you wouldn't define a ``Monad`` instance using the do-notation, you
997 shouldn't define ``Functor`` or ``Applicative`` instance using do-notation (when
998 using ``ApplicativeDo``) either. The correct way to define these instances in
999 terms of ``Monad`` is to use the ``Monad`` operations directly, e.g. ::
1000
1001     instance Functor MyType where
1002         fmap f m = m >>= return . f
1003
1004     instance Applicative MyType where
1005         pure = return
1006         (<*>) = ap
1007
1008
1009 .. _parallel-list-comprehensions:
1010
1011 Parallel List Comprehensions
1012 ----------------------------
1013
1014 .. index::
1015    single: list comprehensions; parallel
1016    single: parallel list comprehensions
1017
1018 .. ghc-flag:: -XParallelListComp
1019
1020     Allow parallel list comprehension syntax.
1021
1022 Parallel list comprehensions are a natural extension to list
1023 comprehensions. List comprehensions can be thought of as a nice syntax
1024 for writing maps and filters. Parallel comprehensions extend this to
1025 include the ``zipWith`` family.
1026
1027 A parallel list comprehension has multiple independent branches of
1028 qualifier lists, each separated by a ``|`` symbol. For example, the
1029 following zips together two lists: ::
1030
1031        [ (x, y) | x <- xs | y <- ys ]
1032
1033 The behaviour of parallel list comprehensions follows that of zip, in
1034 that the resulting list will have the same length as the shortest
1035 branch.
1036
1037 We can define parallel list comprehensions by translation to regular
1038 comprehensions. Here's the basic idea:
1039
1040 Given a parallel comprehension of the form: ::
1041
1042        [ e | p1 <- e11, p2 <- e12, ...
1043            | q1 <- e21, q2 <- e22, ...
1044            ...
1045        ]
1046
1047 This will be translated to: ::
1048
1049        [ e | ((p1,p2), (q1,q2), ...) <- zipN [(p1,p2) | p1 <- e11, p2 <- e12, ...]
1050                                              [(q1,q2) | q1 <- e21, q2 <- e22, ...]
1051                                              ...
1052        ]
1053
1054 where ``zipN`` is the appropriate zip for the given number of branches.
1055
1056 .. _generalised-list-comprehensions:
1057
1058 Generalised (SQL-like) List Comprehensions
1059 ------------------------------------------
1060
1061 .. index::
1062    single: list comprehensions; generalised
1063    single: extended list comprehensions
1064    single: group
1065    single: SQL
1066
1067 .. ghc-flag:: -XTransformListComp
1068
1069     Allow use of generalised list (SQL-like) comprehension syntax. This
1070     introduces the ``group``, ``by``, and ``using`` keywords.
1071
1072 Generalised list comprehensions are a further enhancement to the list
1073 comprehension syntactic sugar to allow operations such as sorting and
1074 grouping which are familiar from SQL. They are fully described in the
1075 paper `Comprehensive comprehensions: comprehensions with "order by" and
1076 "group by" <http://research.microsoft.com/~simonpj/papers/list-comp>`__,
1077 except that the syntax we use differs slightly from the paper.
1078
1079 The extension is enabled with the flag :ghc-flag:`-XTransformListComp`.
1080
1081 Here is an example:
1082
1083 ::
1084
1085     employees = [ ("Simon", "MS", 80)
1086                 , ("Erik", "MS", 100)
1087                 , ("Phil", "Ed", 40)
1088                 , ("Gordon", "Ed", 45)
1089                 , ("Paul", "Yale", 60) ]
1090
1091     output = [ (the dept, sum salary)
1092              | (name, dept, salary) <- employees
1093              , then group by dept using groupWith
1094              , then sortWith by (sum salary)
1095              , then take 5 ]
1096
1097 In this example, the list ``output`` would take on the value:
1098
1099 ::
1100
1101     [("Yale", 60), ("Ed", 85), ("MS", 180)]
1102
1103 There are three new keywords: ``group``, ``by``, and ``using``. (The
1104 functions ``sortWith`` and ``groupWith`` are not keywords; they are
1105 ordinary functions that are exported by ``GHC.Exts``.)
1106
1107 There are five new forms of comprehension qualifier, all introduced by
1108 the (existing) keyword ``then``:
1109
1110 -  ::
1111
1112        then f
1113
1114    This statement requires that
1115    f
1116    have the type
1117    forall a. [a] -> [a]
1118    . You can see an example of its use in the motivating example, as
1119    this form is used to apply
1120    take 5
1121    .
1122 -  ::
1123
1124        then f by e
1125
1126    This form is similar to the previous one, but allows you to create a
1127    function which will be passed as the first argument to f. As a
1128    consequence f must have the type
1129    ``forall a. (a -> t) -> [a] -> [a]``. As you can see from the type,
1130    this function lets f "project out" some information from the elements
1131    of the list it is transforming.
1132
1133    An example is shown in the opening example, where ``sortWith`` is
1134    supplied with a function that lets it find out the ``sum salary`` for
1135    any item in the list comprehension it transforms.
1136
1137 -  ::
1138
1139        then group by e using f
1140
1141    This is the most general of the grouping-type statements. In this
1142    form, f is required to have type
1143    ``forall a. (a -> t) -> [a] -> [[a]]``. As with the ``then f by e``
1144    case above, the first argument is a function supplied to f by the
1145    compiler which lets it compute e on every element of the list being
1146    transformed. However, unlike the non-grouping case, f additionally
1147    partitions the list into a number of sublists: this means that at
1148    every point after this statement, binders occurring before it in the
1149    comprehension refer to *lists* of possible values, not single values.
1150    To help understand this, let's look at an example:
1151
1152    ::
1153
1154        -- This works similarly to groupWith in GHC.Exts, but doesn't sort its input first
1155        groupRuns :: Eq b => (a -> b) -> [a] -> [[a]]
1156        groupRuns f = groupBy (\x y -> f x == f y)
1157
1158        output = [ (the x, y)
1159        | x <- ([1..3] ++ [1..2])
1160        , y <- [4..6]
1161        , then group by x using groupRuns ]
1162
1163    This results in the variable ``output`` taking on the value below:
1164
1165    ::
1166
1167        [(1, [4, 5, 6]), (2, [4, 5, 6]), (3, [4, 5, 6]), (1, [4, 5, 6]), (2, [4, 5, 6])]
1168
1169    Note that we have used the ``the`` function to change the type of x
1170    from a list to its original numeric type. The variable y, in
1171    contrast, is left unchanged from the list form introduced by the
1172    grouping.
1173
1174 -  ::
1175
1176        then group using f
1177
1178    With this form of the group statement, f is required to simply have
1179    the type ``forall a. [a] -> [[a]]``, which will be used to group up
1180    the comprehension so far directly. An example of this form is as
1181    follows:
1182
1183    ::
1184
1185        output = [ x
1186        | y <- [1..5]
1187        , x <- "hello"
1188        , then group using inits]
1189
1190    This will yield a list containing every prefix of the word "hello"
1191    written out 5 times:
1192
1193    ::
1194
1195        ["","h","he","hel","hell","hello","helloh","hellohe","hellohel","hellohell","hellohello","hellohelloh",...]
1196
1197 .. _monad-comprehensions:
1198
1199 Monad comprehensions
1200 --------------------
1201
1202 .. index::
1203    single: monad comprehensions
1204
1205 .. ghc-flag:: -XMonadComprehensions
1206
1207     :since: 7.2
1208
1209     Enable list comprehension syntax for arbitrary monads.
1210
1211 Monad comprehensions generalise the list comprehension notation,
1212 including parallel comprehensions (:ref:`parallel-list-comprehensions`)
1213 and transform comprehensions (:ref:`generalised-list-comprehensions`) to
1214 work for any monad.
1215
1216 Monad comprehensions support:
1217
1218 -  Bindings: ::
1219
1220        [ x + y | x <- Just 1, y <- Just 2 ]
1221
1222    Bindings are translated with the ``(>>=)`` and ``return`` functions
1223    to the usual do-notation: ::
1224
1225        do x <- Just 1
1226           y <- Just 2
1227           return (x+y)
1228
1229 -  Guards: ::
1230
1231        [ x | x <- [1..10], x <= 5 ]
1232
1233    Guards are translated with the ``guard`` function, which requires a
1234    ``MonadPlus`` instance: ::
1235
1236        do x <- [1..10]
1237           guard (x <= 5)
1238           return x
1239
1240 -  Transform statements (as with :ghc-flag:`-XTransformListComp`): ::
1241
1242        [ x+y | x <- [1..10], y <- [1..x], then take 2 ]
1243
1244    This translates to: ::
1245
1246        do (x,y) <- take 2 (do x <- [1..10]
1247                               y <- [1..x]
1248                               return (x,y))
1249           return (x+y)
1250
1251 -  Group statements (as with :ghc-flag:`-XTransformListComp`):
1252
1253    ::
1254
1255        [ x | x <- [1,1,2,2,3], then group by x using GHC.Exts.groupWith ]
1256        [ x | x <- [1,1,2,2,3], then group using myGroup ]
1257
1258 -  Parallel statements (as with :ghc-flag:`-XParallelListComp`):
1259
1260    ::
1261
1262        [ (x+y) | x <- [1..10]
1263                | y <- [11..20]
1264                ]
1265
1266    Parallel statements are translated using the ``mzip`` function, which
1267    requires a ``MonadZip`` instance defined in
1268    :base-ref:`Control.Monad.Zip <Control-Monad-Zip.html>`:
1269
1270    ::
1271
1272        do (x,y) <- mzip (do x <- [1..10]
1273                             return x)
1274                         (do y <- [11..20]
1275                             return y)
1276           return (x+y)
1277
1278 All these features are enabled by default if the :ghc-flag:`-XMonadComprehensions`
1279 extension is enabled. The types and more detailed examples on how to use
1280 comprehensions are explained in the previous chapters
1281 :ref:`generalised-list-comprehensions` and
1282 :ref:`parallel-list-comprehensions`. In general you just have to replace
1283 the type ``[a]`` with the type ``Monad m => m a`` for monad
1284 comprehensions.
1285
1286 .. note::
1287     Even though most of these examples are using the list monad, monad
1288     comprehensions work for any monad. The ``base`` package offers all
1289     necessary instances for lists, which make :ghc-flag:`-XMonadComprehensions`
1290     backward compatible to built-in, transform and parallel list
1291     comprehensions.
1292
1293 More formally, the desugaring is as follows. We write ``D[ e | Q]`` to
1294 mean the desugaring of the monad comprehension ``[ e | Q]``:
1295
1296 .. code-block:: none
1297
1298     Expressions: e
1299     Declarations: d
1300     Lists of qualifiers: Q,R,S
1301
1302     -- Basic forms
1303     D[ e | ]               = return e
1304     D[ e | p <- e, Q ]  = e >>= \p -> D[ e | Q ]
1305     D[ e | e, Q ]          = guard e >> \p -> D[ e | Q ]
1306     D[ e | let d, Q ]      = let d in D[ e | Q ]
1307
1308     -- Parallel comprehensions (iterate for multiple parallel branches)
1309     D[ e | (Q | R), S ]    = mzip D[ Qv | Q ] D[ Rv | R ] >>= \(Qv,Rv) -> D[ e | S ]
1310
1311     -- Transform comprehensions
1312     D[ e | Q then f, R ]                  = f D[ Qv | Q ] >>= \Qv -> D[ e | R ]
1313
1314     D[ e | Q then f by b, R ]             = f (\Qv -> b) D[ Qv | Q ] >>= \Qv -> D[ e | R ]
1315
1316     D[ e | Q then group using f, R ]      = f D[ Qv | Q ] >>= \ys ->
1317                                             case (fmap selQv1 ys, ..., fmap selQvn ys) of
1318                                              Qv -> D[ e | R ]
1319
1320     D[ e | Q then group by b using f, R ] = f (\Qv -> b) D[ Qv | Q ] >>= \ys ->
1321                                             case (fmap selQv1 ys, ..., fmap selQvn ys) of
1322                                                Qv -> D[ e | R ]
1323
1324     where  Qv is the tuple of variables bound by Q (and used subsequently)
1325            selQvi is a selector mapping Qv to the ith component of Qv
1326
1327     Operator     Standard binding       Expected type
1328     --------------------------------------------------------------------
1329     return       GHC.Base               t1 -> m t2
1330     (>>=)        GHC.Base               m1 t1 -> (t2 -> m2 t3) -> m3 t3
1331     (>>)         GHC.Base               m1 t1 -> m2 t2         -> m3 t3
1332     guard        Control.Monad          t1 -> m t2
1333     fmap         GHC.Base               forall a b. (a->b) -> n a -> n b
1334     mzip         Control.Monad.Zip      forall a b. m a -> m b -> m (a,b)
1335
1336 The comprehension should typecheck when its desugaring would typecheck,
1337 except that (as discussed in :ref:`generalised-list-comprehensions`) in the
1338 "then ``f``" and "then group using ``f``" clauses, when the "by ``b``" qualifier
1339 is omitted, argument ``f`` should have a polymorphic type. In particular, "then
1340 ``Data.List.sort``" and "then group using ``Data.List.group``" are
1341 insufficiently polymorphic.
1342
1343 Monad comprehensions support rebindable syntax
1344 (:ref:`rebindable-syntax`). Without rebindable syntax, the operators
1345 from the "standard binding" module are used; with rebindable syntax, the
1346 operators are looked up in the current lexical scope. For example,
1347 parallel comprehensions will be typechecked and desugared using whatever
1348 "``mzip``" is in scope.
1349
1350 The rebindable operators must have the "Expected type" given in the
1351 table above. These types are surprisingly general. For example, you can
1352 use a bind operator with the type
1353
1354 ::
1355
1356     (>>=) :: T x y a -> (a -> T y z b) -> T x z b
1357
1358 In the case of transform comprehensions, notice that the groups are
1359 parameterised over some arbitrary type ``n`` (provided it has an
1360 ``fmap``, as well as the comprehension being over an arbitrary monad.
1361
1362 .. _monadfail-desugaring:
1363
1364 New monadic failure desugaring mechanism
1365 ----------------------------------------
1366
1367 .. ghc-flag:: -XMonadFailDesugaring
1368
1369     :since: 8.0.1
1370
1371     Use the ``MonadFail.fail`` instead of the legacy ``Monad.fail`` function
1372     when desugaring refutable patterns in ``do`` blocks.
1373
1374 The ``-XMonadFailDesugaring`` extension switches the desugaring of
1375 ``do``-blocks to use ``MonadFail.fail`` instead of ``Monad.fail``. This will
1376 eventually be the default behaviour in a future GHC release, under the
1377 `MonadFail Proposal (MFP)
1378 <https://prime.haskell.org/wiki/Libraries/Proposals/MonadFail>`__.
1379
1380 This extension is temporary, and will be deprecated in a future release. It is
1381 included so that library authors have a hard check for whether their code
1382 will work with future GHC versions.
1383
1384 .. _rebindable-syntax:
1385
1386 Rebindable syntax and the implicit Prelude import
1387 -------------------------------------------------
1388
1389 .. ghc-flag:: -XNoImplicitPrelude
1390
1391     Don't import ``Prelude`` by default.
1392
1393 GHC normally imports ``Prelude.hi`` files for
1394 you. If you'd rather it didn't, then give it a ``-XNoImplicitPrelude``
1395 option. The idea is that you can then import a Prelude of your own. (But
1396 don't call it ``Prelude``; the Haskell module namespace is flat, and you
1397 must not conflict with any Prelude module.)
1398
1399 .. ghc-flag:: -XRebindableSyntax
1400
1401     :implies: :ghc-flag:`-XNoImplicitPrelude`
1402     :since: 7.0.1
1403
1404     Enable rebinding of a variety of usually-built-in operations.
1405
1406 Suppose you are importing a Prelude of your own in order to define your
1407 own numeric class hierarchy. It completely defeats that purpose if the
1408 literal "1" means "``Prelude.fromInteger 1``", which is what the Haskell
1409 Report specifies. So the :ghc-flag:`-XRebindableSyntax` flag causes the
1410 following pieces of built-in syntax to refer to *whatever is in scope*,
1411 not the Prelude versions:
1412
1413 -  An integer literal ``368`` means "``fromInteger (368::Integer)``",
1414    rather than "``Prelude.fromInteger (368::Integer)``".
1415
1416 -  Fractional literals are handed in just the same way, except that the
1417    translation is ``fromRational (3.68::Rational)``.
1418
1419 -  The equality test in an overloaded numeric pattern uses whatever
1420    ``(==)`` is in scope.
1421
1422 -  The subtraction operation, and the greater-than-or-equal test, in
1423    ``n+k`` patterns use whatever ``(-)`` and ``(>=)`` are in scope.
1424
1425 -  Negation (e.g. "``- (f x)``") means "``negate (f x)``", both in
1426    numeric patterns, and expressions.
1427
1428 -  Conditionals (e.g. "``if`` e1 ``then`` e2 ``else`` e3") means
1429    "``ifThenElse`` e1 e2 e3". However ``case`` expressions are
1430    unaffected.
1431
1432 -  "Do" notation is translated using whatever functions ``(>>=)``,
1433    ``(>>)``, and ``fail``, are in scope (not the Prelude versions). List
1434    comprehensions, ``mdo`` (:ref:`recursive-do-notation`), and parallel
1435    array comprehensions, are unaffected.
1436
1437 -  Arrow notation (see :ref:`arrow-notation`) uses whatever ``arr``,
1438    ``(>>>)``, ``first``, ``app``, ``(|||)`` and ``loop`` functions are
1439    in scope. But unlike the other constructs, the types of these
1440    functions must match the Prelude types very closely. Details are in
1441    flux; if you want to use this, ask!
1442
1443 -  List notation, such as ``[x,y]`` or ``[m..n]`` can also be treated
1444    via rebindable syntax if you use `-XOverloadedLists`;
1445    see :ref:`overloaded-lists`.
1446
1447 :ghc-flag:`-XRebindableSyntax` implies :ghc-flag:`-XNoImplicitPrelude`.
1448
1449 In all cases (apart from arrow notation), the static semantics should be
1450 that of the desugared form, even if that is a little unexpected. For
1451 example, the static semantics of the literal ``368`` is exactly that of
1452 ``fromInteger (368::Integer)``; it's fine for ``fromInteger`` to have
1453 any of the types: ::
1454
1455     fromInteger :: Integer -> Integer
1456     fromInteger :: forall a. Foo a => Integer -> a
1457     fromInteger :: Num a => a -> Integer
1458     fromInteger :: Integer -> Bool -> Bool
1459
1460 Be warned: this is an experimental facility, with fewer checks than
1461 usual. Use ``-dcore-lint`` to typecheck the desugared program. If Core
1462 Lint is happy you should be all right.
1463
1464 Things unaffected by :ghc-flag:`-XRebindableSyntax`
1465 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1466
1467 :ghc-flag:`-XRebindableSyntax` does not apply to any code generated from a
1468 ``deriving`` clause or declaration. To see why, consider the following code: ::
1469
1470     {-# LANGUAGE RebindableSyntax, OverloadedStrings #-}
1471     newtype Text = Text String
1472
1473     fromString :: String -> Text
1474     fromString = Text
1475
1476     data Foo = Foo deriving Show
1477
1478 This will generate code to the effect of: ::
1479
1480     instance Show Foo where
1481       showsPrec _ Foo = showString "Foo"
1482
1483 But because :ghc-flag:`-XRebindableSyntax` and :ghc-flag:`-XOverloadedStrings`
1484 are enabled, the ``"Foo"`` string literal would now be of type ``Text``, not
1485 ``String``, which ``showString`` doesn't accept! This causes the generated
1486 ``Show`` instance to fail to typecheck. It's hard to imagine any scenario where
1487 it would be desirable have :ghc-flag:`-XRebindableSyntax` behavior within
1488 derived code, so GHC simply ignores :ghc-flag:`-XRebindableSyntax` entirely
1489 when checking derived code.
1490
1491 .. _postfix-operators:
1492
1493 Postfix operators
1494 -----------------
1495
1496 .. ghc-flag:: -XPostfixOperators
1497
1498     Allow the use of post-fix operators
1499
1500 The :ghc-flag:`-XPostfixOperators` flag enables a small extension to the syntax
1501 of left operator sections, which allows you to define postfix operators.
1502 The extension is this: the left section ::
1503
1504       (e !)
1505
1506 is equivalent (from the point of view of both type checking and
1507 execution) to the expression ::
1508
1509       ((!) e)
1510
1511 (for any expression ``e`` and operator ``(!)``. The strict Haskell 98
1512 interpretation is that the section is equivalent to ::
1513
1514       (\y -> (!) e y)
1515
1516 That is, the operator must be a function of two arguments. GHC allows it
1517 to take only one argument, and that in turn allows you to write the
1518 function postfix.
1519
1520 The extension does not extend to the left-hand side of function
1521 definitions; you must define such a function in prefix form.
1522
1523 .. _tuple-sections:
1524
1525 Tuple sections
1526 --------------
1527
1528 .. ghc-flag:: -XTupleSections
1529
1530     :since: 6.12
1531
1532     Allow the use of tuple section syntax
1533
1534 The :ghc-flag:`-XTupleSections` flag enables Python-style partially applied
1535 tuple constructors. For example, the following program ::
1536
1537       (, True)
1538
1539 is considered to be an alternative notation for the more unwieldy
1540 alternative ::
1541
1542       \x -> (x, True)
1543
1544 You can omit any combination of arguments to the tuple, as in the
1545 following ::
1546
1547       (, "I", , , "Love", , 1337)
1548
1549 which translates to ::
1550
1551       \a b c d -> (a, "I", b, c, "Love", d, 1337)
1552
1553 If you have `unboxed tuples <#unboxed-tuples>`__ enabled, tuple sections
1554 will also be available for them, like so ::
1555
1556       (# , True #)
1557
1558 Because there is no unboxed unit tuple, the following expression ::
1559
1560       (# #)
1561
1562 continues to stand for the unboxed singleton tuple data constructor.
1563
1564 .. _lambda-case:
1565
1566 Lambda-case
1567 -----------
1568
1569 .. ghc-flag:: -XLambdaCase
1570
1571     :since: 7.6.1
1572
1573     Allow the use of lambda-case syntax.
1574
1575 The :ghc-flag:`-XLambdaCase` flag enables expressions of the form ::
1576
1577       \case { p1 -> e1; ...; pN -> eN }
1578
1579 which is equivalent to ::
1580
1581       \freshName -> case freshName of { p1 -> e1; ...; pN -> eN }
1582
1583 Note that ``\case`` starts a layout, so you can write ::
1584
1585       \case
1586         p1 -> e1
1587         ...
1588         pN -> eN
1589
1590 .. _empty-case:
1591
1592 Empty case alternatives
1593 -----------------------
1594
1595 .. ghc-flag:: -XEmptyCase
1596
1597     :since: 7.8.1
1598
1599     Allow empty case expressions.
1600
1601 The :ghc-flag:`-XEmptyCase` flag enables case expressions, or lambda-case
1602 expressions, that have no alternatives, thus: ::
1603
1604     case e of { }   -- No alternatives
1605
1606 or ::
1607
1608     \case { }       -- -XLambdaCase is also required
1609
1610 This can be useful when you know that the expression being scrutinised
1611 has no non-bottom values. For example:
1612
1613 ::
1614
1615       data Void
1616       f :: Void -> Int
1617       f x = case x of { }
1618
1619 With dependently-typed features it is more useful (see :ghc-ticket:`2431`). For
1620 example, consider these two candidate definitions of ``absurd``:
1621
1622 ::
1623
1624     data a :==: b where
1625       Refl :: a :==: a
1626
1627     absurd :: True :~: False -> a
1628     absurd x = error "absurd"    -- (A)
1629     absurd x = case x of {}      -- (B)
1630
1631 We much prefer (B). Why? Because GHC can figure out that
1632 ``(True :~: False)`` is an empty type. So (B) has no partiality and GHC
1633 should be able to compile with :ghc-flag:`-Wincomplete-patterns`. (Though
1634 the pattern match checking is not yet clever enough to do that.) On the
1635 other hand (A) looks dangerous, and GHC doesn't check to make sure that,
1636 in fact, the function can never get called.
1637
1638 .. _multi-way-if:
1639
1640 Multi-way if-expressions
1641 ------------------------
1642
1643 .. ghc-flag:: -XMultiWayIf
1644
1645     :since: 7.6.1
1646
1647     Allow the use of multi-way-``if`` syntax.
1648
1649 With :ghc-flag:`-XMultiWayIf` flag GHC accepts conditional expressions with
1650 multiple branches: ::
1651
1652       if | guard1 -> expr1
1653          | ...
1654          | guardN -> exprN
1655
1656 which is roughly equivalent to ::
1657
1658       case () of
1659         _ | guard1 -> expr1
1660         ...
1661         _ | guardN -> exprN
1662
1663 Multi-way if expressions introduce a new layout context. So the example
1664 above is equivalent to: ::
1665
1666       if { | guard1 -> expr1
1667          ; | ...
1668          ; | guardN -> exprN
1669          }
1670
1671 The following behaves as expected: ::
1672
1673       if | guard1 -> if | guard2 -> expr2
1674                         | guard3 -> expr3
1675          | guard4 -> expr4
1676
1677 because layout translates it as ::
1678
1679       if { | guard1 -> if { | guard2 -> expr2
1680                           ; | guard3 -> expr3
1681                           }
1682          ; | guard4 -> expr4
1683          }
1684
1685 Layout with multi-way if works in the same way as other layout contexts,
1686 except that the semi-colons between guards in a multi-way if are
1687 optional. So it is not necessary to line up all the guards at the same
1688 column; this is consistent with the way guards work in function
1689 definitions and case expressions.
1690
1691 .. _local-fixity-declarations:
1692
1693 Local Fixity Declarations
1694 -------------------------
1695
1696 A careful reading of the Haskell 98 Report reveals that fixity
1697 declarations (``infix``, ``infixl``, and ``infixr``) are permitted to
1698 appear inside local bindings such those introduced by ``let`` and
1699 ``where``. However, the Haskell Report does not specify the semantics of
1700 such bindings very precisely.
1701
1702 In GHC, a fixity declaration may accompany a local binding: ::
1703
1704     let f = ...
1705         infixr 3 `f`
1706     in
1707         ...
1708
1709 and the fixity declaration applies wherever the binding is in scope. For
1710 example, in a ``let``, it applies in the right-hand sides of other
1711 ``let``-bindings and the body of the ``let``\ C. Or, in recursive ``do``
1712 expressions (:ref:`recursive-do-notation`), the local fixity
1713 declarations of a ``let`` statement scope over other statements in the
1714 group, just as the bound name does.
1715
1716 Moreover, a local fixity declaration *must* accompany a local binding
1717 of that name: it is not possible to revise the fixity of name bound
1718 elsewhere, as in ::
1719
1720     let infixr 9 $ in ...
1721
1722 Because local fixity declarations are technically Haskell 98, no flag is
1723 necessary to enable them.
1724
1725 .. _package-imports:
1726
1727 Import and export extensions
1728 ----------------------------
1729
1730 Hiding things the imported module doesn't export
1731 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1732
1733 Technically in Haskell 2010 this is illegal: ::
1734
1735     module A( f ) where
1736       f = True
1737
1738     module B where
1739       import A hiding( g )  -- A does not export g
1740       g = f
1741
1742 The ``import A hiding( g )`` in module ``B`` is technically an error
1743 (`Haskell Report,
1744 5.3.1 <http://www.haskell.org/onlinereport/haskell2010/haskellch5.html#x11-1020005.3.1>`__)
1745 because ``A`` does not export ``g``. However GHC allows it, in the
1746 interests of supporting backward compatibility; for example, a newer
1747 version of ``A`` might export ``g``, and you want ``B`` to work in
1748 either case.
1749
1750 The warning :ghc-flag:`-Wdodgy-imports`, which is off by default but included
1751 with :ghc-flag:`-W`, warns if you hide something that the imported module does
1752 not export.
1753
1754 .. _package-qualified-imports:
1755
1756 Package-qualified imports
1757 ~~~~~~~~~~~~~~~~~~~~~~~~~
1758
1759 .. ghc-flag:: -XPackageImports
1760
1761     Allow the use of package-qualified ``import`` syntax.
1762
1763 With the :ghc-flag:`-XPackageImports` flag, GHC allows import declarations to be
1764 qualified by the package name that the module is intended to be imported
1765 from. For example: ::
1766
1767     import "network" Network.Socket
1768
1769 would import the module ``Network.Socket`` from the package ``network``
1770 (any version). This may be used to disambiguate an import when the same
1771 module is available from multiple packages, or is present in both the
1772 current package being built and an external package.
1773
1774 The special package name ``this`` can be used to refer to the current
1775 package being built.
1776
1777 .. note::
1778    You probably don't need to use this feature, it was added mainly so that we
1779    can build backwards-compatible versions of packages when APIs change. It can
1780    lead to fragile dependencies in the common case: modules occasionally move
1781    from one package to another, rendering any package-qualified imports broken.
1782    See also :ref:`package-thinning-and-renaming` for an alternative way of
1783    disambiguating between module names.
1784
1785 .. _safe-imports-ext:
1786
1787 Safe imports
1788 ~~~~~~~~~~~~
1789
1790 .. ghc-flag:: -XSafe
1791               -XTrustworthy
1792               -XUnsafe
1793     :noindex:
1794
1795     :since: 7.2
1796
1797     Declare the Safe Haskell state of the current module.
1798
1799 With the :ghc-flag:`-XSafe`, :ghc-flag:`-XTrustworthy` and :ghc-flag:`-XUnsafe`
1800 language flags, GHC extends the import declaration syntax to take an optional
1801 ``safe`` keyword after the ``import`` keyword. This feature is part of the Safe
1802 Haskell GHC extension. For example: ::
1803
1804     import safe qualified Network.Socket as NS
1805
1806 would import the module ``Network.Socket`` with compilation only
1807 succeeding if ``Network.Socket`` can be safely imported. For a description of
1808 when a import is considered safe see :ref:`safe-haskell`.
1809
1810 .. _explicit-namespaces:
1811
1812 Explicit namespaces in import/export
1813 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1814
1815 .. ghc-flag:: -XExplicitNamespaces
1816
1817     :since: 7.6.1
1818
1819     Enable use of explicit namespaces in module export lists.
1820
1821 In an import or export list, such as ::
1822
1823       module M( f, (++) ) where ...
1824         import N( f, (++) )
1825         ...
1826
1827 the entities ``f`` and ``(++)`` are *values*. However, with type
1828 operators (:ref:`type-operators`) it becomes possible to declare
1829 ``(++)`` as a *type constructor*. In that case, how would you export or
1830 import it?
1831
1832 The :ghc-flag:`-XExplicitNamespaces` extension allows you to prefix the name of
1833 a type constructor in an import or export list with "``type``" to
1834 disambiguate this case, thus: ::
1835
1836       module M( f, type (++) ) where ...
1837         import N( f, type (++) )
1838         ...
1839       module N( f, type (++) ) where
1840         data family a ++ b = L a | R b
1841
1842 The extension :ghc-flag:`-XExplicitNamespaces` is implied by
1843 :ghc-flag:`-XTypeOperators` and (for some reason) by :ghc-flag:`-XTypeFamilies`.
1844
1845 In addition, with :ghc-flag:`-XPatternSynonyms` you can prefix the name of a
1846 data constructor in an import or export list with the keyword
1847 ``pattern``, to allow the import or export of a data constructor without
1848 its parent type constructor (see :ref:`patsyn-impexp`).
1849
1850 .. _syntax-stolen:
1851
1852 Summary of stolen syntax
1853 ------------------------
1854
1855 Turning on an option that enables special syntax *might* cause working
1856 Haskell 98 code to fail to compile, perhaps because it uses a variable
1857 name which has become a reserved word. This section lists the syntax
1858 that is "stolen" by language extensions. We use notation and nonterminal
1859 names from the Haskell 98 lexical syntax (see the Haskell 98 Report). We
1860 only list syntax changes here that might affect existing working
1861 programs (i.e. "stolen" syntax). Many of these extensions will also
1862 enable new context-free syntax, but in all cases programs written to use
1863 the new syntax would not be compilable without the option enabled.
1864
1865 There are two classes of special syntax:
1866
1867 -  New reserved words and symbols: character sequences which are no
1868    longer available for use as identifiers in the program.
1869
1870 -  Other special syntax: sequences of characters that have a different
1871    meaning when this particular option is turned on.
1872
1873 The following syntax is stolen:
1874
1875 ``forall``
1876     .. index::
1877        single: forall
1878
1879     Stolen (in types) by: :ghc-flag:`-XExplicitForAll`, and hence by
1880     :ghc-flag:`-XScopedTypeVariables`, :ghc-flag:`-XLiberalTypeSynonyms`,
1881     :ghc-flag:`-XRankNTypes`, :ghc-flag:`-XExistentialQuantification`
1882
1883 ``mdo``
1884     .. index::
1885        single: mdo
1886
1887     Stolen by: :ghc-flag:`-XRecursiveDo`
1888
1889 ``foreign``
1890     .. index::
1891        single: foreign
1892
1893     Stolen by: :ghc-flag:`-XForeignFunctionInterface`
1894
1895 ``rec``, ``proc``, ``-<``, ``>-``, ``-<<``, ``>>-``, ``(|``, ``|)``
1896     .. index::
1897        single: proc
1898
1899     Stolen by: :ghc-flag:`-XArrows`
1900
1901 ``?varid``
1902     .. index::
1903        single: implicit parameters
1904
1905     Stolen by: :ghc-flag:`-XImplicitParams`
1906
1907 ``[|``, ``[e|``, ``[p|``, ``[d|``, ``[t|``, ``[||``, ``[e||``
1908     .. index::
1909        single: Quasi-quotes
1910
1911     Stolen by: :ghc-flag:`-XQuasiQuotes`. Moreover, this introduces an ambiguity
1912     with list comprehension syntax. See the
1913     :ref:`discussion on quasi-quoting <quasi-quotes-list-comprehension-ambiguity>`
1914     for details.
1915
1916 ``$(``, ``$$(``, ``$varid``, ``$$varid``
1917     .. index::
1918        single: Template Haskell
1919
1920     Stolen by: :ghc-flag:`-XTemplateHaskell`
1921
1922 ``[varid|``
1923     .. index::
1924        single: quasi-quotation
1925
1926     Stolen by: :ghc-flag:`-XQuasiQuotes`
1927
1928 ⟨varid⟩, ``#``\ ⟨char⟩, ``#``, ⟨string⟩, ``#``, ⟨integer⟩, ``#``, ⟨float⟩, ``#``, ⟨float⟩, ``##``
1929     Stolen by: :ghc-flag:`-XMagicHash`
1930
1931 ``(#``, ``#)``
1932     Stolen by: :ghc-flag:`-XUnboxedTuples`
1933
1934 ⟨varid⟩, ``!``, ⟨varid⟩
1935     Stolen by: :ghc-flag:`-XBangPatterns`
1936
1937 ``pattern``
1938     Stolen by: :ghc-flag:`-XPatternSynonyms`
1939
1940 .. _data-type-extensions:
1941
1942 Extensions to data types and type synonyms
1943 ==========================================
1944
1945 .. _nullary-types:
1946
1947 Data types with no constructors
1948 -------------------------------
1949
1950 .. ghc-flag:: -XEmptyDataDecls
1951
1952     Allow definition of empty ``data`` types.
1953
1954 With the :ghc-flag:`-XEmptyDataDecls` flag (or equivalent ``LANGUAGE`` pragma), GHC
1955 lets you declare a data type with no constructors. For example: ::
1956
1957       data S      -- S :: *
1958       data T a    -- T :: * -> *
1959
1960 Syntactically, the declaration lacks the "= constrs" part. The type can
1961 be parameterised over types of any kind, but if the kind is not ``*``
1962 then an explicit kind annotation must be used (see :ref:`kinding`).
1963
1964 Such data types have only one value, namely bottom. Nevertheless, they
1965 can be useful when defining "phantom types".
1966
1967 .. _datatype-contexts:
1968
1969 Data type contexts
1970 ------------------
1971
1972 .. ghc-flag:: -XDatatypeContexts
1973
1974     :since: 7.0.1
1975
1976     Allow contexts on ``data`` types.
1977
1978 Haskell allows datatypes to be given contexts, e.g. ::
1979
1980     data Eq a => Set a = NilSet | ConsSet a (Set a)
1981
1982 give constructors with types: ::
1983
1984     NilSet :: Set a
1985     ConsSet :: Eq a => a -> Set a -> Set a
1986
1987 This is widely considered a misfeature, and is going to be removed from
1988 the language. In GHC, it is controlled by the deprecated extension
1989 ``DatatypeContexts``.
1990
1991 .. _infix-tycons:
1992
1993 Infix type constructors, classes, and type variables
1994 ----------------------------------------------------
1995
1996 GHC allows type constructors, classes, and type variables to be
1997 operators, and to be written infix, very much like expressions. More
1998 specifically:
1999
2000 -  A type constructor or class can be any non-reserved operator.
2001    Symbols used in types are always like capitalized identifiers; they
2002    are never variables. Note that this is different from the lexical
2003    syntax of data constructors, which are required to begin with a
2004    ``:``.
2005
2006 -  Data type and type-synonym declarations can be written infix,
2007    parenthesised if you want further arguments. E.g. ::
2008
2009          data a :*: b = Foo a b
2010          type a :+: b = Either a b
2011          class a :=: b where ...
2012
2013          data (a :**: b) x = Baz a b x
2014          type (a :++: b) y = Either (a,b) y
2015
2016 -  Types, and class constraints, can be written infix. For example ::
2017
2018          x :: Int :*: Bool
2019          f :: (a :=: b) => a -> b
2020
2021 -  Back-quotes work as for expressions, both for type constructors and
2022    type variables; e.g. ``Int `Either` Bool``, or ``Int `a` Bool``.
2023    Similarly, parentheses work the same; e.g. ``(:*:) Int Bool``.
2024
2025 -  Fixities may be declared for type constructors, or classes, just as
2026    for data constructors. However, one cannot distinguish between the
2027    two in a fixity declaration; a fixity declaration sets the fixity for
2028    a data constructor and the corresponding type constructor. For
2029    example: ::
2030
2031          infixl 7 T, :*:
2032
2033    sets the fixity for both type constructor ``T`` and data constructor
2034    ``T``, and similarly for ``:*:``. ``Int `a` Bool``.
2035
2036 -  Function arrow is ``infixr`` with fixity 0 (this might change; it's
2037    not clear what it should be).
2038
2039 .. _type-operators:
2040
2041 Type operators
2042 --------------
2043
2044 .. ghc-flag:: -XTypeOperators
2045
2046     :implies: :ghc-flag:`-XExplicitNamespaces`
2047
2048     Allow the use and definition of types with operator names.
2049
2050 In types, an operator symbol like ``(+)`` is normally treated as a type
2051 *variable*, just like ``a``. Thus in Haskell 98 you can say
2052
2053 ::
2054
2055     type T (+) = ((+), (+))
2056     -- Just like: type T a = (a,a)
2057
2058     f :: T Int -> Int
2059     f (x,y)= x
2060
2061 As you can see, using operators in this way is not very useful, and
2062 Haskell 98 does not even allow you to write them infix.
2063
2064 The language :ghc-flag:`-XTypeOperators` changes this behaviour:
2065
2066 -  Operator symbols become type *constructors* rather than type
2067    *variables*.
2068
2069 -  Operator symbols in types can be written infix, both in definitions
2070    and uses. For example: ::
2071
2072        data a + b = Plus a b
2073        type Foo = Int + Bool
2074
2075 -  There is now some potential ambiguity in import and export lists; for
2076    example if you write ``import M( (+) )`` do you mean the *function*
2077    ``(+)`` or the *type constructor* ``(+)``? The default is the former,
2078    but with :ghc-flag:`-XExplicitNamespaces` (which is implied by
2079    :ghc-flag:`-XTypeOperators`) GHC allows you to specify the latter by
2080    preceding it with the keyword ``type``, thus: ::
2081
2082        import M( type (+) )
2083
2084    See :ref:`explicit-namespaces`.
2085
2086 -  The fixity of a type operator may be set using the usual fixity
2087    declarations but, as in :ref:`infix-tycons`, the function and type
2088    constructor share a single fixity.
2089
2090 .. _type-synonyms:
2091
2092 Liberalised type synonyms
2093 -------------------------
2094
2095 .. ghc-flag:: -XLiberalTypeSynonyms
2096
2097     :implies: :ghc-flag:`-XExplicitForAll`
2098
2099     Relax many of the Haskell 98 rules on type synonym definitions.
2100
2101 Type synonyms are like macros at the type level, but Haskell 98 imposes
2102 many rules on individual synonym declarations. With the
2103 :ghc-flag:`-XLiberalTypeSynonyms` extension, GHC does validity checking on types
2104 *only after expanding type synonyms*. That means that GHC can be very
2105 much more liberal about type synonyms than Haskell 98.
2106
2107 -  You can write a ``forall`` (including overloading) in a type synonym,
2108    thus: ::
2109
2110          type Discard a = forall b. Show b => a -> b -> (a, String)
2111
2112          f :: Discard a
2113          f x y = (x, show y)
2114
2115          g :: Discard Int -> (Int,String)    -- A rank-2 type
2116          g f = f 3 True
2117
2118 -  If you also use :ghc-flag:`-XUnboxedTuples`, you can write an unboxed tuple
2119    in a type synonym: ::
2120
2121          type Pr = (# Int, Int #)
2122
2123          h :: Int -> Pr
2124          h x = (# x, x #)
2125
2126 -  You can apply a type synonym to a forall type: ::
2127
2128          type Foo a = a -> a -> Bool
2129
2130          f :: Foo (forall b. b->b)
2131
2132    After expanding the synonym, ``f`` has the legal (in GHC) type: ::
2133
2134          f :: (forall b. b->b) -> (forall b. b->b) -> Bool
2135
2136 -  You can apply a type synonym to a partially applied type synonym: ::
2137
2138          type Generic i o = forall x. i x -> o x
2139          type Id x = x
2140
2141          foo :: Generic Id []
2142
2143    After expanding the synonym, ``foo`` has the legal (in GHC) type: ::
2144
2145          foo :: forall x. x -> [x]
2146
2147 GHC currently does kind checking before expanding synonyms (though even
2148 that could be changed).
2149
2150 After expanding type synonyms, GHC does validity checking on types,
2151 looking for the following malformedness which isn't detected simply by
2152 kind checking:
2153
2154 -  Type constructor applied to a type involving for-alls (if
2155    :ghc-flag:`-XImpredicativeTypes` is off)
2156
2157 -  Partially-applied type synonym.
2158
2159 So, for example, this will be rejected: ::
2160
2161       type Pr = forall a. a
2162
2163       h :: [Pr]
2164       h = ...
2165
2166 because GHC does not allow type constructors applied to for-all types.
2167
2168 .. _existential-quantification:
2169
2170 Existentially quantified data constructors
2171 ------------------------------------------
2172
2173 .. ghc-flag:: -XExistentialQuantification
2174
2175     :implies: :ghc-flag:`-XExplicitForAll`
2176
2177     Allow existentially quantified type variables in types.
2178
2179 The idea of using existential quantification in data type declarations
2180 was suggested by Perry, and implemented in Hope+ (Nigel Perry, *The
2181 Implementation of Practical Functional Programming Languages*, PhD
2182 Thesis, University of London, 1991). It was later formalised by Laufer
2183 and Odersky (*Polymorphic type inference and abstract data types*,
2184 TOPLAS, 16(5), pp. 1411-1430, 1994). It's been in Lennart Augustsson's
2185 ``hbc`` Haskell compiler for several years, and proved very useful.
2186 Here's the idea. Consider the declaration: ::
2187
2188       data Foo = forall a. MkFoo a (a -> Bool)
2189                | Nil
2190
2191 The data type ``Foo`` has two constructors with types: ::
2192
2193       MkFoo :: forall a. a -> (a -> Bool) -> Foo
2194       Nil   :: Foo
2195
2196 Notice that the type variable ``a`` in the type of ``MkFoo`` does not
2197 appear in the data type itself, which is plain ``Foo``. For example, the
2198 following expression is fine: ::
2199
2200       [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]
2201
2202 Here, ``(MkFoo 3 even)`` packages an integer with a function ``even``
2203 that maps an integer to ``Bool``; and ``MkFoo 'c'
2204 isUpper`` packages a character with a compatible function. These two
2205 things are each of type ``Foo`` and can be put in a list.
2206
2207 What can we do with a value of type ``Foo``? In particular, what
2208 happens when we pattern-match on ``MkFoo``? ::
2209
2210       f (MkFoo val fn) = ???
2211
2212 Since all we know about ``val`` and ``fn`` is that they are compatible,
2213 the only (useful) thing we can do with them is to apply ``fn`` to
2214 ``val`` to get a boolean. For example: ::
2215
2216       f :: Foo -> Bool
2217       f (MkFoo val fn) = fn val
2218
2219 What this allows us to do is to package heterogeneous values together
2220 with a bunch of functions that manipulate them, and then treat that
2221 collection of packages in a uniform manner. You can express quite a bit
2222 of object-oriented-like programming this way.
2223
2224 .. _existential:
2225
2226 Why existential?
2227 ~~~~~~~~~~~~~~~~
2228
2229 What has this to do with *existential* quantification? Simply that
2230 ``MkFoo`` has the (nearly) isomorphic type ::
2231
2232       MkFoo :: (exists a . (a, a -> Bool)) -> Foo
2233
2234 But Haskell programmers can safely think of the ordinary *universally*
2235 quantified type given above, thereby avoiding adding a new existential
2236 quantification construct.
2237
2238 .. _existential-with-context:
2239
2240 Existentials and type classes
2241 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2242
2243 An easy extension is to allow arbitrary contexts before the constructor.
2244 For example: ::
2245
2246     data Baz = forall a. Eq a => Baz1 a a
2247              | forall b. Show b => Baz2 b (b -> b)
2248
2249 The two constructors have the types you'd expect: ::
2250
2251     Baz1 :: forall a. Eq a => a -> a -> Baz
2252     Baz2 :: forall b. Show b => b -> (b -> b) -> Baz
2253
2254 But when pattern matching on ``Baz1`` the matched values can be compared
2255 for equality, and when pattern matching on ``Baz2`` the first matched
2256 value can be converted to a string (as well as applying the function to
2257 it). So this program is legal: ::
2258
2259       f :: Baz -> String
2260       f (Baz1 p q) | p == q    = "Yes"
2261                    | otherwise = "No"
2262       f (Baz2 v fn)            = show (fn v)
2263
2264 Operationally, in a dictionary-passing implementation, the constructors
2265 ``Baz1`` and ``Baz2`` must store the dictionaries for ``Eq`` and
2266 ``Show`` respectively, and extract it on pattern matching.
2267
2268 .. _existential-records:
2269
2270 Record Constructors
2271 ~~~~~~~~~~~~~~~~~~~
2272
2273 GHC allows existentials to be used with records syntax as well. For
2274 example: ::
2275
2276     data Counter a = forall self. NewCounter
2277         { _this    :: self
2278         , _inc     :: self -> self
2279         , _display :: self -> IO ()
2280         , tag      :: a
2281         }
2282
2283 Here ``tag`` is a public field, with a well-typed selector function
2284 ``tag :: Counter a -> a``. The ``self`` type is hidden from the outside;
2285 any attempt to apply ``_this``, ``_inc`` or ``_display`` as functions
2286 will raise a compile-time error. In other words, *GHC defines a record
2287 selector function only for fields whose type does not mention the
2288 existentially-quantified variables*. (This example used an underscore in
2289 the fields for which record selectors will not be defined, but that is
2290 only programming style; GHC ignores them.)
2291
2292 To make use of these hidden fields, we need to create some helper
2293 functions: ::
2294
2295     inc :: Counter a -> Counter a
2296     inc (NewCounter x i d t) = NewCounter
2297         { _this = i x, _inc = i, _display = d, tag = t }
2298
2299     display :: Counter a -> IO ()
2300     display NewCounter{ _this = x, _display = d } = d x
2301
2302 Now we can define counters with different underlying implementations: ::
2303
2304     counterA :: Counter String
2305     counterA = NewCounter
2306         { _this = 0, _inc = (1+), _display = print, tag = "A" }
2307
2308     counterB :: Counter String
2309     counterB = NewCounter
2310         { _this = "", _inc = ('#':), _display = putStrLn, tag = "B" }
2311
2312     main = do
2313         display (inc counterA)         -- prints "1"
2314         display (inc (inc counterB))   -- prints "##"
2315
2316 Record update syntax is supported for existentials (and GADTs): ::
2317
2318     setTag :: Counter a -> a -> Counter a
2319     setTag obj t = obj{ tag = t }
2320
2321 The rule for record update is this:
2322
2323     the types of the updated fields may mention only the universally-quantified
2324     type variables of the data constructor. For GADTs, the field may mention
2325     only types that appear as a simple type-variable argument in the
2326     constructor's result type.
2327
2328 For example: ::
2329
2330     data T a b where { T1 { f1::a, f2::b, f3::(b,c) } :: T a b } -- c is existential
2331     upd1 t x = t { f1=x }   -- OK:   upd1 :: T a b -> a' -> T a' b
2332     upd2 t x = t { f3=x }   -- BAD   (f3's type mentions c, which is
2333                             --        existentially quantified)
2334
2335     data G a b where { G1 { g1::a, g2::c } :: G a [c] }
2336     upd3 g x = g { g1=x }   -- OK:   upd3 :: G a b -> c -> G c b
2337     upd4 g x = g { g2=x }   -- BAD (f2's type mentions c, which is not a simple
2338                             --      type-variable argument in G1's result type)
2339
2340 Restrictions
2341 ~~~~~~~~~~~~
2342
2343 There are several restrictions on the ways in which existentially-quantified
2344 constructors can be used.
2345
2346 -  When pattern matching, each pattern match introduces a new, distinct,
2347    type for each existential type variable. These types cannot be
2348    unified with any other type, nor can they escape from the scope of
2349    the pattern match. For example, these fragments are incorrect: ::
2350
2351        f1 (MkFoo a f) = a
2352
2353    Here, the type bound by ``MkFoo`` "escapes", because ``a`` is the
2354    result of ``f1``. One way to see why this is wrong is to ask what
2355    type ``f1`` has: ::
2356
2357          f1 :: Foo -> a             -- Weird!
2358
2359    What is this "``a``" in the result type? Clearly we don't mean this: ::
2360
2361          f1 :: forall a. Foo -> a   -- Wrong!
2362
2363    The original program is just plain wrong. Here's another sort of
2364    error ::
2365
2366          f2 (Baz1 a b) (Baz1 p q) = a==q
2367
2368    It's ok to say ``a==b`` or ``p==q``, but ``a==q`` is wrong because it
2369    equates the two distinct types arising from the two ``Baz1``
2370    constructors.
2371
2372 -  You can't pattern-match on an existentially quantified constructor in
2373    a ``let`` or ``where`` group of bindings. So this is illegal: ::
2374
2375          f3 x = a==b where { Baz1 a b = x }
2376
2377    Instead, use a ``case`` expression: ::
2378
2379          f3 x = case x of Baz1 a b -> a==b
2380
2381    In general, you can only pattern-match on an existentially-quantified
2382    constructor in a ``case`` expression or in the patterns of a function
2383    definition. The reason for this restriction is really an
2384    implementation one. Type-checking binding groups is already a
2385    nightmare without existentials complicating the picture. Also an
2386    existential pattern binding at the top level of a module doesn't make
2387    sense, because it's not clear how to prevent the
2388    existentially-quantified type "escaping". So for now, there's a
2389    simple-to-state restriction. We'll see how annoying it is.
2390
2391 -  You can't use existential quantification for ``newtype``
2392    declarations. So this is illegal: ::
2393
2394          newtype T = forall a. Ord a => MkT a
2395
2396    Reason: a value of type ``T`` must be represented as a pair of a
2397    dictionary for ``Ord t`` and a value of type ``t``. That contradicts
2398    the idea that ``newtype`` should have no concrete representation. You
2399    can get just the same efficiency and effect by using ``data`` instead
2400    of ``newtype``. If there is no overloading involved, then there is
2401    more of a case for allowing an existentially-quantified ``newtype``,
2402    because the ``data`` version does carry an implementation cost, but
2403    single-field existentially quantified constructors aren't much use.
2404    So the simple restriction (no existential stuff on ``newtype``)
2405    stands, unless there are convincing reasons to change it.
2406
2407 -  You can't use ``deriving`` to define instances of a data type with
2408    existentially quantified data constructors. Reason: in most cases it
2409    would not make sense. For example:; ::
2410
2411        data T = forall a. MkT [a] deriving( Eq )
2412
2413    To derive ``Eq`` in the standard way we would need to have equality
2414    between the single component of two ``MkT`` constructors: ::
2415
2416        instance Eq T where
2417          (MkT a) == (MkT b) = ???
2418
2419    But ``a`` and ``b`` have distinct types, and so can't be compared.
2420    It's just about possible to imagine examples in which the derived
2421    instance would make sense, but it seems altogether simpler simply to
2422    prohibit such declarations. Define your own instances!
2423
2424 .. _gadt-style:
2425
2426 Declaring data types with explicit constructor signatures
2427 ---------------------------------------------------------
2428
2429 .. ghc-flag:: -XGADTSyntax
2430
2431     :since: 7.2
2432
2433     Allow the use of GADT syntax in data type definitions (but not GADTs
2434     themselves; for this see :ghc-flag:`-XGADTs`)
2435
2436 When the ``GADTSyntax`` extension is enabled, GHC allows you to declare
2437 an algebraic data type by giving the type signatures of constructors
2438 explicitly. For example: ::
2439
2440       data Maybe a where
2441           Nothing :: Maybe a
2442           Just    :: a -> Maybe a
2443
2444 The form is called a "GADT-style declaration" because Generalised
2445 Algebraic Data Types, described in :ref:`gadt`, can only be declared
2446 using this form.
2447
2448 Notice that GADT-style syntax generalises existential types
2449 (:ref:`existential-quantification`). For example, these two declarations
2450 are equivalent: ::
2451
2452       data Foo = forall a. MkFoo a (a -> Bool)
2453       data Foo' where { MKFoo :: a -> (a->Bool) -> Foo' }
2454
2455 Any data type that can be declared in standard Haskell 98 syntax can
2456 also be declared using GADT-style syntax. The choice is largely
2457 stylistic, but GADT-style declarations differ in one important respect:
2458 they treat class constraints on the data constructors differently.
2459 Specifically, if the constructor is given a type-class context, that
2460 context is made available by pattern matching. For example: ::
2461
2462       data Set a where
2463         MkSet :: Eq a => [a] -> Set a
2464
2465       makeSet :: Eq a => [a] -> Set a
2466       makeSet xs = MkSet (nub xs)
2467
2468       insert :: a -> Set a -> Set a
2469       insert a (MkSet as) | a `elem` as = MkSet as
2470                           | otherwise   = MkSet (a:as)
2471
2472 A use of ``MkSet`` as a constructor (e.g. in the definition of
2473 ``makeSet``) gives rise to a ``(Eq a)`` constraint, as you would expect.
2474 The new feature is that pattern-matching on ``MkSet`` (as in the
2475 definition of ``insert``) makes *available* an ``(Eq a)`` context. In
2476 implementation terms, the ``MkSet`` constructor has a hidden field that
2477 stores the ``(Eq a)`` dictionary that is passed to ``MkSet``; so when
2478 pattern-matching that dictionary becomes available for the right-hand
2479 side of the match. In the example, the equality dictionary is used to
2480 satisfy the equality constraint generated by the call to ``elem``, so
2481 that the type of ``insert`` itself has no ``Eq`` constraint.
2482
2483 For example, one possible application is to reify dictionaries: ::
2484
2485        data NumInst a where
2486          MkNumInst :: Num a => NumInst a
2487
2488        intInst :: NumInst Int
2489        intInst = MkNumInst
2490
2491        plus :: NumInst a -> a -> a -> a
2492        plus MkNumInst p q = p + q
2493
2494 Here, a value of type ``NumInst a`` is equivalent to an explicit
2495 ``(Num a)`` dictionary.
2496
2497 All this applies to constructors declared using the syntax of
2498 :ref:`existential-with-context`. For example, the ``NumInst`` data type
2499 above could equivalently be declared like this: ::
2500
2501        data NumInst a
2502           = Num a => MkNumInst (NumInst a)
2503
2504 Notice that, unlike the situation when declaring an existential, there
2505 is no ``forall``, because the ``Num`` constrains the data type's
2506 universally quantified type variable ``a``. A constructor may have both
2507 universal and existential type variables: for example, the following two
2508 declarations are equivalent: ::
2509
2510        data T1 a
2511         = forall b. (Num a, Eq b) => MkT1 a b
2512        data T2 a where
2513         MkT2 :: (Num a, Eq b) => a -> b -> T2 a
2514
2515 All this behaviour contrasts with Haskell 98's peculiar treatment of
2516 contexts on a data type declaration (Section 4.2.1 of the Haskell 98
2517 Report). In Haskell 98 the definition ::
2518
2519       data Eq a => Set' a = MkSet' [a]
2520
2521 gives ``MkSet'`` the same type as ``MkSet`` above. But instead of
2522 *making available* an ``(Eq a)`` constraint, pattern-matching on
2523 ``MkSet'`` *requires* an ``(Eq a)`` constraint! GHC faithfully
2524 implements this behaviour, odd though it is. But for GADT-style
2525 declarations, GHC's behaviour is much more useful, as well as much more
2526 intuitive.
2527
2528 The rest of this section gives further details about GADT-style data
2529 type declarations.
2530
2531 -  The result type of each data constructor must begin with the type
2532    constructor being defined. If the result type of all constructors has
2533    the form ``T a1 ... an``, where ``a1 ... an`` are distinct type
2534    variables, then the data type is *ordinary*; otherwise is a
2535    *generalised* data type (:ref:`gadt`).
2536
2537 -  As with other type signatures, you can give a single signature for
2538    several data constructors. In this example we give a single signature
2539    for ``T1`` and ``T2``: ::
2540
2541          data T a where
2542            T1,T2 :: a -> T a
2543            T3 :: T a
2544
2545 -  The type signature of each constructor is independent, and is
2546    implicitly universally quantified as usual. In particular, the type
2547    variable(s) in the "``data T a where``" header have no scope, and
2548    different constructors may have different universally-quantified type
2549    variables: ::
2550
2551          data T a where        -- The 'a' has no scope
2552            T1,T2 :: b -> T b   -- Means forall b. b -> T b
2553            T3 :: T a           -- Means forall a. T a
2554
2555 -  A constructor signature may mention type class constraints, which can
2556    differ for different constructors. For example, this is fine: ::
2557
2558          data T a where
2559            T1 :: Eq b => b -> b -> T b
2560            T2 :: (Show c, Ix c) => c -> [c] -> T c
2561
2562    When pattern matching, these constraints are made available to
2563    discharge constraints in the body of the match. For example: ::
2564
2565          f :: T a -> String
2566          f (T1 x y) | x==y      = "yes"
2567                     | otherwise = "no"
2568          f (T2 a b)             = show a
2569
2570    Note that ``f`` is not overloaded; the ``Eq`` constraint arising from
2571    the use of ``==`` is discharged by the pattern match on ``T1`` and
2572    similarly the ``Show`` constraint arising from the use of ``show``.
2573
2574 -  Unlike a Haskell-98-style data type declaration, the type variable(s)
2575    in the "``data Set a where``" header have no scope. Indeed, one can
2576    write a kind signature instead: ::
2577
2578          data Set :: * -> * where ...
2579
2580    or even a mixture of the two: ::
2581
2582          data Bar a :: (* -> *) -> * where ...
2583
2584    The type variables (if given) may be explicitly kinded, so we could
2585    also write the header for ``Foo`` like this: ::
2586
2587          data Bar a (b :: * -> *) where ...
2588
2589 -  You can use strictness annotations, in the obvious places in the
2590    constructor type: ::
2591
2592          data Term a where
2593              Lit    :: !Int -> Term Int
2594              If     :: Term Bool -> !(Term a) -> !(Term a) -> Term a
2595              Pair   :: Term a -> Term b -> Term (a,b)
2596
2597 -  You can use a ``deriving`` clause on a GADT-style data type
2598    declaration. For example, these two declarations are equivalent ::
2599
2600          data Maybe1 a where {
2601              Nothing1 :: Maybe1 a ;
2602              Just1    :: a -> Maybe1 a
2603            } deriving( Eq, Ord )
2604
2605          data Maybe2 a = Nothing2 | Just2 a
2606               deriving( Eq, Ord )
2607
2608 -  The type signature may have quantified type variables that do not
2609    appear in the result type: ::
2610
2611          data Foo where
2612             MkFoo :: a -> (a->Bool) -> Foo
2613             Nil   :: Foo
2614
2615    Here the type variable ``a`` does not appear in the result type of
2616    either constructor. Although it is universally quantified in the type
2617    of the constructor, such a type variable is often called
2618    "existential". Indeed, the above declaration declares precisely the
2619    same type as the ``data Foo`` in :ref:`existential-quantification`.
2620
2621    The type may contain a class context too, of course: ::
2622
2623          data Showable where
2624            MkShowable :: Show a => a -> Showable
2625
2626 -  You can use record syntax on a GADT-style data type declaration: ::
2627
2628          data Person where
2629              Adult :: { name :: String, children :: [Person] } -> Person
2630              Child :: Show a => { name :: !String, funny :: a } -> Person
2631
2632    As usual, for every constructor that has a field ``f``, the type of
2633    field ``f`` must be the same (modulo alpha conversion). The ``Child``
2634    constructor above shows that the signature may have a context,
2635    existentially-quantified variables, and strictness annotations, just
2636    as in the non-record case. (NB: the "type" that follows the
2637    double-colon is not really a type, because of the record syntax and
2638    strictness annotations. A "type" of this form can appear only in a
2639    constructor signature.)
2640
2641 -  Record updates are allowed with GADT-style declarations, only fields
2642    that have the following property: the type of the field mentions no
2643    existential type variables.
2644
2645 -  As in the case of existentials declared using the Haskell-98-like
2646    record syntax (:ref:`existential-records`), record-selector functions
2647    are generated only for those fields that have well-typed selectors.
2648    Here is the example of that section, in GADT-style syntax: ::
2649
2650        data Counter a where
2651            NewCounter :: { _this    :: self
2652                          , _inc     :: self -> self
2653                          , _display :: self -> IO ()
2654                          , tag      :: a
2655                          } -> Counter a
2656
2657    As before, only one selector function is generated here, that for
2658    ``tag``. Nevertheless, you can still use all the field names in
2659    pattern matching and record construction.
2660
2661 -  In a GADT-style data type declaration there is no obvious way to
2662    specify that a data constructor should be infix, which makes a
2663    difference if you derive ``Show`` for the type. (Data constructors
2664    declared infix are displayed infix by the derived ``show``.) So GHC
2665    implements the following design: a data constructor declared in a
2666    GADT-style data type declaration is displayed infix by ``Show`` iff
2667    (a) it is an operator symbol, (b) it has two arguments, (c) it has a
2668    programmer-supplied fixity declaration. For example
2669
2670    ::
2671
2672           infix 6 (:--:)
2673           data T a where
2674             (:--:) :: Int -> Bool -> T Int
2675
2676 .. _gadt:
2677
2678 Generalised Algebraic Data Types (GADTs)
2679 ----------------------------------------
2680
2681 .. ghc-flag:: -XGADTs
2682
2683     :implies: :ghc-flag:`-XMonoLocalBinds`, :ghc-flag:`-XGADTSyntax`
2684
2685     Allow use of Generalised Algebraic Data Types (GADTs).
2686
2687 Generalised Algebraic Data Types generalise ordinary algebraic data
2688 types by allowing constructors to have richer return types. Here is an
2689 example: ::
2690
2691       data Term a where
2692           Lit    :: Int -> Term Int
2693           Succ   :: Term Int -> Term Int
2694           IsZero :: Term Int -> Term Bool
2695           If     :: Term Bool -> Term a -> Term a -> Term a
2696           Pair   :: Term a -> Term b -> Term (a,b)
2697
2698 Notice that the return type of the constructors is not always
2699 ``Term a``, as is the case with ordinary data types. This generality
2700 allows us to write a well-typed ``eval`` function for these ``Terms``: ::
2701
2702       eval :: Term a -> a
2703       eval (Lit i)      = i
2704       eval (Succ t)     = 1 + eval t
2705       eval (IsZero t)   = eval t == 0
2706       eval (If b e1 e2) = if eval b then eval e1 else eval e2
2707       eval (Pair e1 e2) = (eval e1, eval e2)
2708
2709 The key point about GADTs is that *pattern matching causes type
2710 refinement*. For example, in the right hand side of the equation ::
2711
2712       eval :: Term a -> a
2713       eval (Lit i) =  ...
2714
2715 the type ``a`` is refined to ``Int``. That's the whole point! A precise
2716 specification of the type rules is beyond what this user manual aspires
2717 to, but the design closely follows that described in the paper `Simple
2718 unification-based type inference for
2719 GADTs <http://research.microsoft.com/%7Esimonpj/papers/gadt/>`__, (ICFP
2720 2006). The general principle is this: *type refinement is only carried
2721 out based on user-supplied type annotations*. So if no type signature is
2722 supplied for ``eval``, no type refinement happens, and lots of obscure
2723 error messages will occur. However, the refinement is quite general. For
2724 example, if we had: ::
2725
2726       eval :: Term a -> a -> a
2727       eval (Lit i) j =  i+j
2728
2729 the pattern match causes the type ``a`` to be refined to ``Int``
2730 (because of the type of the constructor ``Lit``), and that refinement
2731 also applies to the type of ``j``, and the result type of the ``case``
2732 expression. Hence the addition ``i+j`` is legal.
2733
2734 These and many other examples are given in papers by Hongwei Xi, and Tim
2735 Sheard. There is a longer introduction `on the
2736 wiki <http://www.haskell.org/haskellwiki/GADT>`__, and Ralf Hinze's `Fun
2737 with phantom
2738 types <http://www.cs.ox.ac.uk/ralf.hinze/publications/With.pdf>`__ also
2739 has a number of examples. Note that papers may use different notation to
2740 that implemented in GHC.
2741
2742 The rest of this section outlines the extensions to GHC that support
2743 GADTs. The extension is enabled with :ghc-flag:`-XGADTs`. The :ghc-flag:`-XGADTs` flag
2744 also sets :ghc-flag:`-XGADTSyntax` and :ghc-flag:`-XMonoLocalBinds`.
2745
2746 -  A GADT can only be declared using GADT-style syntax
2747    (:ref:`gadt-style`); the old Haskell 98 syntax for data declarations
2748    always declares an ordinary data type. The result type of each
2749    constructor must begin with the type constructor being defined, but
2750    for a GADT the arguments to the type constructor can be arbitrary
2751    monotypes. For example, in the ``Term`` data type above, the type of
2752    each constructor must end with ``Term ty``, but the ``ty`` need not
2753    be a type variable (e.g. the ``Lit`` constructor).
2754
2755 -  It is permitted to declare an ordinary algebraic data type using
2756    GADT-style syntax. What makes a GADT into a GADT is not the syntax,
2757    but rather the presence of data constructors whose result type is not
2758    just ``T a b``.
2759
2760 -  You cannot use a ``deriving`` clause for a GADT; only for an ordinary
2761    data type.
2762
2763 -  As mentioned in :ref:`gadt-style`, record syntax is supported. For
2764    example:
2765
2766    ::
2767
2768          data Term a where
2769              Lit    :: { val  :: Int }      -> Term Int
2770              Succ   :: { num  :: Term Int } -> Term Int
2771              Pred   :: { num  :: Term Int } -> Term Int
2772              IsZero :: { arg  :: Term Int } -> Term Bool
2773              Pair   :: { arg1 :: Term a
2774                        , arg2 :: Term b
2775                        }                    -> Term (a,b)
2776              If     :: { cnd  :: Term Bool
2777                        , tru  :: Term a
2778                        , fls  :: Term a
2779                        }                    -> Term a
2780
2781    However, for GADTs there is the following additional constraint:
2782    every constructor that has a field ``f`` must have the same result
2783    type (modulo alpha conversion) Hence, in the above example, we cannot
2784    merge the ``num`` and ``arg`` fields above into a single name.
2785    Although their field types are both ``Term Int``, their selector
2786    functions actually have different types:
2787
2788    ::
2789
2790          num :: Term Int -> Term Int
2791          arg :: Term Bool -> Term Int
2792
2793 -  When pattern-matching against data constructors drawn from a GADT,
2794    for example in a ``case`` expression, the following rules apply:
2795
2796    -  The type of the scrutinee must be rigid.
2797
2798    -  The type of the entire ``case`` expression must be rigid.
2799
2800    -  The type of any free variable mentioned in any of the ``case``
2801       alternatives must be rigid.
2802
2803    A type is "rigid" if it is completely known to the compiler at its
2804    binding site. The easiest way to ensure that a variable a rigid type
2805    is to give it a type signature. For more precise details see `Simple
2806    unification-based type inference for
2807    GADTs <http://research.microsoft.com/%7Esimonpj/papers/gadt>`__. The
2808    criteria implemented by GHC are given in the Appendix.
2809
2810 .. _record-system-extensions:
2811
2812 Extensions to the record system
2813 ===============================
2814
2815 .. _traditional-record-syntax:
2816
2817 Traditional record syntax
2818 -------------------------
2819
2820 .. ghc-flag:: -XNoTraditionalRecordSyntax
2821
2822     :since: 7.4.1
2823
2824     Disallow use of record syntax.
2825
2826 Traditional record syntax, such as ``C {f = x}``, is enabled by default.
2827 To disable it, you can use the :ghc-flag:`-XNoTraditionalRecordSyntax` flag.
2828
2829 .. _disambiguate-fields:
2830
2831 Record field disambiguation
2832 ---------------------------
2833
2834 .. ghc-flag:: -XDisambiguateRecordFields
2835
2836     Allow the compiler to automatically choose between identically-named
2837     record selectors based on type (if the choice is unambiguous).
2838
2839 In record construction and record pattern matching it is entirely
2840 unambiguous which field is referred to, even if there are two different
2841 data types in scope with a common field name. For example:
2842
2843 ::
2844
2845     module M where
2846       data S = MkS { x :: Int, y :: Bool }
2847
2848     module Foo where
2849       import M
2850
2851       data T = MkT { x :: Int }
2852
2853       ok1 (MkS { x = n }) = n+1   -- Unambiguous
2854       ok2 n = MkT { x = n+1 }     -- Unambiguous
2855
2856       bad1 k = k { x = 3 }        -- Ambiguous
2857       bad2 k = x k                -- Ambiguous
2858
2859 Even though there are two ``x``'s in scope, it is clear that the ``x``
2860 in the pattern in the definition of ``ok1`` can only mean the field
2861 ``x`` from type ``S``. Similarly for the function ``ok2``. However, in
2862 the record update in ``bad1`` and the record selection in ``bad2`` it is
2863 not clear which of the two types is intended.
2864
2865 Haskell 98 regards all four as ambiguous, but with the
2866 :ghc-flag:`-XDisambiguateRecordFields` flag, GHC will accept the former two. The
2867 rules are precisely the same as those for instance declarations in
2868 Haskell 98, where the method names on the left-hand side of the method
2869 bindings in an instance declaration refer unambiguously to the method of
2870 that class (provided they are in scope at all), even if there are other
2871 variables in scope with the same name. This reduces the clutter of
2872 qualified names when you import two records from different modules that
2873 use the same field name.
2874
2875 Some details:
2876
2877 -  Field disambiguation can be combined with punning (see
2878    :ref:`record-puns`). For example: ::
2879
2880        module Foo where
2881          import M
2882          x=True
2883          ok3 (MkS { x }) = x+1   -- Uses both disambiguation and punning
2884
2885 -  With :ghc-flag:`-XDisambiguateRecordFields` you can use *unqualified* field
2886    names even if the corresponding selector is only in scope *qualified*
2887    For example, assuming the same module ``M`` as in our earlier
2888    example, this is legal: ::
2889
2890        module Foo where
2891          import qualified M    -- Note qualified
2892
2893          ok4 (M.MkS { x = n }) = n+1   -- Unambiguous
2894
2895    Since the constructor ``MkS`` is only in scope qualified, you must
2896    name it ``M.MkS``, but the field ``x`` does not need to be qualified
2897    even though ``M.x`` is in scope but ``x`` is not (In effect, it is
2898    qualified by the constructor).
2899
2900 .. _duplicate-record-fields:
2901
2902 Duplicate record fields
2903 -----------------------
2904
2905 .. ghc-flag:: -XDuplicateRecordFields
2906
2907     :implies: :ghc-flag:`-XDisambiguateRecordFields`
2908     :since: 8.0.1
2909
2910     Allow definition of record types with identically-named fields.
2911
2912 Going beyond :ghc-flag:`-XDisambiguateRecordFields` (see :ref:`disambiguate-fields`),
2913 the :ghc-flag:`-XDuplicateRecordFields` extension allows multiple datatypes to be
2914 declared using the same field names in a single module. For example, it allows
2915 this: ::
2916
2917     module M where
2918       data S = MkS { x :: Int }
2919       data T = MkT { x :: Bool }
2920
2921 Uses of fields that are always unambiguous because they mention the constructor,
2922 including construction and pattern-matching, may freely use duplicated field
2923 names. For example, the following are permitted (just as with
2924 :ghc-flag:`-XDisambiguateRecordFields`): ::
2925
2926     s = MkS { x = 3 }
2927
2928     f (MkT { x = b }) = b
2929
2930 Field names used as selector functions or in record updates must be unambiguous,
2931 either because there is only one such field in scope, or because a type
2932 signature is supplied, as described in the following sections.
2933
2934 Selector functions
2935 ~~~~~~~~~~~~~~~~~~
2936
2937 Fields may be used as selector functions only if they are unambiguous, so this
2938 is still not allowed if both ``S(x)`` and ``T(x)`` are in scope: ::
2939
2940     bad r = x r
2941
2942 An ambiguous selector may be disambiguated by the type being "pushed down" to
2943 the occurrence of the selector (see :ref:`higher-rank-type-inference` for more
2944 details on what "pushed down" means). For example, the following are permitted: ::
2945
2946     ok1 = x :: S -> Int
2947
2948     ok2 :: S -> Int
2949     ok2 = x
2950
2951     ok3 = k x -- assuming we already have k :: (S -> Int) -> _
2952
2953 In addition, the datatype that is meant may be given as a type signature on the
2954 argument to the selector: ::
2955
2956     ok4 s = x (s :: S)
2957
2958 However, we do not infer the type of the argument to determine the datatype, or
2959 have any way of deferring the choice to the constraint solver. Thus the
2960 following is ambiguous: ::
2961
2962     bad :: S -> Int
2963     bad s = x s
2964
2965 Even though a field label is duplicated in its defining module, it may be
2966 possible to use the selector unambiguously elsewhere. For example, another
2967 module could import ``S(x)`` but not ``T(x)``, and then use ``x`` unambiguously.
2968
2969 Record updates
2970 ~~~~~~~~~~~~~~
2971
2972 In a record update such as ``e { x = 1 }``, if there are multiple ``x`` fields
2973 in scope, then the type of the context must fix which record datatype is
2974 intended, or a type annotation must be supplied. Consider the following
2975 definitions: ::
2976
2977     data S = MkS { foo :: Int }
2978     data T = MkT { foo :: Int, bar :: Int }
2979     data U = MkU { bar :: Int, baz :: Int }
2980
2981 Without :ghc-flag:`-XDuplicateRecordFields`, an update mentioning ``foo`` will always be
2982 ambiguous if all these definitions were in scope. When the extension is enabled,
2983 there are several options for disambiguating updates:
2984
2985 - Check for types that have all the fields being updated. For example: ::
2986
2987       f x = x { foo = 3, bar = 2 }
2988
2989   Here ``f`` must be updating ``T`` because neither ``S`` nor ``U`` have both
2990   fields.
2991
2992 - Use the type being pushed in to the record update, as in the following: ::
2993
2994       g1 :: T -> T
2995       g1 x = x { foo = 3 }
2996
2997       g2 x = x { foo = 3 } :: T
2998
2999       g3 = k (x { foo = 3 }) -- assuming we already have k :: T -> _
3000
3001 - Use an explicit type signature on the record expression, as in: ::
3002
3003       h x = (x :: T) { foo = 3 }
3004
3005 The type of the expression being updated will not be inferred, and no
3006 constraint-solving will be performed, so the following will be rejected as
3007 ambiguous: ::
3008
3009     let x :: T
3010         x = blah
3011     in x { foo = 3 }
3012
3013     \x -> [x { foo = 3 },  blah :: T ]
3014
3015     \ (x :: T) -> x { foo = 3 }
3016
3017 Import and export of record fields
3018 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3019
3020 When :ghc-flag:`-XDuplicateRecordFields` is enabled, an ambiguous field must be exported
3021 as part of its datatype, rather than at the top level. For example, the
3022 following is legal: ::
3023
3024     module M (S(x), T(..)) where
3025       data S = MkS { x :: Int }
3026       data T = MkT { x :: Bool }
3027
3028 However, this would not be permitted, because ``x`` is ambiguous: ::
3029
3030     module M (x) where ...
3031
3032 Similar restrictions apply on import.
3033
3034 .. _record-puns:
3035
3036 Record puns
3037 -----------
3038
3039 .. ghc-flag:: -XNamedFieldPuns
3040
3041     Allow use of record puns.
3042
3043 Record puns are enabled by the flag :ghc-flag:`-XNamedFieldPuns`.
3044
3045 When using records, it is common to write a pattern that binds a
3046 variable with the same name as a record field, such as: ::
3047
3048     data C = C {a :: Int}
3049     f (C {a = a}) = a
3050
3051 Record punning permits the variable name to be elided, so one can simply
3052 write ::
3053
3054     f (C {a}) = a
3055
3056 to mean the same pattern as above. That is, in a record pattern, the
3057 pattern ``a`` expands into the pattern ``a = a`` for the same name
3058 ``a``.
3059
3060 Note that:
3061
3062 -  Record punning can also be used in an expression, writing, for
3063    example, ::
3064
3065        let a = 1 in C {a}
3066
3067    instead of ::
3068
3069        let a = 1 in C {a = a}
3070
3071    The expansion is purely syntactic, so the expanded right-hand side
3072    expression refers to the nearest enclosing variable that is spelled
3073    the same as the field name.
3074
3075 -  Puns and other patterns can be mixed in the same record: ::
3076
3077        data C = C {a :: Int, b :: Int}
3078        f (C {a, b = 4}) = a
3079
3080 -  Puns can be used wherever record patterns occur (e.g. in ``let``
3081    bindings or at the top-level).
3082
3083 -  A pun on a qualified field name is expanded by stripping off the
3084    module qualifier. For example: ::
3085
3086        f (C {M.a}) = a
3087
3088    means ::
3089
3090        f (M.C {M.a = a}) = a
3091
3092    (This is useful if the field selector ``a`` for constructor ``M.C``
3093    is only in scope in qualified form.)
3094
3095 .. _record-wildcards:
3096
3097 Record wildcards
3098 ----------------
3099
3100 .. ghc-flag:: -XRecordWildCards
3101
3102     :implies: :ghc-flag:`-XDisambiguateRecordFields`.
3103
3104     Allow the use of wildcards in record construction and pattern matching.
3105
3106 Record wildcards are enabled by the flag :ghc-flag:`-XRecordWildCards`. This
3107 flag implies :ghc-flag:`-XDisambiguateRecordFields`.
3108
3109 For records with many fields, it can be tiresome to write out each field
3110 individually in a record pattern, as in ::
3111
3112     data C = C {a :: Int, b :: Int, c :: Int, d :: Int}
3113     f (C {a = 1, b = b, c = c, d = d}) = b + c + d
3114
3115 Record wildcard syntax permits a "``..``" in a record pattern, where
3116 each elided field ``f`` is replaced by the pattern ``f = f``. For
3117 example, the above pattern can be written as ::
3118
3119     f (C {a = 1, ..}) = b + c + d
3120
3121 More details:
3122
3123 -  Record wildcards in patterns can be mixed with other patterns,
3124    including puns (:ref:`record-puns`); for example, in a pattern
3125    ``(C {a = 1, b, ..})``. Additionally, record wildcards can be used
3126    wherever record patterns occur, including in ``let`` bindings and at
3127    the top-level. For example, the top-level binding ::
3128
3129        C {a = 1, ..} = e
3130
3131    defines ``b``, ``c``, and ``d``.
3132
3133 -  Record wildcards can also be used in an expression, when constructing
3134    a record. For example, ::
3135
3136        let {a = 1; b = 2; c = 3; d = 4} in C {..}
3137
3138    in place of ::
3139
3140        let {a = 1; b = 2; c = 3; d = 4} in C {a=a, b=b, c=c, d=d}
3141
3142    The expansion is purely syntactic, so the record wildcard expression
3143    refers to the nearest enclosing variables that are spelled the same
3144    as the omitted field names.
3145
3146 -  Record wildcards may *not* be used in record *updates*. For example
3147    this is illegal: ::
3148
3149        f r = r { x = 3, .. }
3150
3151 -  For both pattern and expression wildcards, the "``..``" expands to
3152    the missing *in-scope* record fields. Specifically the expansion of
3153    "``C {..}``" includes ``f`` if and only if:
3154
3155    -  ``f`` is a record field of constructor ``C``.
3156
3157    -  The record field ``f`` is in scope somehow (either qualified or
3158       unqualified).
3159
3160    -  In the case of expressions (but not patterns), the variable ``f``
3161       is in scope unqualified, and is not imported or bound at top level.
3162       For example, ``f`` can be bound by an enclosing pattern match or
3163       let/where-binding.  (The motivation here is that it should be
3164       easy for the reader to figure out what the "``..``" expands to.)
3165
3166    These rules restrict record wildcards to the situations in which the
3167    user could have written the expanded version. For example ::
3168
3169        module M where
3170          data R = R { a,b,c :: Int }
3171        module X where
3172          import M( R(a,c) )
3173          f b = R { .. }
3174
3175    The ``R{..}`` expands to ``R{M.a=a}``, omitting ``b`` since the
3176    record field is not in scope, and omitting ``c`` since the variable
3177    ``c`` is not in scope (apart from the binding of the record selector
3178    ``c``, of course).
3179
3180 -  Record wildcards cannot be used (a) in a record update construct, and
3181    (b) for data constructors that are not declared with record fields.
3182    For example: ::
3183
3184        f x = x { v=True, .. }   -- Illegal (a)
3185
3186        data T = MkT Int Bool
3187        g = MkT { .. }           -- Illegal (b)
3188        h (MkT { .. }) = True    -- Illegal (b)
3189
3190 .. _deriving:
3191
3192 Extensions to the "deriving" mechanism
3193 ======================================
3194
3195 .. _deriving-inferred:
3196
3197 Inferred context for deriving clauses
3198 -------------------------------------
3199
3200 The Haskell Report is vague about exactly when a ``deriving`` clause is
3201 legal. For example: ::
3202
3203       data T0 f a = MkT0 a         deriving( Eq )
3204       data T1 f a = MkT1 (f a)     deriving( Eq )
3205       data T2 f a = MkT2 (f (f a)) deriving( Eq )
3206
3207 The natural generated ``Eq`` code would result in these instance
3208 declarations: ::
3209
3210       instance Eq a         => Eq (T0 f a) where ...
3211       instance Eq (f a)     => Eq (T1 f a) where ...
3212       instance Eq (f (f a)) => Eq (T2 f a) where ...
3213
3214 The first of these is obviously fine. The second is still fine, although
3215 less obviously. The third is not Haskell 98, and risks losing
3216 termination of instances.
3217
3218 GHC takes a conservative position: it accepts the first two, but not the
3219 third. The rule is this: each constraint in the inferred instance
3220 context must consist only of type variables, with no repetitions.
3221
3222 This rule is applied regardless of flags. If you want a more exotic
3223 context, you can write it yourself, using the `standalone deriving
3224 mechanism <#stand-alone-deriving>`__.
3225
3226 .. _stand-alone-deriving:
3227
3228 Stand-alone deriving declarations
3229 ---------------------------------
3230
3231 .. ghc-flag:: -XStandaloneDeriving
3232
3233     Allow the use of stand-alone ``deriving`` declarations.
3234
3235 GHC allows stand-alone ``deriving`` declarations, enabled by
3236 :ghc-flag:`-XStandaloneDeriving`: ::
3237
3238       data Foo a = Bar a | Baz String
3239
3240       deriving instance Eq a => Eq (Foo a)
3241
3242 The syntax is identical to that of an ordinary instance declaration
3243 apart from (a) the keyword ``deriving``, and (b) the absence of the
3244 ``where`` part.
3245
3246 However, standalone deriving differs from a ``deriving`` clause in a
3247 number of important ways:
3248
3249 -  The standalone deriving declaration does not need to be in the same
3250    module as the data type declaration. (But be aware of the dangers of
3251    orphan instances (:ref:`orphan-modules`).
3252
3253 -  You must supply an explicit context (in the example the context is
3254    ``(Eq a)``), exactly as you would in an ordinary instance
3255    declaration. (In contrast, in a ``deriving`` clause attached to a
3256    data type declaration, the context is inferred.)
3257
3258 -  Unlike a ``deriving`` declaration attached to a ``data`` declaration,
3259    the instance can be more specific than the data type (assuming you
3260    also use :ghc-flag:`-XFlexibleInstances`, :ref:`instance-rules`). Consider
3261    for example ::
3262
3263          data Foo a = Bar a | Baz String
3264
3265          deriving instance Eq a => Eq (Foo [a])
3266          deriving instance Eq a => Eq (Foo (Maybe a))
3267
3268    This will generate a derived instance for ``(Foo [a])`` and
3269    ``(Foo (Maybe a))``, but other types such as ``(Foo (Int,Bool))``
3270    will not be an instance of ``Eq``.
3271
3272 -  Unlike a ``deriving`` declaration attached to a ``data`` declaration,
3273    GHC does not restrict the form of the data type. Instead, GHC simply
3274    generates the appropriate boilerplate code for the specified class,
3275    and typechecks it. If there is a type error, it is your problem. (GHC
3276    will show you the offending code if it has a type error.)
3277
3278    The merit of this is that you can derive instances for GADTs and
3279    other exotic data types, providing only that the boilerplate code
3280    does indeed typecheck. For example: ::
3281
3282          data T a where
3283             T1 :: T Int
3284             T2 :: T Bool
3285
3286          deriving instance Show (T a)
3287
3288    In this example, you cannot say ``... deriving( Show )`` on the data
3289    type declaration for ``T``, because ``T`` is a GADT, but you *can*
3290    generate the instance declaration using stand-alone deriving.
3291
3292    The down-side is that, if the boilerplate code fails to typecheck,
3293    you will get an error message about that code, which you did not
3294    write. Whereas, with a ``deriving`` clause the side-conditions are
3295    necessarily more conservative, but any error message may be more
3296    comprehensible.
3297
3298 -  Under most circumstances, you cannot use standalone deriving to create an
3299    instance for a data type whose constructors are not all in scope. This is
3300    because the derived instance would generate code that uses the constructors
3301    behind the scenes, which would break abstraction.
3302
3303    The one exception to this rule is :ghc-flag:`-XDeriveAnyClass`, since
3304    deriving an instance via :ghc-flag:`-XDeriveAnyClass` simply generates
3305    an empty instance declaration, which does not require the use of any
3306    constructors. See the `deriving any class <#derive-any-class>`__ section
3307    for more details.
3308
3309 In other ways, however, a standalone deriving obeys the same rules as
3310 ordinary deriving:
3311
3312 -  A ``deriving instance`` declaration must obey the same rules
3313    concerning form and termination as ordinary instance declarations,
3314    controlled by the same flags; see :ref:`instance-decls`.
3315
3316 -  The stand-alone syntax is generalised for newtypes in exactly the
3317    same way that ordinary ``deriving`` clauses are generalised
3318    (:ref:`newtype-deriving`). For example: ::
3319
3320          newtype Foo a = MkFoo (State Int a)
3321
3322          deriving instance MonadState Int Foo
3323
3324    GHC always treats the *last* parameter of the instance (``Foo`` in
3325    this example) as the type whose instance is being derived.
3326
3327 .. _deriving-extra:
3328
3329 Deriving instances of extra classes (``Data``, etc.)
3330 ----------------------------------------------------
3331
3332 .. ghc-flag:: -XDeriveGeneric
3333
3334     :since: 7.2
3335
3336     Allow automatic deriving of instances for the ``Generic`` typeclass.
3337
3338 .. ghc-flag:: -XDeriveFunctor
3339
3340     :since: 6.12
3341
3342     Allow automatic deriving of instances for the ``Functor`` typeclass.
3343
3344 .. ghc-flag:: -XDeriveFoldable
3345
3346     :since: 6.12
3347
3348     Allow automatic deriving of instances for the ``Foldable`` typeclass.
3349
3350 .. ghc-flag:: -XDeriveTraversable
3351
3352     :since: 6.12
3353
3354     :implies: :ghc-flag:`-XDeriveFoldable`, :ghc-flag:`-XDeriveFunctor`
3355
3356     Allow automatic deriving of instances for the ``Traversable`` typeclass.
3357
3358 Haskell 98 allows the programmer to add "``deriving( Eq, Ord )``" to a
3359 data type declaration, to generate a standard instance declaration for
3360 classes specified in the ``deriving`` clause. In Haskell 98, the only
3361 classes that may appear in the ``deriving`` clause are the standard
3362 classes ``Eq``, ``Ord``, ``Enum``, ``Ix``, ``Bounded``, ``Read``, and
3363 ``Show``.
3364
3365 GHC extends this list with several more classes that may be
3366 automatically derived:
3367
3368 -  With :ghc-flag:`-XDeriveGeneric`, you can derive instances of the classes
3369    ``Generic`` and ``Generic1``, defined in ``GHC.Generics``. You can
3370    use these to define generic functions, as described in
3371    :ref:`generic-programming`.
3372
3373 -  With :ghc-flag:`-XDeriveFunctor`, you can derive instances of the class
3374    ``Functor``, defined in ``GHC.Base``. See :ref:`deriving-functor`.
3375
3376 -  With :ghc-flag:`-XDeriveDataTypeable`, you can derive instances of the class
3377    ``Data``, defined in ``Data.Data``. See :ref:`deriving-typeable` for
3378    deriving ``Typeable``.
3379
3380 -  With :ghc-flag:`-XDeriveFoldable`, you can derive instances of the class
3381    ``Foldable``, defined in ``Data.Foldable``. See
3382    :ref:`deriving-foldable`.
3383
3384 -  With :ghc-flag:`-XDeriveTraversable`, you can derive instances of the class
3385    ``Traversable``, defined in ``Data.Traversable``. Since the
3386    ``Traversable`` instance dictates the instances of ``Functor`` and
3387    ``Foldable``, you'll probably want to derive them too, so
3388    :ghc-flag:`-XDeriveTraversable` implies :ghc-flag:`-XDeriveFunctor` and
3389    :ghc-flag:`-XDeriveFoldable`. See :ref:`deriving-traversable`.
3390
3391 -  With :ghc-flag:`-XDeriveLift`, you can derive instances of the class ``Lift``,
3392    defined in the ``Language.Haskell.TH.Syntax`` module of the
3393    ``template-haskell`` package. See :ref:`deriving-lift`.
3394
3395 You can also use a standalone deriving declaration instead (see
3396 :ref:`stand-alone-deriving`).
3397
3398 In each case the appropriate class must be in scope before it can be
3399 mentioned in the ``deriving`` clause.
3400
3401 .. _deriving-functor:
3402
3403 Deriving ``Functor`` instances
3404 ------------------------------
3405
3406 With :ghc-flag:`-XDeriveFunctor`, one can derive ``Functor`` instances for data types
3407 of kind ``* -> *``. For example, this declaration::
3408
3409     data Example a = Ex a Char (Example a) (Example Char)
3410       deriving Functor
3411
3412 would generate the following instance: ::
3413
3414     instance Functor Example where
3415       fmap f (Ex a1 a2 a3 a4) = Ex (f a1) a2 (fmap f a3) a4
3416
3417 The basic algorithm for :ghc-flag:`-XDeriveFunctor` walks the arguments of each
3418 constructor of a data type, applying a mapping function depending on the type
3419 of each argument. If a plain type variable is found that is syntactically
3420 equivalent to the last type parameter of the data type (``a`` in the above
3421 example), then we apply the function ``f`` directly to it. If a type is
3422 encountered that is not syntactically equivalent to the last type parameter
3423 *but does mention* the last type parameter somewhere in it, then a recursive
3424 call to ``fmap`` is made. If a type is found which doesn't mention the last
3425 type parameter at all, then it is left alone.
3426
3427 The second of those cases, in which a type is unequal to the type parameter but
3428 does contain the type parameter, can be surprisingly tricky. For example, the
3429 following example compiles::
3430
3431     newtype Right a = Right (Either Int a) deriving Functor
3432
3433 Modifying the code slightly, however, produces code which will not compile::
3434
3435     newtype Wrong a = Wrong (Either a Int) deriving Functor
3436
3437 The difference involves the placement of the last type parameter, ``a``. In the
3438 ``Right`` case, ``a`` occurs within the type ``Either Int a``, and moreover, it
3439 appears as the last type argument of ``Either``. In the ``Wrong`` case,
3440 however, ``a`` is not the last type argument to ``Either``; rather, ``Int`` is.
3441
3442 This distinction is important because of the way :ghc-flag:`-XDeriveFunctor` works. The
3443 derived ``Functor Right`` instance would be::
3444
3445     instance Functor Right where
3446       fmap f (Right a) = Right (fmap f a)
3447
3448 Given a value of type ``Right a``, GHC must produce a value of type
3449 ``Right b``. Since the argument to the ``Right`` constructor has type
3450 ``Either Int a``, the code recursively calls ``fmap`` on it to produce a value
3451 of type ``Either Int b``, which is used in turn to construct a final value of
3452 type ``Right b``.
3453
3454 The generated code for the ``Functor Wrong`` instance would look exactly the
3455 same, except with ``Wrong`` replacing every occurrence of ``Right``. The
3456 problem is now that ``fmap`` is being applied recursively to a value of type
3457 ``Either a Int``. This cannot possibly produce a value of type
3458 ``Either b Int``, as ``fmap`` can only change the last type parameter! This
3459 causes the generated code to be ill-typed.
3460
3461 As a general rule, if a data type has a derived ``Functor`` instance and its
3462 last type parameter occurs on the right-hand side of the data declaration, then
3463 either it must (1) occur bare (e.g., ``newtype Id a = a``), or (2) occur as the
3464 last argument of a type constructor (as in ``Right`` above).
3465
3466 There are two exceptions to this rule:
3467
3468 #. Tuple types. When a non-unit tuple is used on the right-hand side of a data
3469    declaration, :ghc-flag:`-XDeriveFunctor` treats it as a product of distinct types.
3470    In other words, the following code::
3471
3472        newtype Triple a = Triple (a, Int, [a]) deriving Functor
3473
3474    Would result in a generated ``Functor`` instance like so::
3475
3476        instance Functor Triple where
3477          fmap f (Triple a) =
3478            Triple (case a of
3479                         (a1, a2, a3) -> (f a1, a2, fmap f a3))
3480
3481    That is, :ghc-flag:`-XDeriveFunctor` pattern-matches its way into tuples and maps
3482    over each type that constitutes the tuple. The generated code is
3483    reminiscient of what would be generated from
3484    ``data Triple a = Triple a Int [a]``, except with extra machinery to handle
3485    the tuple.
3486
3487 #. Function types. The last type parameter can appear anywhere in a function
3488    type as long as it occurs in a *covariant* position. To illustrate what this
3489    means, consider the following three examples::
3490
3491        newtype CovFun1 a = CovFun1 (Int -> a) deriving Functor
3492        newtype CovFun2 a = CovFun2 ((a -> Int) -> a) deriving Functor
3493        newtype CovFun3 a = CovFun3 (((Int -> a) -> Int) -> a) deriving Functor
3494
3495    All three of these examples would compile without issue. On the other hand::
3496
3497        newtype ContraFun1 a = ContraFun1 (a -> Int) deriving Functor
3498        newtype ContraFun2 a = ContraFun2 ((Int -> a) -> Int) deriving Functor
3499        newtype ContraFun3 a = ContraFun3 (((a -> Int) -> a) -> Int) deriving Functor
3500
3501    While these examples look similar, none of them would successfully compile.
3502    This is because all occurrences of the last type parameter ``a`` occur in *contravariant* positions, not covariant ones.
3503
3504    Intuitively, a covariant type is *produced*, and a contravariant type is
3505    *consumed*. Most types in Haskell are covariant, but the function type is
3506    special in that the lefthand side of a function arrow reverses variance. If
3507    a function type ``a -> b`` appears in a covariant position (e.g.,
3508    ``CovFun1`` above), then ``a`` is in a contravariant position and ``b`` is
3509    in a covariant position. Similarly, if ``a -> b`` appears in a contravariant
3510    position (e.g., ``CovFun2`` above), then ``a`` is in ``a`` covariant
3511    position and ``b`` is in a contravariant position.
3512
3513    To see why a data type with a contravariant occurrence of its last type
3514    parameter cannot have a derived ``Functor`` instance, let's suppose that a
3515    ``Functor ContraFun1`` instance exists. The implementation would look
3516    something like this::
3517
3518        instance Functor ContraFun1 where
3519          fmap f (ContraFun g) = ContraFun (\x -> _)
3520
3521    We have ``f :: a -> b``, ``g :: a -> Int``, and ``x :: b``. Using these, we
3522    must somehow fill in the hole (denoted with an underscore) with a value of
3523    type ``Int``. What are our options?
3524
3525    We could try applying ``g`` to ``x``. This won't work though, as ``g``
3526    expects an argument of type ``a``, and ``x :: b``. Even worse, we can't turn
3527    ``x`` into something of type ``a``, since ``f`` also needs an argument of
3528    type ``a``! In short, there's no good way to make this work.
3529
3530    On the other hand, a derived ``Functor`` instances for the ``CovFun``\ s are
3531    within the realm of possibility::
3532
3533        instance Functor CovFun1 where
3534          fmap f (CovFun1 g) = CovFun1 (\x -> f (g x))
3535
3536        instance Functor CovFun2 where
3537          fmap f (CovFun2 g) = CovFun2 (\h -> f (g (\x -> h (f x))))
3538
3539        instance Functor CovFun3 where
3540          fmap f (CovFun3 g) = CovFun3 (\h -> f (g (\k -> h (\x -> f (k x)))))
3541
3542 There are some other scenarios in which a derived ``Functor`` instance will
3543 fail to compile:
3544
3545 #. A data type has no type parameters (e.g., ``data Nothing = Nothing``).
3546
3547 #. A data type's last type variable is used in a :ghc-flag:`-XDatatypeContexts`
3548    constraint (e.g., ``data Ord a => O a = O a``).
3549
3550 #. A data type's last type variable is used in an
3551    :ghc-flag:`-XExistentialQuantification` constraint, or is refined in a GADT. For
3552    example, ::
3553
3554        data T a b where
3555            T4 :: Ord b => b -> T a b
3556            T5 :: b -> T b b
3557            T6 :: T a (b,b)
3558
3559        deriving instance Functor (T a)
3560
3561    would not compile successfully due to the way in which ``b`` is constrained.
3562
3563 .. _deriving-foldable:
3564
3565 Deriving ``Foldable`` instances
3566 -------------------------------
3567
3568 With :ghc-flag:`-XDeriveFoldable`, one can derive ``Foldable`` instances for data types
3569 of kind ``* -> *``. For example, this declaration::
3570
3571     data Example a = Ex a Char (Example a) (Example Char)
3572       deriving Foldable
3573
3574 would generate the following instance::
3575
3576     instance Foldable Example where
3577       foldr f z (Ex a1 a2 a3 a4) = f a1 (foldr f z a3)
3578       foldMap f (Ex a1 a2 a3 a4) = mappend (f a1) (foldMap f a3)
3579
3580 The algorithm for :ghc-flag:`-XDeriveFoldable` is adapted from the :ghc-flag:`-XDeriveFunctor`
3581 algorithm, but it generates definitions for ``foldMap`` and ``foldr`` instead
3582 of ``fmap``. In addition, :ghc-flag:`-XDeriveFoldable` filters out all
3583 constructor arguments on the RHS expression whose types do not mention the last
3584 type parameter, since those arguments do not need to be folded over.
3585
3586 Here are the differences between the generated code in each extension:
3587
3588 #. When a bare type variable ``a`` is encountered, :ghc-flag:`-XDeriveFunctor` would
3589    generate ``f a`` for an ``fmap`` definition. :ghc-flag:`-XDeriveFoldable` would
3590    generate ``f a z`` for ``foldr``, and ``f a`` for ``foldMap``.
3591
3592 #. When a type that is not syntactically equivalent to ``a``, but which does
3593    contain ``a``, is encountered, :ghc-flag:`-XDeriveFunctor` recursively calls
3594    ``fmap`` on it. Similarly, :ghc-flag:`-XDeriveFoldable` would recursively call
3595    ``foldr`` and ``foldMap``.
3596
3597 #. :ghc-flag:`-XDeriveFunctor` puts everything back together again at the end by
3598    invoking the constructor. :ghc-flag:`-XDeriveFoldable`, however, builds up a value
3599    of some type. For ``foldr``, this is accomplished by chaining applications
3600    of ``f`` and recursive ``foldr`` calls on the state value ``z``. For
3601    ``foldMap``, this happens by combining all values with ``mappend``.
3602
3603 There are some other differences regarding what data types can have derived
3604 ``Foldable`` instances:
3605
3606 #. Data types containing function types on the right-hand side cannot have
3607    derived ``Foldable`` instances.
3608
3609 #. ``Foldable`` instances can be derived for data types in which the last type
3610    parameter is existentially constrained or refined in a GADT. For example,
3611    this data type::
3612
3613        data E a where
3614            E1 :: (a ~ Int) => a   -> E a
3615            E2 ::              Int -> E Int
3616            E3 :: (a ~ Int) => a   -> E Int
3617            E4 :: (a ~ Int) => Int -> E a
3618
3619        deriving instance Foldable E
3620
3621    would have the following generated ``Foldable`` instance::
3622
3623        instance Foldable E where
3624            foldr f z (E1 e) = f e z
3625            foldr f z (E2 e) = z
3626            foldr f z (E3 e) = z
3627            foldr f z (E4 e) = z
3628
3629            foldMap f (E1 e) = f e
3630            foldMap f (E2 e) = mempty
3631            foldMap f (E3 e) = mempty
3632            foldMap f (E4 e) = mempty
3633
3634    Notice how every constructor of ``E`` utilizes some sort of existential
3635    quantification, but only the argument of ``E1`` is actually "folded over".
3636    This is because we make a deliberate choice to only fold over universally
3637    polymorphic types that are syntactically equivalent to the last type
3638    parameter. In particular:
3639
3640   -  We don't fold over the arguments of ``E1`` or ``E4`` beacause even though
3641      ``(a ~ Int)``, ``Int`` is not syntactically equivalent to ``a``.
3642
3643   -  We don't fold over the argument of ``E3`` because ``a`` is not universally
3644      polymorphic. The ``a`` in ``E3`` is (implicitly) existentially quantified,
3645      so it is not the same as the last type parameter of ``E``.
3646
3647 .. _deriving-traversable:
3648
3649 Deriving ``Traversable`` instances
3650 ----------------------------------
3651
3652 With :ghc-flag:`-XDeriveTraversable`, one can derive ``Traversable`` instances for data
3653 types of kind ``* -> *``. For example, this declaration::
3654
3655     data Example a = Ex a Char (Example a) (Example Char)
3656       deriving (Functor, Foldable, Traversable)
3657
3658 would generate the following ``Traversable`` instance::
3659
3660     instance Traversable Example where
3661       traverse f (Ex a1 a2 a3 a4)
3662         = fmap (\b1 b3 -> Ex b1 a2 b3 a4) (f a1) <*> traverse f a3
3663
3664 The algorithm for :ghc-flag:`-XDeriveTraversable` is adapted from the
3665 :ghc-flag:`-XDeriveFunctor` algorithm, but it generates a definition for ``traverse``
3666 instead of ``fmap``. In addition, :ghc-flag:`-XDeriveTraversable` filters out
3667 all constructor arguments on the RHS expression whose types do not mention the
3668 last type parameter, since those arguments do not produce any effects in a
3669 traversal. Here are the differences between the generated code in each
3670 extension:
3671
3672 #. When a bare type variable ``a`` is encountered, both :ghc-flag:`-XDeriveFunctor` and
3673    :ghc-flag:`-XDeriveTraversable` would generate ``f a`` for an ``fmap`` and
3674    ``traverse`` definition, respectively.
3675
3676 #. When a type that is not syntactically equivalent to ``a``, but which does
3677    contain ``a``, is encountered, :ghc-flag:`-XDeriveFunctor` recursively calls
3678    ``fmap`` on it. Similarly, :ghc-flag:`-XDeriveTraversable` would recursively call
3679    ``traverse``.
3680
3681 #. :ghc-flag:`-XDeriveFunctor` puts everything back together again at the end by
3682    invoking the constructor. :ghc-flag:`-XDeriveTraversable` does something similar,
3683    but it works in an ``Applicative`` context by chaining everything together
3684    with ``(<*>)``.
3685
3686 Unlike :ghc-flag:`-XDeriveFunctor`, :ghc-flag:`-XDeriveTraversable` cannot be used on data
3687 types containing a function type on the right-hand side.
3688
3689 For a full specification of the algorithms used in :ghc-flag:`-XDeriveFunctor`,
3690 :ghc-flag:`-XDeriveFoldable`, and :ghc-flag:`-XDeriveTraversable`, see
3691 :ghc-wiki:`this wiki page <Commentary/Compiler/DeriveFunctor>`.
3692
3693 .. _deriving-typeable:
3694
3695 Deriving ``Typeable`` instances
3696 -------------------------------
3697
3698 .. ghc-flag:: -XDeriveDataTypeable
3699
3700     Enable automatic deriving of instances for the ``Typeable`` typeclass
3701
3702 The class ``Typeable`` is very special:
3703
3704 -  ``Typeable`` is kind-polymorphic (see :ref:`kind-polymorphism`).
3705
3706 -  GHC has a custom solver for discharging constraints that involve
3707    class ``Typeable``, and handwritten instances are forbidden. This
3708    ensures that the programmer cannot subvert the type system by writing
3709    bogus instances.
3710
3711 -  Derived instances of ``Typeable`` are ignored, and may be reported as
3712    an error in a later version of the compiler.
3713
3714 -  The rules for solving \`Typeable\` constraints are as follows:
3715
3716    -  A concrete type constructor applied to some types. ::
3717
3718           instance (Typeable t1, .., Typeable t_n) =>
3719             Typeable (T t1 .. t_n)
3720
3721       This rule works for any concrete type constructor, including type
3722       constructors with polymorphic kinds. The only restriction is that
3723       if the type constructor has a polymorphic kind, then it has to be
3724       applied to all of its kinds parameters, and these kinds need to be
3725       concrete (i.e., they cannot mention kind variables).
3726
3727    -  ::
3728
3729           A type variable applied to some types.
3730           instance (Typeable f, Typeable t1, .., Typeable t_n) =>
3731             Typeable (f t1 .. t_n)
3732
3733    -  ::
3734
3735           A concrete type literal.
3736           instance Typeable 0       -- Type natural literals
3737           instance Typeable "Hello" -- Type-level symbols
3738
3739 .. _deriving-lift:
3740
3741 Deriving ``Lift`` instances
3742 ---------------------------
3743
3744 .. ghc-flag:: -XDeriveLift
3745
3746     :since: 8.0.1
3747
3748     Enable automatic deriving of instances for the ``Lift`` typeclass for
3749     Template Haskell.
3750
3751 The class ``Lift``, unlike other derivable classes, lives in
3752 ``template-haskell`` instead of ``base``. Having a data type be an instance of
3753 ``Lift`` permits its values to be promoted to Template Haskell expressions (of
3754 type ``ExpQ``), which can then be spliced into Haskell source code.
3755
3756 Here is an example of how one can derive ``Lift``:
3757
3758 ::
3759
3760     {-# LANGUAGE DeriveLift #-}
3761     module Bar where
3762
3763     import Language.Haskell.TH.Syntax
3764
3765     data Foo a = Foo a | a :^: a deriving Lift
3766
3767     {-
3768     instance (Lift a) => Lift (Foo a) where
3769         lift (Foo a)
3770         = appE
3771             (conE
3772                 (mkNameG_d "package-name" "Bar" "Foo"))
3773             (lift a)
3774         lift (u :^: v)
3775         = infixApp
3776             (lift u)
3777             (conE
3778                 (mkNameG_d "package-name" "Bar" ":^:"))
3779             (lift v)
3780     -}
3781
3782     -----
3783     {-# LANGUAGE TemplateHaskell #-}
3784     module Baz where
3785
3786     import Bar
3787     import Language.Haskell.TH.Lift
3788
3789     foo :: Foo String
3790     foo = $(lift $ Foo "foo")
3791
3792     fooExp :: Lift a => Foo a -> Q Exp
3793     fooExp f = [| f |]
3794
3795 :ghc-flag:`-XDeriveLift` also works for certain unboxed types (``Addr#``, ``Char#``,
3796 ``Double#``, ``Float#``, ``Int#``, and ``Word#``):
3797
3798 ::
3799
3800     {-# LANGUAGE DeriveLift, MagicHash #-}
3801     module Unboxed where
3802
3803     import GHC.Exts
3804     import Language.Haskell.TH.Syntax
3805
3806     data IntHash = IntHash Int# deriving Lift
3807
3808     {-
3809     instance Lift IntHash where
3810         lift (IntHash i)
3811         = appE
3812             (conE
3813                 (mkNameG_d "package-name" "Unboxed" "IntHash"))
3814             (litE
3815                 (intPrimL (toInteger (I# i))))
3816     -}
3817
3818
3819 .. _newtype-deriving:
3820
3821 Generalised derived instances for newtypes
3822 ------------------------------------------
3823
3824 .. ghc-flag:: -XGeneralisedNewtypeDeriving
3825               -XGeneralizedNewtypeDeriving
3826
3827     Enable GHC's cunning generalised deriving mechanism for ``newtype``\s
3828
3829 When you define an abstract type using ``newtype``, you may want the new
3830 type to inherit some instances from its representation. In Haskell 98,
3831 you can inherit instances of ``Eq``, ``Ord``, ``Enum`` and ``Bounded``
3832 by deriving them, but for any other classes you have to write an
3833 explicit instance declaration. For example, if you define ::
3834
3835       newtype Dollars = Dollars Int
3836
3837 and you want to use arithmetic on ``Dollars``, you have to explicitly
3838 define an instance of ``Num``: ::
3839
3840       instance Num Dollars where
3841         Dollars a + Dollars b = Dollars (a+b)
3842         ...
3843
3844 All the instance does is apply and remove the ``newtype`` constructor.
3845 It is particularly galling that, since the constructor doesn't appear at
3846 run-time, this instance declaration defines a dictionary which is
3847 *wholly equivalent* to the ``Int`` dictionary, only slower!
3848
3849 .. _generalized-newtype-deriving:
3850
3851 Generalising the deriving clause
3852 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3853
3854 GHC now permits such instances to be derived instead, using the flag
3855 :ghc-flag:`-XGeneralizedNewtypeDeriving`, so one can write ::
3856
3857       newtype Dollars = Dollars { getDollars :: Int } deriving (Eq,Show,Num)
3858
3859 and the implementation uses the *same* ``Num`` dictionary for
3860 ``Dollars`` as for ``Int``. In other words, GHC will generate something that
3861 resembles the following code ::
3862
3863       instance Num Int => Num Dollars
3864
3865 and then attempt to simplify the ``Num Int`` context as much as possible.
3866 GHC knows that there is a ``Num Int`` instance in scope, so it is able to
3867 discharge the ``Num Int`` constraint, leaving the code that GHC actually
3868 generates ::
3869
3870       instance Num Dollars
3871
3872 One can think of this instance being implemented with the same code as the
3873 ``Num Int`` instance, but with ``Dollars`` and ``getDollars`` added wherever
3874 necessary in order to make it typecheck. (In practice, GHC uses a somewhat
3875 different approach to code generation. See the :ref:`precise-gnd-specification`
3876 section below for more details.)
3877
3878 We can also derive instances of constructor classes in a similar way.
3879 For example, suppose we have implemented state and failure monad
3880 transformers, such that ::
3881
3882       instance Monad m => Monad (State s m)
3883       instance Monad m => Monad (Failure m)
3884
3885 In Haskell 98, we can define a parsing monad by ::
3886
3887       type Parser tok m a = State [tok] (Failure m) a
3888
3889 which is automatically a monad thanks to the instance declarations
3890 above. With the extension, we can make the parser type abstract, without
3891 needing to write an instance of class ``Monad``, via ::
3892
3893       newtype Parser tok m a = Parser (State [tok] (Failure m) a)
3894                              deriving Monad
3895
3896 In this case the derived instance declaration is of the form ::
3897
3898       instance Monad (State [tok] (Failure m)) => Monad (Parser tok m)
3899
3900 Notice that, since ``Monad`` is a constructor class, the instance is a
3901 *partial application* of the new type, not the entire left hand side. We
3902 can imagine that the type declaration is "eta-converted" to generate the
3903 context of the instance declaration.
3904
3905 We can even derive instances of multi-parameter classes, provided the
3906 newtype is the last class parameter. In this case, a "partial
3907 application" of the class appears in the ``deriving`` clause. For
3908 example, given the class ::
3909
3910       class StateMonad s m | m -> s where ...
3911       instance Monad m => StateMonad s (State s m) where ...
3912
3913 then we can derive an instance of ``StateMonad`` for ``Parser`` by ::
3914
3915       newtype Parser tok m a = Parser (State [tok] (Failure m) a)
3916                              deriving (Monad, StateMonad [tok])
3917
3918 The derived instance is obtained by completing the application of the
3919 class to the new type: ::
3920
3921       instance StateMonad [tok] (State [tok] (Failure m)) =>
3922                StateMonad [tok] (Parser tok m)
3923
3924 As a result of this extension, all derived instances in newtype
3925 declarations are treated uniformly (and implemented just by reusing the
3926 dictionary for the representation type), *except* ``Show`` and ``Read``,
3927 which really behave differently for the newtype and its representation.
3928
3929 .. _precise-gnd-specification:
3930
3931 A more precise specification
3932 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3933
3934 A derived instance is derived only for declarations of these forms
3935 (after expansion of any type synonyms) ::
3936
3937       newtype T v1..vn                   = MkT (t vk+1..vn) deriving (C t1..tj)
3938       newtype instance T s1..sk vk+1..vn = MkT (t vk+1..vn) deriving (C t1..tj)
3939
3940 where
3941
3942 -  ``v1..vn`` are type variables, and ``t``, ``s1..sk``, ``t1..tj`` are
3943    types.
3944
3945 -  The ``(C t1..tj)`` is a partial applications of the class ``C``,
3946    where the arity of ``C`` is exactly ``j+1``. That is, ``C`` lacks
3947    exactly one type argument.
3948
3949 -  ``k`` is chosen so that ``C t1..tj (T v1...vk)`` is well-kinded. (Or,
3950    in the case of a ``data instance``, so that ``C t1..tj (T s1..sk)``
3951    is well kinded.)
3952
3953 -  The type ``t`` is an arbitrary type.
3954
3955 -  The type variables ``vk+1...vn`` do not occur in the types ``t``,
3956    ``s1..sk``, or ``t1..tj``.
3957
3958 -  ``C`` is not ``Read``, ``Show``, ``Typeable``, or ``Data``. These
3959    classes should not "look through" the type or its constructor. You
3960    can still derive these classes for a newtype, but it happens in the
3961    usual way, not via this new mechanism.
3962
3963 -  It is safe to coerce each of the methods of ``C``. That is, the
3964    missing last argument to ``C`` is not used at a nominal role in any
3965    of the ``C``'s methods. (See :ref:`roles`.)
3966
3967 - ``C`` is allowed to have associated type families, provided they meet the
3968   requirements laid out in the section on :ref:`GND and associated types
3969   <gnd-and-associated-types>`.
3970
3971 Then the derived instance declaration is of the form ::
3972
3973       instance C t1..tj t => C t1..tj (T v1...vk)
3974
3975 Note that if ``C`` does not contain any class methods, the instance context
3976 is wholly unnecessary, and as such GHC will instead generate: ::
3977
3978       instance C t1..tj (T v1..vk)
3979
3980 As an example which does *not* work, consider ::
3981
3982       newtype NonMonad m s = NonMonad (State s m s) deriving Monad
3983
3984 Here we cannot derive the instance ::
3985
3986       instance Monad (State s m) => Monad (NonMonad m)
3987
3988 because the type variable ``s`` occurs in ``State s m``, and so cannot
3989 be "eta-converted" away. It is a good thing that this ``deriving``
3990 clause is rejected, because ``NonMonad m`` is not, in fact, a monad ---
3991 for the same reason. Try defining ``>>=`` with the correct type: you
3992 won't be able to.
3993
3994 Notice also that the *order* of class parameters becomes important,
3995 since we can only derive instances for the last one. If the
3996 ``StateMonad`` class above were instead defined as ::
3997
3998       class StateMonad m s | m -> s where ...
3999
4000 then we would not have been able to derive an instance for the
4001 ``Parser`` type above. We hypothesise that multi-parameter classes
4002 usually have one "main" parameter for which deriving new instances is
4003 most interesting.
4004
4005 Lastly, all of this applies only for classes other than ``Read``,
4006 ``Show``, ``Typeable``, and ``Data``, for which the stock derivation
4007 applies (section 4.3.3. of the Haskell Report). (For the standard
4008 classes ``Eq``, ``Ord``, ``Ix``, and ``Bounded`` it is immaterial
4009 whether the stock method is used or the one described here.)
4010
4011 .. _gnd-and-associated-types:
4012
4013 Associated type families
4014 ~~~~~~~~~~~~~~~~~~~~~~~~
4015
4016 :ghc-flag:`-XGeneralizedNewtypeDeriving` also works for some type classes with
4017 associated type families. Here is an example: ::
4018
4019       class HasRing a where
4020         type Ring a
4021
4022       newtype L1Norm a = L1Norm a
4023         deriving HasRing
4024
4025 The derived ``HasRing`` instance would look like ::
4026
4027       instance HasRing (L1Norm a) where
4028         type Ring (L1Norm a) = Ring a
4029
4030 To be precise, if the class being derived is of the form ::
4031
4032       class C c_1 c_2 ... c_m where
4033         type T1 t1_1 t1_2 ... t1_n
4034         ...
4035         type Tk tk_1 tk_2 ... tk_p
4036
4037 and the newtype is of the form ::
4038
4039       newtype N n_1 n_2 ... n_q = MkN <rep-type>
4040
4041 then you can derive a ``C c_1 c_2 ... c_(m-1)`` instance for
4042 ``N n_1 n_2 ... n_q``, provided that:
4043
4044 - The type parameter ``c_m`` occurs once in each of the type variables of
4045   ``T1`` through ``Tk``. Imagine a class where this condition didn't hold.
4046   For example: ::
4047
4048       class Bad a b where
4049         type B a
4050
4051       instance Bad Int a where
4052         type B Int = Char
4053
4054       newtype Foo a = Foo a
4055         deriving (Bad Int)
4056
4057   For the derived ``Bad Int`` instance, GHC would need to generate something
4058   like this: ::
4059
4060       instance Bad Int (Foo a) where
4061         type B Int = B ???
4062
4063   Now we're stuck, since we have no way to refer to ``a`` on the right-hand
4064   side of the ``B`` family instance, so this instance doesn't really make sense
4065   in a :ghc-flag:`-XGeneralizedNewtypeDeriving` setting.
4066
4067 - ``C`` does not have any associated data families (only type families). To
4068   see why data families are forbidden, imagine the following scenario: ::
4069
4070       class Ex a where
4071         data D a
4072
4073       instance Ex Int where
4074         data D Int = DInt Bool
4075
4076       newtype Age = MkAge Int deriving Ex
4077
4078   For the derived ``Ex`` instance, GHC would need to generate something like
4079   this: ::
4080
4081       instance Ex Age where
4082         data D Age = ???
4083
4084   But it is not clear what GHC would fill in for ``???``, as each data family
4085   instance must generate fresh data constructors.
4086
4087 If both of these conditions are met, GHC will generate this instance: ::
4088
4089       instance C c_1 c_2 ... c_(m-1) <rep-type> =>
4090                C c_1 c_2 ... c_(m-1) (N n_1 n_2 ... n_q) where
4091         type T1 t1_1 t1_2 ... (N n_1 n_2 ... n_q) ... t1_n
4092            = T1 t1_1 t1_2 ... <rep-type>          ... t1_n
4093         ...
4094         type Tk tk_1 tk_2 ... (N n_1 n_2 ... n_q) ... tk_p
4095            = Tk tk_1 tk_2 ... <rep-type>          ... tk_p
4096
4097 Again, if ``C`` contains no class methods, the instance context will be
4098 redundant, so GHC will instead generate
4099 ``instance C c_1 c_2 ... c_(m-1) (N n_1 n_2 ... n_q)``.
4100
4101 Beware that in some cases, you may need to enable the
4102 :ghc-flag:`-XUndecidableInstances` extension in order to use this feature.
4103 Here's a pathological case that illustrates why this might happen: ::
4104
4105       class C a where
4106         type T a
4107
4108       newtype Loop = MkLoop Loop
4109         deriving C
4110
4111 This will generate the derived instance: ::
4112
4113       instance C Loop where
4114         type T Loop = T Loop
4115
4116 Here, it is evident that attempting to use the type ``T Loop`` will throw the
4117 typechecker into an infinite loop, as its definition recurses endlessly. In
4118 other cases, you might need to enable :ghc-flag:`-XUndecidableInstances` even
4119 if the generated code won't put the typechecker into a loop. For example: ::
4120
4121       instance C Int where
4122         type C Int = Int
4123
4124       newtype MyInt = MyInt Int
4125     &