Eliminate a user manual warning
[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 contrast, 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
970 .. _applicative-do-existential:
971
972 Existential patterns and GADTs
973 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
974
975 Note that when the pattern in a statement matches a constructor with
976 existential type variables and/or constraints, the transformation that
977 ``ApplicativeDo`` performs may mean that the pattern does not scope
978 over the statements that follow it.  This is because the rearrangement
979 happens before the expression is typechecked.  For example, this
980 program does not typecheck::
981
982     {-# LANGUAGE RankNTypes, GADTs, ApplicativeDo #-}
983
984     data T where A :: forall a . Eq a => a -> T
985
986     test = do
987       A x <- undefined
988       _ <- return True
989       return (x == x)
990
991 The reason is that the ``Eq`` constraint that would be brought into
992 scope from the pattern match ``A x`` is not available when
993 typechecking the expression ``x == x``, because ``ApplicativeDo`` has
994 rearranged the expression to look like this::
995
996     test =
997       (\x _ -> x == x)
998         <$> do A x <- undefined; return x
999         <*> return True
1000
1001 Turning off ``ApplicativeDo`` lets the program typecheck.  This is
1002 something to bear in mind when using ``ApplicativeDo`` in combination
1003 with :ref:`existential-quantification` or :ref:`gadt`.
1004
1005 .. _applicative-do-pitfall:
1006
1007 Things to watch out for
1008 ~~~~~~~~~~~~~~~~~~~~~~~
1009
1010 Your code should just work as before when :ghc-flag:`-XApplicativeDo` is enabled,
1011 provided you use conventional ``Applicative`` instances. However, if you define
1012 a ``Functor`` or ``Applicative`` instance using do-notation, then it will likely
1013 get turned into an infinite loop by GHC. For example, if you do this: ::
1014
1015     instance Functor MyType where
1016         fmap f m = do x <- m; return (f x)
1017
1018 Then applicative desugaring will turn it into ::
1019
1020     instance Functor MyType where
1021         fmap f m = fmap (\x -> f x) m
1022
1023 And the program will loop at runtime. Similarly, an ``Applicative`` instance
1024 like this ::
1025
1026     instance Applicative MyType where
1027         pure = return
1028         x <*> y = do f <- x; a <- y; return (f a)
1029
1030 will result in an infinte loop when ``<*>`` is called.
1031
1032 Just as you wouldn't define a ``Monad`` instance using the do-notation, you
1033 shouldn't define ``Functor`` or ``Applicative`` instance using do-notation (when
1034 using ``ApplicativeDo``) either. The correct way to define these instances in
1035 terms of ``Monad`` is to use the ``Monad`` operations directly, e.g. ::
1036
1037     instance Functor MyType where
1038         fmap f m = m >>= return . f
1039
1040     instance Applicative MyType where
1041         pure = return
1042         (<*>) = ap
1043
1044
1045 .. _parallel-list-comprehensions:
1046
1047 Parallel List Comprehensions
1048 ----------------------------
1049
1050 .. index::
1051    single: list comprehensions; parallel
1052    single: parallel list comprehensions
1053
1054 .. ghc-flag:: -XParallelListComp
1055
1056     Allow parallel list comprehension syntax.
1057
1058 Parallel list comprehensions are a natural extension to list
1059 comprehensions. List comprehensions can be thought of as a nice syntax
1060 for writing maps and filters. Parallel comprehensions extend this to
1061 include the ``zipWith`` family.
1062
1063 A parallel list comprehension has multiple independent branches of
1064 qualifier lists, each separated by a ``|`` symbol. For example, the
1065 following zips together two lists: ::
1066
1067        [ (x, y) | x <- xs | y <- ys ]
1068
1069 The behaviour of parallel list comprehensions follows that of zip, in
1070 that the resulting list will have the same length as the shortest
1071 branch.
1072
1073 We can define parallel list comprehensions by translation to regular
1074 comprehensions. Here's the basic idea:
1075
1076 Given a parallel comprehension of the form: ::
1077
1078        [ e | p1 <- e11, p2 <- e12, ...
1079            | q1 <- e21, q2 <- e22, ...
1080            ...
1081        ]
1082
1083 This will be translated to: ::
1084
1085        [ e | ((p1,p2), (q1,q2), ...) <- zipN [(p1,p2) | p1 <- e11, p2 <- e12, ...]
1086                                              [(q1,q2) | q1 <- e21, q2 <- e22, ...]
1087                                              ...
1088        ]
1089
1090 where ``zipN`` is the appropriate zip for the given number of branches.
1091
1092 .. _generalised-list-comprehensions:
1093
1094 Generalised (SQL-like) List Comprehensions
1095 ------------------------------------------
1096
1097 .. index::
1098    single: list comprehensions; generalised
1099    single: extended list comprehensions
1100    single: group
1101    single: SQL
1102
1103 .. ghc-flag:: -XTransformListComp
1104
1105     Allow use of generalised list (SQL-like) comprehension syntax. This
1106     introduces the ``group``, ``by``, and ``using`` keywords.
1107
1108 Generalised list comprehensions are a further enhancement to the list
1109 comprehension syntactic sugar to allow operations such as sorting and
1110 grouping which are familiar from SQL. They are fully described in the
1111 paper `Comprehensive comprehensions: comprehensions with "order by" and
1112 "group by" <http://research.microsoft.com/~simonpj/papers/list-comp>`__,
1113 except that the syntax we use differs slightly from the paper.
1114
1115 The extension is enabled with the flag :ghc-flag:`-XTransformListComp`.
1116
1117 Here is an example:
1118
1119 ::
1120
1121     employees = [ ("Simon", "MS", 80)
1122                 , ("Erik", "MS", 100)
1123                 , ("Phil", "Ed", 40)
1124                 , ("Gordon", "Ed", 45)
1125                 , ("Paul", "Yale", 60) ]
1126
1127     output = [ (the dept, sum salary)
1128              | (name, dept, salary) <- employees
1129              , then group by dept using groupWith
1130              , then sortWith by (sum salary)
1131              , then take 5 ]
1132
1133 In this example, the list ``output`` would take on the value:
1134
1135 ::
1136
1137     [("Yale", 60), ("Ed", 85), ("MS", 180)]
1138
1139 There are three new keywords: ``group``, ``by``, and ``using``. (The
1140 functions ``sortWith`` and ``groupWith`` are not keywords; they are
1141 ordinary functions that are exported by ``GHC.Exts``.)
1142
1143 There are five new forms of comprehension qualifier, all introduced by
1144 the (existing) keyword ``then``:
1145
1146 -  ::
1147
1148        then f
1149
1150    This statement requires that
1151    f
1152    have the type
1153    forall a. [a] -> [a]
1154    . You can see an example of its use in the motivating example, as
1155    this form is used to apply
1156    take 5
1157    .
1158 -  ::
1159
1160        then f by e
1161
1162    This form is similar to the previous one, but allows you to create a
1163    function which will be passed as the first argument to f. As a
1164    consequence f must have the type
1165    ``forall a. (a -> t) -> [a] -> [a]``. As you can see from the type,
1166    this function lets f "project out" some information from the elements
1167    of the list it is transforming.
1168
1169    An example is shown in the opening example, where ``sortWith`` is
1170    supplied with a function that lets it find out the ``sum salary`` for
1171    any item in the list comprehension it transforms.
1172
1173 -  ::
1174
1175        then group by e using f
1176
1177    This is the most general of the grouping-type statements. In this
1178    form, f is required to have type
1179    ``forall a. (a -> t) -> [a] -> [[a]]``. As with the ``then f by e``
1180    case above, the first argument is a function supplied to f by the
1181    compiler which lets it compute e on every element of the list being
1182    transformed. However, unlike the non-grouping case, f additionally
1183    partitions the list into a number of sublists: this means that at
1184    every point after this statement, binders occurring before it in the
1185    comprehension refer to *lists* of possible values, not single values.
1186    To help understand this, let's look at an example:
1187
1188    ::
1189
1190        -- This works similarly to groupWith in GHC.Exts, but doesn't sort its input first
1191        groupRuns :: Eq b => (a -> b) -> [a] -> [[a]]
1192        groupRuns f = groupBy (\x y -> f x == f y)
1193
1194        output = [ (the x, y)
1195        | x <- ([1..3] ++ [1..2])
1196        , y <- [4..6]
1197        , then group by x using groupRuns ]
1198
1199    This results in the variable ``output`` taking on the value below:
1200
1201    ::
1202
1203        [(1, [4, 5, 6]), (2, [4, 5, 6]), (3, [4, 5, 6]), (1, [4, 5, 6]), (2, [4, 5, 6])]
1204
1205    Note that we have used the ``the`` function to change the type of x
1206    from a list to its original numeric type. The variable y, in
1207    contrast, is left unchanged from the list form introduced by the
1208    grouping.
1209
1210 -  ::
1211
1212        then group using f
1213
1214    With this form of the group statement, f is required to simply have
1215    the type ``forall a. [a] -> [[a]]``, which will be used to group up
1216    the comprehension so far directly. An example of this form is as
1217    follows:
1218
1219    ::
1220
1221        output = [ x
1222        | y <- [1..5]
1223        , x <- "hello"
1224        , then group using inits]
1225
1226    This will yield a list containing every prefix of the word "hello"
1227    written out 5 times:
1228
1229    ::
1230
1231        ["","h","he","hel","hell","hello","helloh","hellohe","hellohel","hellohell","hellohello","hellohelloh",...]
1232
1233 .. _monad-comprehensions:
1234
1235 Monad comprehensions
1236 --------------------
1237
1238 .. index::
1239    single: monad comprehensions
1240
1241 .. ghc-flag:: -XMonadComprehensions
1242
1243     :since: 7.2
1244
1245     Enable list comprehension syntax for arbitrary monads.
1246
1247 Monad comprehensions generalise the list comprehension notation,
1248 including parallel comprehensions (:ref:`parallel-list-comprehensions`)
1249 and transform comprehensions (:ref:`generalised-list-comprehensions`) to
1250 work for any monad.
1251
1252 Monad comprehensions support:
1253
1254 -  Bindings: ::
1255
1256        [ x + y | x <- Just 1, y <- Just 2 ]
1257
1258    Bindings are translated with the ``(>>=)`` and ``return`` functions
1259    to the usual do-notation: ::
1260
1261        do x <- Just 1
1262           y <- Just 2
1263           return (x+y)
1264
1265 -  Guards: ::
1266
1267        [ x | x <- [1..10], x <= 5 ]
1268
1269    Guards are translated with the ``guard`` function, which requires a
1270    ``MonadPlus`` instance: ::
1271
1272        do x <- [1..10]
1273           guard (x <= 5)
1274           return x
1275
1276 -  Transform statements (as with :ghc-flag:`-XTransformListComp`): ::
1277
1278        [ x+y | x <- [1..10], y <- [1..x], then take 2 ]
1279
1280    This translates to: ::
1281
1282        do (x,y) <- take 2 (do x <- [1..10]
1283                               y <- [1..x]
1284                               return (x,y))
1285           return (x+y)
1286
1287 -  Group statements (as with :ghc-flag:`-XTransformListComp`):
1288
1289    ::
1290
1291        [ x | x <- [1,1,2,2,3], then group by x using GHC.Exts.groupWith ]
1292        [ x | x <- [1,1,2,2,3], then group using myGroup ]
1293
1294 -  Parallel statements (as with :ghc-flag:`-XParallelListComp`):
1295
1296    ::
1297
1298        [ (x+y) | x <- [1..10]
1299                | y <- [11..20]
1300                ]
1301
1302    Parallel statements are translated using the ``mzip`` function, which
1303    requires a ``MonadZip`` instance defined in
1304    :base-ref:`Control.Monad.Zip <Control-Monad-Zip.html>`:
1305
1306    ::
1307
1308        do (x,y) <- mzip (do x <- [1..10]
1309                             return x)
1310                         (do y <- [11..20]
1311                             return y)
1312           return (x+y)
1313
1314 All these features are enabled by default if the :ghc-flag:`-XMonadComprehensions`
1315 extension is enabled. The types and more detailed examples on how to use
1316 comprehensions are explained in the previous chapters
1317 :ref:`generalised-list-comprehensions` and
1318 :ref:`parallel-list-comprehensions`. In general you just have to replace
1319 the type ``[a]`` with the type ``Monad m => m a`` for monad
1320 comprehensions.
1321
1322 .. note::
1323     Even though most of these examples are using the list monad, monad
1324     comprehensions work for any monad. The ``base`` package offers all
1325     necessary instances for lists, which make :ghc-flag:`-XMonadComprehensions`
1326     backward compatible to built-in, transform and parallel list
1327     comprehensions.
1328
1329 More formally, the desugaring is as follows. We write ``D[ e | Q]`` to
1330 mean the desugaring of the monad comprehension ``[ e | Q]``:
1331
1332 .. code-block:: none
1333
1334     Expressions: e
1335     Declarations: d
1336     Lists of qualifiers: Q,R,S
1337
1338     -- Basic forms
1339     D[ e | ]               = return e
1340     D[ e | p <- e, Q ]  = e >>= \p -> D[ e | Q ]
1341     D[ e | e, Q ]          = guard e >> \p -> D[ e | Q ]
1342     D[ e | let d, Q ]      = let d in D[ e | Q ]
1343
1344     -- Parallel comprehensions (iterate for multiple parallel branches)
1345     D[ e | (Q | R), S ]    = mzip D[ Qv | Q ] D[ Rv | R ] >>= \(Qv,Rv) -> D[ e | S ]
1346
1347     -- Transform comprehensions
1348     D[ e | Q then f, R ]                  = f D[ Qv | Q ] >>= \Qv -> D[ e | R ]
1349
1350     D[ e | Q then f by b, R ]             = f (\Qv -> b) D[ Qv | Q ] >>= \Qv -> D[ e | R ]
1351
1352     D[ e | Q then group using f, R ]      = f D[ Qv | Q ] >>= \ys ->
1353                                             case (fmap selQv1 ys, ..., fmap selQvn ys) of
1354                                              Qv -> D[ e | R ]
1355
1356     D[ e | Q then group by b using f, R ] = f (\Qv -> b) D[ Qv | Q ] >>= \ys ->
1357                                             case (fmap selQv1 ys, ..., fmap selQvn ys) of
1358                                                Qv -> D[ e | R ]
1359
1360     where  Qv is the tuple of variables bound by Q (and used subsequently)
1361            selQvi is a selector mapping Qv to the ith component of Qv
1362
1363     Operator     Standard binding       Expected type
1364     --------------------------------------------------------------------
1365     return       GHC.Base               t1 -> m t2
1366     (>>=)        GHC.Base               m1 t1 -> (t2 -> m2 t3) -> m3 t3
1367     (>>)         GHC.Base               m1 t1 -> m2 t2         -> m3 t3
1368     guard        Control.Monad          t1 -> m t2
1369     fmap         GHC.Base               forall a b. (a->b) -> n a -> n b
1370     mzip         Control.Monad.Zip      forall a b. m a -> m b -> m (a,b)
1371
1372 The comprehension should typecheck when its desugaring would typecheck,
1373 except that (as discussed in :ref:`generalised-list-comprehensions`) in the
1374 "then ``f``" and "then group using ``f``" clauses, when the "by ``b``" qualifier
1375 is omitted, argument ``f`` should have a polymorphic type. In particular, "then
1376 ``Data.List.sort``" and "then group using ``Data.List.group``" are
1377 insufficiently polymorphic.
1378
1379 Monad comprehensions support rebindable syntax
1380 (:ref:`rebindable-syntax`). Without rebindable syntax, the operators
1381 from the "standard binding" module are used; with rebindable syntax, the
1382 operators are looked up in the current lexical scope. For example,
1383 parallel comprehensions will be typechecked and desugared using whatever
1384 "``mzip``" is in scope.
1385
1386 The rebindable operators must have the "Expected type" given in the
1387 table above. These types are surprisingly general. For example, you can
1388 use a bind operator with the type
1389
1390 ::
1391
1392     (>>=) :: T x y a -> (a -> T y z b) -> T x z b
1393
1394 In the case of transform comprehensions, notice that the groups are
1395 parameterised over some arbitrary type ``n`` (provided it has an
1396 ``fmap``, as well as the comprehension being over an arbitrary monad.
1397
1398 .. _monadfail-desugaring:
1399
1400 New monadic failure desugaring mechanism
1401 ----------------------------------------
1402
1403 .. ghc-flag:: -XMonadFailDesugaring
1404
1405     :since: 8.0.1
1406
1407     Use the ``MonadFail.fail`` instead of the legacy ``Monad.fail`` function
1408     when desugaring refutable patterns in ``do`` blocks.
1409
1410 The ``-XMonadFailDesugaring`` extension switches the desugaring of
1411 ``do``-blocks to use ``MonadFail.fail`` instead of ``Monad.fail``. This will
1412 eventually be the default behaviour in a future GHC release, under the
1413 `MonadFail Proposal (MFP)
1414 <https://prime.haskell.org/wiki/Libraries/Proposals/MonadFail>`__.
1415
1416 This extension is temporary, and will be deprecated in a future release. It is
1417 included so that library authors have a hard check for whether their code
1418 will work with future GHC versions.
1419
1420 .. _rebindable-syntax:
1421
1422 Rebindable syntax and the implicit Prelude import
1423 -------------------------------------------------
1424
1425 .. ghc-flag:: -XNoImplicitPrelude
1426
1427     Don't import ``Prelude`` by default.
1428
1429 GHC normally imports ``Prelude.hi`` files for
1430 you. If you'd rather it didn't, then give it a ``-XNoImplicitPrelude``
1431 option. The idea is that you can then import a Prelude of your own. (But
1432 don't call it ``Prelude``; the Haskell module namespace is flat, and you
1433 must not conflict with any Prelude module.)
1434
1435 .. ghc-flag:: -XRebindableSyntax
1436
1437     :implies: :ghc-flag:`-XNoImplicitPrelude`
1438     :since: 7.0.1
1439
1440     Enable rebinding of a variety of usually-built-in operations.
1441
1442 Suppose you are importing a Prelude of your own in order to define your
1443 own numeric class hierarchy. It completely defeats that purpose if the
1444 literal "1" means "``Prelude.fromInteger 1``", which is what the Haskell
1445 Report specifies. So the :ghc-flag:`-XRebindableSyntax` flag causes the
1446 following pieces of built-in syntax to refer to *whatever is in scope*,
1447 not the Prelude versions:
1448
1449 -  An integer literal ``368`` means "``fromInteger (368::Integer)``",
1450    rather than "``Prelude.fromInteger (368::Integer)``".
1451
1452 -  Fractional literals are handed in just the same way, except that the
1453    translation is ``fromRational (3.68::Rational)``.
1454
1455 -  The equality test in an overloaded numeric pattern uses whatever
1456    ``(==)`` is in scope.
1457
1458 -  The subtraction operation, and the greater-than-or-equal test, in
1459    ``n+k`` patterns use whatever ``(-)`` and ``(>=)`` are in scope.
1460
1461 -  Negation (e.g. "``- (f x)``") means "``negate (f x)``", both in
1462    numeric patterns, and expressions.
1463
1464 -  Conditionals (e.g. "``if`` e1 ``then`` e2 ``else`` e3") means
1465    "``ifThenElse`` e1 e2 e3". However ``case`` expressions are
1466    unaffected.
1467
1468 -  "Do" notation is translated using whatever functions ``(>>=)``,
1469    ``(>>)``, and ``fail``, are in scope (not the Prelude versions). List
1470    comprehensions, ``mdo`` (:ref:`recursive-do-notation`), and parallel
1471    array comprehensions, are unaffected.
1472
1473 -  Arrow notation (see :ref:`arrow-notation`) uses whatever ``arr``,
1474    ``(>>>)``, ``first``, ``app``, ``(|||)`` and ``loop`` functions are
1475    in scope. But unlike the other constructs, the types of these
1476    functions must match the Prelude types very closely. Details are in
1477    flux; if you want to use this, ask!
1478
1479 -  List notation, such as ``[x,y]`` or ``[m..n]`` can also be treated
1480    via rebindable syntax if you use `-XOverloadedLists`;
1481    see :ref:`overloaded-lists`.
1482
1483 -  An overloaded label "``#foo``" means "``fromLabel @"foo"``", rather than
1484    "``GHC.OverloadedLabels.fromLabel @"foo"``" (see :ref:`overloaded-labels`).
1485
1486 :ghc-flag:`-XRebindableSyntax` implies :ghc-flag:`-XNoImplicitPrelude`.
1487
1488 In all cases (apart from arrow notation), the static semantics should be
1489 that of the desugared form, even if that is a little unexpected. For
1490 example, the static semantics of the literal ``368`` is exactly that of
1491 ``fromInteger (368::Integer)``; it's fine for ``fromInteger`` to have
1492 any of the types: ::
1493
1494     fromInteger :: Integer -> Integer
1495     fromInteger :: forall a. Foo a => Integer -> a
1496     fromInteger :: Num a => a -> Integer
1497     fromInteger :: Integer -> Bool -> Bool
1498
1499 Be warned: this is an experimental facility, with fewer checks than
1500 usual. Use ``-dcore-lint`` to typecheck the desugared program. If Core
1501 Lint is happy you should be all right.
1502
1503 Things unaffected by :ghc-flag:`-XRebindableSyntax`
1504 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1505
1506 :ghc-flag:`-XRebindableSyntax` does not apply to any code generated from a
1507 ``deriving`` clause or declaration. To see why, consider the following code: ::
1508
1509     {-# LANGUAGE RebindableSyntax, OverloadedStrings #-}
1510     newtype Text = Text String
1511
1512     fromString :: String -> Text
1513     fromString = Text
1514
1515     data Foo = Foo deriving Show
1516
1517 This will generate code to the effect of: ::
1518
1519     instance Show Foo where
1520       showsPrec _ Foo = showString "Foo"
1521
1522 But because :ghc-flag:`-XRebindableSyntax` and :ghc-flag:`-XOverloadedStrings`
1523 are enabled, the ``"Foo"`` string literal would now be of type ``Text``, not
1524 ``String``, which ``showString`` doesn't accept! This causes the generated
1525 ``Show`` instance to fail to typecheck. It's hard to imagine any scenario where
1526 it would be desirable have :ghc-flag:`-XRebindableSyntax` behavior within
1527 derived code, so GHC simply ignores :ghc-flag:`-XRebindableSyntax` entirely
1528 when checking derived code.
1529
1530 .. _postfix-operators:
1531
1532 Postfix operators
1533 -----------------
1534
1535 .. ghc-flag:: -XPostfixOperators
1536
1537     Allow the use of post-fix operators
1538
1539 The :ghc-flag:`-XPostfixOperators` flag enables a small extension to the syntax
1540 of left operator sections, which allows you to define postfix operators.
1541 The extension is this: the left section ::
1542
1543       (e !)
1544
1545 is equivalent (from the point of view of both type checking and
1546 execution) to the expression ::
1547
1548       ((!) e)
1549
1550 (for any expression ``e`` and operator ``(!)``. The strict Haskell 98
1551 interpretation is that the section is equivalent to ::
1552
1553       (\y -> (!) e y)
1554
1555 That is, the operator must be a function of two arguments. GHC allows it
1556 to take only one argument, and that in turn allows you to write the
1557 function postfix.
1558
1559 The extension does not extend to the left-hand side of function
1560 definitions; you must define such a function in prefix form.
1561
1562 .. _tuple-sections:
1563
1564 Tuple sections
1565 --------------
1566
1567 .. ghc-flag:: -XTupleSections
1568
1569     :since: 6.12
1570
1571     Allow the use of tuple section syntax
1572
1573 The :ghc-flag:`-XTupleSections` flag enables Python-style partially applied
1574 tuple constructors. For example, the following program ::
1575
1576       (, True)
1577
1578 is considered to be an alternative notation for the more unwieldy
1579 alternative ::
1580
1581       \x -> (x, True)
1582
1583 You can omit any combination of arguments to the tuple, as in the
1584 following ::
1585
1586       (, "I", , , "Love", , 1337)
1587
1588 which translates to ::
1589
1590       \a b c d -> (a, "I", b, c, "Love", d, 1337)
1591
1592 If you have `unboxed tuples <#unboxed-tuples>`__ enabled, tuple sections
1593 will also be available for them, like so ::
1594
1595       (# , True #)
1596
1597 Because there is no unboxed unit tuple, the following expression ::
1598
1599       (# #)
1600
1601 continues to stand for the unboxed singleton tuple data constructor.
1602
1603 .. _lambda-case:
1604
1605 Lambda-case
1606 -----------
1607
1608 .. ghc-flag:: -XLambdaCase
1609
1610     :since: 7.6.1
1611
1612     Allow the use of lambda-case syntax.
1613
1614 The :ghc-flag:`-XLambdaCase` flag enables expressions of the form ::
1615
1616       \case { p1 -> e1; ...; pN -> eN }
1617
1618 which is equivalent to ::
1619
1620       \freshName -> case freshName of { p1 -> e1; ...; pN -> eN }
1621
1622 Note that ``\case`` starts a layout, so you can write ::
1623
1624       \case
1625         p1 -> e1
1626         ...
1627         pN -> eN
1628
1629 .. _empty-case:
1630
1631 Empty case alternatives
1632 -----------------------
1633
1634 .. ghc-flag:: -XEmptyCase
1635
1636     :since: 7.8.1
1637
1638     Allow empty case expressions.
1639
1640 The :ghc-flag:`-XEmptyCase` flag enables case expressions, or lambda-case
1641 expressions, that have no alternatives, thus: ::
1642
1643     case e of { }   -- No alternatives
1644
1645 or ::
1646
1647     \case { }       -- -XLambdaCase is also required
1648
1649 This can be useful when you know that the expression being scrutinised
1650 has no non-bottom values. For example:
1651
1652 ::
1653
1654       data Void
1655       f :: Void -> Int
1656       f x = case x of { }
1657
1658 With dependently-typed features it is more useful (see :ghc-ticket:`2431`). For
1659 example, consider these two candidate definitions of ``absurd``:
1660
1661 ::
1662
1663     data a :==: b where
1664       Refl :: a :==: a
1665
1666     absurd :: True :~: False -> a
1667     absurd x = error "absurd"    -- (A)
1668     absurd x = case x of {}      -- (B)
1669
1670 We much prefer (B). Why? Because GHC can figure out that
1671 ``(True :~: False)`` is an empty type. So (B) has no partiality and GHC
1672 should be able to compile with :ghc-flag:`-Wincomplete-patterns`. (Though
1673 the pattern match checking is not yet clever enough to do that.) On the
1674 other hand (A) looks dangerous, and GHC doesn't check to make sure that,
1675 in fact, the function can never get called.
1676
1677 .. _multi-way-if:
1678
1679 Multi-way if-expressions
1680 ------------------------
1681
1682 .. ghc-flag:: -XMultiWayIf
1683
1684     :since: 7.6.1
1685
1686     Allow the use of multi-way-``if`` syntax.
1687
1688 With :ghc-flag:`-XMultiWayIf` flag GHC accepts conditional expressions with
1689 multiple branches: ::
1690
1691       if | guard1 -> expr1
1692          | ...
1693          | guardN -> exprN
1694
1695 which is roughly equivalent to ::
1696
1697       case () of
1698         _ | guard1 -> expr1
1699         ...
1700         _ | guardN -> exprN
1701
1702 Multi-way if expressions introduce a new layout context. So the example
1703 above is equivalent to: ::
1704
1705       if { | guard1 -> expr1
1706          ; | ...
1707          ; | guardN -> exprN
1708          }
1709
1710 The following behaves as expected: ::
1711
1712       if | guard1 -> if | guard2 -> expr2
1713                         | guard3 -> expr3
1714          | guard4 -> expr4
1715
1716 because layout translates it as ::
1717
1718       if { | guard1 -> if { | guard2 -> expr2
1719                           ; | guard3 -> expr3
1720                           }
1721          ; | guard4 -> expr4
1722          }
1723
1724 Layout with multi-way if works in the same way as other layout contexts,
1725 except that the semi-colons between guards in a multi-way if are
1726 optional. So it is not necessary to line up all the guards at the same
1727 column; this is consistent with the way guards work in function
1728 definitions and case expressions.
1729
1730 .. _local-fixity-declarations:
1731
1732 Local Fixity Declarations
1733 -------------------------
1734
1735 A careful reading of the Haskell 98 Report reveals that fixity
1736 declarations (``infix``, ``infixl``, and ``infixr``) are permitted to
1737 appear inside local bindings such those introduced by ``let`` and
1738 ``where``. However, the Haskell Report does not specify the semantics of
1739 such bindings very precisely.
1740
1741 In GHC, a fixity declaration may accompany a local binding: ::
1742
1743     let f = ...
1744         infixr 3 `f`
1745     in
1746         ...
1747
1748 and the fixity declaration applies wherever the binding is in scope. For
1749 example, in a ``let``, it applies in the right-hand sides of other
1750 ``let``-bindings and the body of the ``let``\ C. Or, in recursive ``do``
1751 expressions (:ref:`recursive-do-notation`), the local fixity
1752 declarations of a ``let`` statement scope over other statements in the
1753 group, just as the bound name does.
1754
1755 Moreover, a local fixity declaration *must* accompany a local binding
1756 of that name: it is not possible to revise the fixity of name bound
1757 elsewhere, as in ::
1758
1759     let infixr 9 $ in ...
1760
1761 Because local fixity declarations are technically Haskell 98, no flag is
1762 necessary to enable them.
1763
1764 .. _package-imports:
1765
1766 Import and export extensions
1767 ----------------------------
1768
1769 Hiding things the imported module doesn't export
1770 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1771
1772 Technically in Haskell 2010 this is illegal: ::
1773
1774     module A( f ) where
1775       f = True
1776
1777     module B where
1778       import A hiding( g )  -- A does not export g
1779       g = f
1780
1781 The ``import A hiding( g )`` in module ``B`` is technically an error
1782 (`Haskell Report,
1783 5.3.1 <http://www.haskell.org/onlinereport/haskell2010/haskellch5.html#x11-1020005.3.1>`__)
1784 because ``A`` does not export ``g``. However GHC allows it, in the
1785 interests of supporting backward compatibility; for example, a newer
1786 version of ``A`` might export ``g``, and you want ``B`` to work in
1787 either case.
1788
1789 The warning :ghc-flag:`-Wdodgy-imports`, which is off by default but included
1790 with :ghc-flag:`-W`, warns if you hide something that the imported module does
1791 not export.
1792
1793 .. _package-qualified-imports:
1794
1795 Package-qualified imports
1796 ~~~~~~~~~~~~~~~~~~~~~~~~~
1797
1798 .. ghc-flag:: -XPackageImports
1799
1800     Allow the use of package-qualified ``import`` syntax.
1801
1802 With the :ghc-flag:`-XPackageImports` flag, GHC allows import declarations to be
1803 qualified by the package name that the module is intended to be imported
1804 from. For example: ::
1805
1806     import "network" Network.Socket
1807
1808 would import the module ``Network.Socket`` from the package ``network``
1809 (any version). This may be used to disambiguate an import when the same
1810 module is available from multiple packages, or is present in both the
1811 current package being built and an external package.
1812
1813 The special package name ``this`` can be used to refer to the current
1814 package being built.
1815
1816 .. note::
1817    You probably don't need to use this feature, it was added mainly so that we
1818    can build backwards-compatible versions of packages when APIs change. It can
1819    lead to fragile dependencies in the common case: modules occasionally move
1820    from one package to another, rendering any package-qualified imports broken.
1821    See also :ref:`package-thinning-and-renaming` for an alternative way of
1822    disambiguating between module names.
1823
1824 .. _safe-imports-ext:
1825
1826 Safe imports
1827 ~~~~~~~~~~~~
1828
1829 .. ghc-flag:: -XSafe
1830               -XTrustworthy
1831               -XUnsafe
1832     :noindex:
1833
1834     :since: 7.2
1835
1836     Declare the Safe Haskell state of the current module.
1837
1838 With the :ghc-flag:`-XSafe`, :ghc-flag:`-XTrustworthy` and :ghc-flag:`-XUnsafe`
1839 language flags, GHC extends the import declaration syntax to take an optional
1840 ``safe`` keyword after the ``import`` keyword. This feature is part of the Safe
1841 Haskell GHC extension. For example: ::
1842
1843     import safe qualified Network.Socket as NS
1844
1845 would import the module ``Network.Socket`` with compilation only
1846 succeeding if ``Network.Socket`` can be safely imported. For a description of
1847 when a import is considered safe see :ref:`safe-haskell`.
1848
1849 .. _explicit-namespaces:
1850
1851 Explicit namespaces in import/export
1852 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1853
1854 .. ghc-flag:: -XExplicitNamespaces
1855
1856     :since: 7.6.1
1857
1858     Enable use of explicit namespaces in module export lists.
1859
1860 In an import or export list, such as ::
1861
1862       module M( f, (++) ) where ...
1863         import N( f, (++) )
1864         ...
1865
1866 the entities ``f`` and ``(++)`` are *values*. However, with type
1867 operators (:ref:`type-operators`) it becomes possible to declare
1868 ``(++)`` as a *type constructor*. In that case, how would you export or
1869 import it?
1870
1871 The :ghc-flag:`-XExplicitNamespaces` extension allows you to prefix the name of
1872 a type constructor in an import or export list with "``type``" to
1873 disambiguate this case, thus: ::
1874
1875       module M( f, type (++) ) where ...
1876         import N( f, type (++) )
1877         ...
1878       module N( f, type (++) ) where
1879         data family a ++ b = L a | R b
1880
1881 The extension :ghc-flag:`-XExplicitNamespaces` is implied by
1882 :ghc-flag:`-XTypeOperators` and (for some reason) by :ghc-flag:`-XTypeFamilies`.
1883
1884 In addition, with :ghc-flag:`-XPatternSynonyms` you can prefix the name of a
1885 data constructor in an import or export list with the keyword
1886 ``pattern``, to allow the import or export of a data constructor without
1887 its parent type constructor (see :ref:`patsyn-impexp`).
1888
1889 .. _syntax-stolen:
1890
1891 Summary of stolen syntax
1892 ------------------------
1893
1894 Turning on an option that enables special syntax *might* cause working
1895 Haskell 98 code to fail to compile, perhaps because it uses a variable
1896 name which has become a reserved word. This section lists the syntax
1897 that is "stolen" by language extensions. We use notation and nonterminal
1898 names from the Haskell 98 lexical syntax (see the Haskell 98 Report). We
1899 only list syntax changes here that might affect existing working
1900 programs (i.e. "stolen" syntax). Many of these extensions will also
1901 enable new context-free syntax, but in all cases programs written to use
1902 the new syntax would not be compilable without the option enabled.
1903
1904 There are two classes of special syntax:
1905
1906 -  New reserved words and symbols: character sequences which are no
1907    longer available for use as identifiers in the program.
1908
1909 -  Other special syntax: sequences of characters that have a different
1910    meaning when this particular option is turned on.
1911
1912 The following syntax is stolen:
1913
1914 ``forall``
1915     .. index::
1916        single: forall
1917
1918     Stolen (in types) by: :ghc-flag:`-XExplicitForAll`, and hence by
1919     :ghc-flag:`-XScopedTypeVariables`, :ghc-flag:`-XLiberalTypeSynonyms`,
1920     :ghc-flag:`-XRankNTypes`, :ghc-flag:`-XExistentialQuantification`
1921
1922 ``mdo``
1923     .. index::
1924        single: mdo
1925
1926     Stolen by: :ghc-flag:`-XRecursiveDo`
1927
1928 ``foreign``
1929     .. index::
1930        single: foreign
1931
1932     Stolen by: :ghc-flag:`-XForeignFunctionInterface`
1933
1934 ``rec``, ``proc``, ``-<``, ``>-``, ``-<<``, ``>>-``, ``(|``, ``|)``
1935     .. index::
1936        single: proc
1937
1938     Stolen by: :ghc-flag:`-XArrows`
1939
1940 ``?varid``
1941     .. index::
1942        single: implicit parameters
1943
1944     Stolen by: :ghc-flag:`-XImplicitParams`
1945
1946 ``[|``, ``[e|``, ``[p|``, ``[d|``, ``[t|``, ``[||``, ``[e||``
1947     .. index::
1948        single: Quasi-quotes
1949
1950     Stolen by: :ghc-flag:`-XQuasiQuotes`. Moreover, this introduces an ambiguity
1951     with list comprehension syntax. See the
1952     :ref:`discussion on quasi-quoting <quasi-quotes-list-comprehension-ambiguity>`
1953     for details.
1954
1955 ``$(``, ``$$(``, ``$varid``, ``$$varid``
1956     .. index::
1957        single: Template Haskell
1958
1959     Stolen by: :ghc-flag:`-XTemplateHaskell`
1960
1961 ``[varid|``
1962     .. index::
1963        single: quasi-quotation
1964
1965     Stolen by: :ghc-flag:`-XQuasiQuotes`
1966
1967 ⟨varid⟩, ``#``\ ⟨char⟩, ``#``, ⟨string⟩, ``#``, ⟨integer⟩, ``#``, ⟨float⟩, ``#``, ⟨float⟩, ``##``
1968     Stolen by: :ghc-flag:`-XMagicHash`
1969
1970 ``(#``, ``#)``
1971     Stolen by: :ghc-flag:`-XUnboxedTuples`
1972
1973 ⟨varid⟩, ``!``, ⟨varid⟩
1974     Stolen by: :ghc-flag:`-XBangPatterns`
1975
1976 ``pattern``
1977     Stolen by: :ghc-flag:`-XPatternSynonyms`
1978
1979 .. _data-type-extensions:
1980
1981 Extensions to data types and type synonyms
1982 ==========================================
1983
1984 .. _nullary-types:
1985
1986 Data types with no constructors
1987 -------------------------------
1988
1989 .. ghc-flag:: -XEmptyDataDecls
1990
1991     Allow definition of empty ``data`` types.
1992
1993 With the :ghc-flag:`-XEmptyDataDecls` flag (or equivalent ``LANGUAGE`` pragma), GHC
1994 lets you declare a data type with no constructors. For example: ::
1995
1996       data S      -- S :: *
1997       data T a    -- T :: * -> *
1998
1999 Syntactically, the declaration lacks the "= constrs" part. The type can
2000 be parameterised over types of any kind, but if the kind is not ``*``
2001 then an explicit kind annotation must be used (see :ref:`kinding`).
2002
2003 Such data types have only one value, namely bottom. Nevertheless, they
2004 can be useful when defining "phantom types".
2005
2006 .. _datatype-contexts:
2007
2008 Data type contexts
2009 ------------------
2010
2011 .. ghc-flag:: -XDatatypeContexts
2012
2013     :since: 7.0.1
2014
2015     Allow contexts on ``data`` types.
2016
2017 Haskell allows datatypes to be given contexts, e.g. ::
2018
2019     data Eq a => Set a = NilSet | ConsSet a (Set a)
2020
2021 give constructors with types: ::
2022
2023     NilSet :: Set a
2024     ConsSet :: Eq a => a -> Set a -> Set a
2025
2026 This is widely considered a misfeature, and is going to be removed from
2027 the language. In GHC, it is controlled by the deprecated extension
2028 ``DatatypeContexts``.
2029
2030 .. _infix-tycons:
2031
2032 Infix type constructors, classes, and type variables
2033 ----------------------------------------------------
2034
2035 GHC allows type constructors, classes, and type variables to be
2036 operators, and to be written infix, very much like expressions. More
2037 specifically:
2038
2039 -  A type constructor or class can be any non-reserved operator.
2040    Symbols used in types are always like capitalized identifiers; they
2041    are never variables. Note that this is different from the lexical
2042    syntax of data constructors, which are required to begin with a
2043    ``:``.
2044
2045 -  Data type and type-synonym declarations can be written infix,
2046    parenthesised if you want further arguments. E.g. ::
2047
2048          data a :*: b = Foo a b
2049          type a :+: b = Either a b
2050          class a :=: b where ...
2051
2052          data (a :**: b) x = Baz a b x
2053          type (a :++: b) y = Either (a,b) y
2054
2055 -  Types, and class constraints, can be written infix. For example ::
2056
2057          x :: Int :*: Bool
2058          f :: (a :=: b) => a -> b
2059
2060 -  Back-quotes work as for expressions, both for type constructors and
2061    type variables; e.g. ``Int `Either` Bool``, or ``Int `a` Bool``.
2062    Similarly, parentheses work the same; e.g. ``(:*:) Int Bool``.
2063
2064 -  Fixities may be declared for type constructors, or classes, just as
2065    for data constructors. However, one cannot distinguish between the
2066    two in a fixity declaration; a fixity declaration sets the fixity for
2067    a data constructor and the corresponding type constructor. For
2068    example: ::
2069
2070          infixl 7 T, :*:
2071
2072    sets the fixity for both type constructor ``T`` and data constructor
2073    ``T``, and similarly for ``:*:``. ``Int `a` Bool``.
2074
2075 -  Function arrow is ``infixr`` with fixity 0 (this might change; it's
2076    not clear what it should be).
2077
2078 .. _type-operators:
2079
2080 Type operators
2081 --------------
2082
2083 .. ghc-flag:: -XTypeOperators
2084
2085     :implies: :ghc-flag:`-XExplicitNamespaces`
2086
2087     Allow the use and definition of types with operator names.
2088
2089 In types, an operator symbol like ``(+)`` is normally treated as a type
2090 *variable*, just like ``a``. Thus in Haskell 98 you can say
2091
2092 ::
2093
2094     type T (+) = ((+), (+))
2095     -- Just like: type T a = (a,a)
2096
2097     f :: T Int -> Int
2098     f (x,y)= x
2099
2100 As you can see, using operators in this way is not very useful, and
2101 Haskell 98 does not even allow you to write them infix.
2102
2103 The language :ghc-flag:`-XTypeOperators` changes this behaviour:
2104
2105 -  Operator symbols become type *constructors* rather than type
2106    *variables*.
2107
2108 -  Operator symbols in types can be written infix, both in definitions
2109    and uses. For example: ::
2110
2111        data a + b = Plus a b
2112        type Foo = Int + Bool
2113
2114 -  There is now some potential ambiguity in import and export lists; for
2115    example if you write ``import M( (+) )`` do you mean the *function*
2116    ``(+)`` or the *type constructor* ``(+)``? The default is the former,
2117    but with :ghc-flag:`-XExplicitNamespaces` (which is implied by
2118    :ghc-flag:`-XTypeOperators`) GHC allows you to specify the latter by
2119    preceding it with the keyword ``type``, thus: ::
2120
2121        import M( type (+) )
2122
2123    See :ref:`explicit-namespaces`.
2124
2125 -  The fixity of a type operator may be set using the usual fixity
2126    declarations but, as in :ref:`infix-tycons`, the function and type
2127    constructor share a single fixity.
2128
2129 .. _type-synonyms:
2130
2131 Liberalised type synonyms
2132 -------------------------
2133
2134 .. ghc-flag:: -XLiberalTypeSynonyms
2135
2136     :implies: :ghc-flag:`-XExplicitForAll`
2137
2138     Relax many of the Haskell 98 rules on type synonym definitions.
2139
2140 Type synonyms are like macros at the type level, but Haskell 98 imposes
2141 many rules on individual synonym declarations. With the
2142 :ghc-flag:`-XLiberalTypeSynonyms` extension, GHC does validity checking on types
2143 *only after expanding type synonyms*. That means that GHC can be very
2144 much more liberal about type synonyms than Haskell 98.
2145
2146 -  You can write a ``forall`` (including overloading) in a type synonym,
2147    thus: ::
2148
2149          type Discard a = forall b. Show b => a -> b -> (a, String)
2150
2151          f :: Discard a
2152          f x y = (x, show y)
2153
2154          g :: Discard Int -> (Int,String)    -- A rank-2 type
2155          g f = f 3 True
2156
2157 -  If you also use :ghc-flag:`-XUnboxedTuples`, you can write an unboxed tuple
2158    in a type synonym: ::
2159
2160          type Pr = (# Int, Int #)
2161
2162          h :: Int -> Pr
2163          h x = (# x, x #)
2164
2165 -  You can apply a type synonym to a forall type: ::
2166
2167          type Foo a = a -> a -> Bool
2168
2169          f :: Foo (forall b. b->b)
2170
2171    After expanding the synonym, ``f`` has the legal (in GHC) type: ::
2172
2173          f :: (forall b. b->b) -> (forall b. b->b) -> Bool
2174
2175 -  You can apply a type synonym to a partially applied type synonym: ::
2176
2177          type Generic i o = forall x. i x -> o x
2178          type Id x = x
2179
2180          foo :: Generic Id []
2181
2182    After expanding the synonym, ``foo`` has the legal (in GHC) type: ::
2183
2184          foo :: forall x. x -> [x]
2185
2186 GHC currently does kind checking before expanding synonyms (though even
2187 that could be changed).
2188
2189 After expanding type synonyms, GHC does validity checking on types,
2190 looking for the following malformedness which isn't detected simply by
2191 kind checking:
2192
2193 -  Type constructor applied to a type involving for-alls (if
2194    :ghc-flag:`-XImpredicativeTypes` is off)
2195
2196 -  Partially-applied type synonym.
2197
2198 So, for example, this will be rejected: ::
2199
2200       type Pr = forall a. a
2201
2202       h :: [Pr]
2203       h = ...
2204
2205 because GHC does not allow type constructors applied to for-all types.
2206
2207 .. _existential-quantification:
2208
2209 Existentially quantified data constructors
2210 ------------------------------------------
2211
2212 .. ghc-flag:: -XExistentialQuantification
2213
2214     :implies: :ghc-flag:`-XExplicitForAll`
2215
2216     Allow existentially quantified type variables in types.
2217
2218 The idea of using existential quantification in data type declarations
2219 was suggested by Perry, and implemented in Hope+ (Nigel Perry, *The
2220 Implementation of Practical Functional Programming Languages*, PhD
2221 Thesis, University of London, 1991). It was later formalised by Laufer
2222 and Odersky (*Polymorphic type inference and abstract data types*,
2223 TOPLAS, 16(5), pp. 1411-1430, 1994). It's been in Lennart Augustsson's
2224 ``hbc`` Haskell compiler for several years, and proved very useful.
2225 Here's the idea. Consider the declaration: ::
2226
2227       data Foo = forall a. MkFoo a (a -> Bool)
2228                | Nil
2229
2230 The data type ``Foo`` has two constructors with types: ::
2231
2232       MkFoo :: forall a. a -> (a -> Bool) -> Foo
2233       Nil   :: Foo
2234
2235 Notice that the type variable ``a`` in the type of ``MkFoo`` does not
2236 appear in the data type itself, which is plain ``Foo``. For example, the
2237 following expression is fine: ::
2238
2239       [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]
2240
2241 Here, ``(MkFoo 3 even)`` packages an integer with a function ``even``
2242 that maps an integer to ``Bool``; and ``MkFoo 'c'
2243 isUpper`` packages a character with a compatible function. These two
2244 things are each of type ``Foo`` and can be put in a list.
2245
2246 What can we do with a value of type ``Foo``? In particular, what
2247 happens when we pattern-match on ``MkFoo``? ::
2248
2249       f (MkFoo val fn) = ???
2250
2251 Since all we know about ``val`` and ``fn`` is that they are compatible,
2252 the only (useful) thing we can do with them is to apply ``fn`` to
2253 ``val`` to get a boolean. For example: ::
2254
2255       f :: Foo -> Bool
2256       f (MkFoo val fn) = fn val
2257
2258 What this allows us to do is to package heterogeneous values together
2259 with a bunch of functions that manipulate them, and then treat that
2260 collection of packages in a uniform manner. You can express quite a bit
2261 of object-oriented-like programming this way.
2262
2263 .. _existential:
2264
2265 Why existential?
2266 ~~~~~~~~~~~~~~~~
2267
2268 What has this to do with *existential* quantification? Simply that
2269 ``MkFoo`` has the (nearly) isomorphic type ::
2270
2271       MkFoo :: (exists a . (a, a -> Bool)) -> Foo
2272
2273 But Haskell programmers can safely think of the ordinary *universally*
2274 quantified type given above, thereby avoiding adding a new existential
2275 quantification construct.
2276
2277 .. _existential-with-context:
2278
2279 Existentials and type classes
2280 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2281
2282 An easy extension is to allow arbitrary contexts before the constructor.
2283 For example: ::
2284
2285     data Baz = forall a. Eq a => Baz1 a a
2286              | forall b. Show b => Baz2 b (b -> b)
2287
2288 The two constructors have the types you'd expect: ::
2289
2290     Baz1 :: forall a. Eq a => a -> a -> Baz
2291     Baz2 :: forall b. Show b => b -> (b -> b) -> Baz
2292
2293 But when pattern matching on ``Baz1`` the matched values can be compared
2294 for equality, and when pattern matching on ``Baz2`` the first matched
2295 value can be converted to a string (as well as applying the function to
2296 it). So this program is legal: ::
2297
2298       f :: Baz -> String
2299       f (Baz1 p q) | p == q    = "Yes"
2300                    | otherwise = "No"
2301       f (Baz2 v fn)            = show (fn v)
2302
2303 Operationally, in a dictionary-passing implementation, the constructors
2304 ``Baz1`` and ``Baz2`` must store the dictionaries for ``Eq`` and
2305 ``Show`` respectively, and extract it on pattern matching.
2306
2307 .. _existential-records:
2308
2309 Record Constructors
2310 ~~~~~~~~~~~~~~~~~~~
2311
2312 GHC allows existentials to be used with records syntax as well. For
2313 example: ::
2314
2315     data Counter a = forall self. NewCounter
2316         { _this    :: self
2317         , _inc     :: self -> self
2318         , _display :: self -> IO ()
2319         , tag      :: a
2320         }
2321
2322 Here ``tag`` is a public field, with a well-typed selector function
2323 ``tag :: Counter a -> a``. The ``self`` type is hidden from the outside;
2324 any attempt to apply ``_this``, ``_inc`` or ``_display`` as functions
2325 will raise a compile-time error. In other words, *GHC defines a record
2326 selector function only for fields whose type does not mention the
2327 existentially-quantified variables*. (This example used an underscore in
2328 the fields for which record selectors will not be defined, but that is
2329 only programming style; GHC ignores them.)
2330
2331 To make use of these hidden fields, we need to create some helper
2332 functions: ::
2333
2334     inc :: Counter a -> Counter a
2335     inc (NewCounter x i d t) = NewCounter
2336         { _this = i x, _inc = i, _display = d, tag = t }
2337
2338     display :: Counter a -> IO ()
2339     display NewCounter{ _this = x, _display = d } = d x
2340
2341 Now we can define counters with different underlying implementations: ::
2342
2343     counterA :: Counter String
2344     counterA = NewCounter
2345         { _this = 0, _inc = (1+), _display = print, tag = "A" }
2346
2347     counterB :: Counter String
2348     counterB = NewCounter
2349         { _this = "", _inc = ('#':), _display = putStrLn, tag = "B" }
2350
2351     main = do
2352         display (inc counterA)         -- prints "1"
2353         display (inc (inc counterB))   -- prints "##"
2354
2355 Record update syntax is supported for existentials (and GADTs): ::
2356
2357     setTag :: Counter a -> a -> Counter a
2358     setTag obj t = obj{ tag = t }
2359
2360 The rule for record update is this:
2361
2362     the types of the updated fields may mention only the universally-quantified
2363     type variables of the data constructor. For GADTs, the field may mention
2364     only types that appear as a simple type-variable argument in the
2365     constructor's result type.
2366
2367 For example: ::
2368
2369     data T a b where { T1 { f1::a, f2::b, f3::(b,c) } :: T a b } -- c is existential
2370     upd1 t x = t { f1=x }   -- OK:   upd1 :: T a b -> a' -> T a' b
2371     upd2 t x = t { f3=x }   -- BAD   (f3's type mentions c, which is
2372                             --        existentially quantified)
2373
2374     data G a b where { G1 { g1::a, g2::c } :: G a [c] }
2375     upd3 g x = g { g1=x }   -- OK:   upd3 :: G a b -> c -> G c b
2376     upd4 g x = g { g2=x }   -- BAD (f2's type mentions c, which is not a simple
2377                             --      type-variable argument in G1's result type)
2378
2379 Restrictions
2380 ~~~~~~~~~~~~
2381
2382 There are several restrictions on the ways in which existentially-quantified
2383 constructors can be used.
2384
2385 -  When pattern matching, each pattern match introduces a new, distinct,
2386    type for each existential type variable. These types cannot be
2387    unified with any other type, nor can they escape from the scope of
2388    the pattern match. For example, these fragments are incorrect: ::
2389
2390        f1 (MkFoo a f) = a
2391
2392    Here, the type bound by ``MkFoo`` "escapes", because ``a`` is the
2393    result of ``f1``. One way to see why this is wrong is to ask what
2394    type ``f1`` has: ::
2395
2396          f1 :: Foo -> a             -- Weird!
2397
2398    What is this "``a``" in the result type? Clearly we don't mean this: ::
2399
2400          f1 :: forall a. Foo -> a   -- Wrong!
2401
2402    The original program is just plain wrong. Here's another sort of
2403    error ::
2404
2405          f2 (Baz1 a b) (Baz1 p q) = a==q
2406
2407    It's ok to say ``a==b`` or ``p==q``, but ``a==q`` is wrong because it
2408    equates the two distinct types arising from the two ``Baz1``
2409    constructors.
2410
2411 -  You can't pattern-match on an existentially quantified constructor in
2412    a ``let`` or ``where`` group of bindings. So this is illegal: ::
2413
2414          f3 x = a==b where { Baz1 a b = x }
2415
2416    Instead, use a ``case`` expression: ::
2417
2418          f3 x = case x of Baz1 a b -> a==b
2419
2420    In general, you can only pattern-match on an existentially-quantified
2421    constructor in a ``case`` expression or in the patterns of a function
2422    definition. The reason for this restriction is really an
2423    implementation one. Type-checking binding groups is already a
2424    nightmare without existentials complicating the picture. Also an
2425    existential pattern binding at the top level of a module doesn't make
2426    sense, because it's not clear how to prevent the
2427    existentially-quantified type "escaping". So for now, there's a
2428    simple-to-state restriction. We'll see how annoying it is.
2429
2430 -  You can't use existential quantification for ``newtype``
2431    declarations. So this is illegal: ::
2432
2433          newtype T = forall a. Ord a => MkT a
2434
2435    Reason: a value of type ``T`` must be represented as a pair of a
2436    dictionary for ``Ord t`` and a value of type ``t``. That contradicts
2437    the idea that ``newtype`` should have no concrete representation. You
2438    can get just the same efficiency and effect by using ``data`` instead
2439    of ``newtype``. If there is no overloading involved, then there is
2440    more of a case for allowing an existentially-quantified ``newtype``,
2441    because the ``data`` version does carry an implementation cost, but
2442    single-field existentially quantified constructors aren't much use.
2443    So the simple restriction (no existential stuff on ``newtype``)
2444    stands, unless there are convincing reasons to change it.
2445
2446 -  You can't use ``deriving`` to define instances of a data type with
2447    existentially quantified data constructors. Reason: in most cases it
2448    would not make sense. For example:; ::
2449
2450        data T = forall a. MkT [a] deriving( Eq )
2451
2452    To derive ``Eq`` in the standard way we would need to have equality
2453    between the single component of two ``MkT`` constructors: ::
2454
2455        instance Eq T where
2456          (MkT a) == (MkT b) = ???
2457
2458    But ``a`` and ``b`` have distinct types, and so can't be compared.
2459    It's just about possible to imagine examples in which the derived
2460    instance would make sense, but it seems altogether simpler simply to
2461    prohibit such declarations. Define your own instances!
2462
2463 .. _gadt-style:
2464
2465 Declaring data types with explicit constructor signatures
2466 ---------------------------------------------------------
2467
2468 .. ghc-flag:: -XGADTSyntax
2469
2470     :since: 7.2
2471
2472     Allow the use of GADT syntax in data type definitions (but not GADTs
2473     themselves; for this see :ghc-flag:`-XGADTs`)
2474
2475 When the ``GADTSyntax`` extension is enabled, GHC allows you to declare
2476 an algebraic data type by giving the type signatures of constructors
2477 explicitly. For example: ::
2478
2479       data Maybe a where
2480           Nothing :: Maybe a
2481           Just    :: a -> Maybe a
2482
2483 The form is called a "GADT-style declaration" because Generalised
2484 Algebraic Data Types, described in :ref:`gadt`, can only be declared
2485 using this form.
2486
2487 Notice that GADT-style syntax generalises existential types
2488 (:ref:`existential-quantification`). For example, these two declarations
2489 are equivalent: ::
2490
2491       data Foo = forall a. MkFoo a (a -> Bool)
2492       data Foo' where { MKFoo :: a -> (a->Bool) -> Foo' }
2493
2494 Any data type that can be declared in standard Haskell 98 syntax can
2495 also be declared using GADT-style syntax. The choice is largely
2496 stylistic, but GADT-style declarations differ in one important respect:
2497 they treat class constraints on the data constructors differently.
2498 Specifically, if the constructor is given a type-class context, that
2499 context is made available by pattern matching. For example: ::
2500
2501       data Set a where
2502         MkSet :: Eq a => [a] -> Set a
2503
2504       makeSet :: Eq a => [a] -> Set a
2505       makeSet xs = MkSet (nub xs)
2506
2507       insert :: a -> Set a -> Set a
2508       insert a (MkSet as) | a `elem` as = MkSet as
2509                           | otherwise   = MkSet (a:as)
2510
2511 A use of ``MkSet`` as a constructor (e.g. in the definition of
2512 ``makeSet``) gives rise to a ``(Eq a)`` constraint, as you would expect.
2513 The new feature is that pattern-matching on ``MkSet`` (as in the
2514 definition of ``insert``) makes *available* an ``(Eq a)`` context. In
2515 implementation terms, the ``MkSet`` constructor has a hidden field that
2516 stores the ``(Eq a)`` dictionary that is passed to ``MkSet``; so when
2517 pattern-matching that dictionary becomes available for the right-hand
2518 side of the match. In the example, the equality dictionary is used to
2519 satisfy the equality constraint generated by the call to ``elem``, so
2520 that the type of ``insert`` itself has no ``Eq`` constraint.
2521
2522 For example, one possible application is to reify dictionaries: ::
2523
2524        data NumInst a where
2525          MkNumInst :: Num a => NumInst a
2526
2527        intInst :: NumInst Int
2528        intInst = MkNumInst
2529
2530        plus :: NumInst a -> a -> a -> a
2531        plus MkNumInst p q = p + q
2532
2533 Here, a value of type ``NumInst a`` is equivalent to an explicit
2534 ``(Num a)`` dictionary.
2535
2536 All this applies to constructors declared using the syntax of
2537 :ref:`existential-with-context`. For example, the ``NumInst`` data type
2538 above could equivalently be declared like this: ::
2539
2540        data NumInst a
2541           = Num a => MkNumInst (NumInst a)
2542
2543 Notice that, unlike the situation when declaring an existential, there
2544 is no ``forall``, because the ``Num`` constrains the data type's
2545 universally quantified type variable ``a``. A constructor may have both
2546 universal and existential type variables: for example, the following two
2547 declarations are equivalent: ::
2548
2549        data T1 a
2550         = forall b. (Num a, Eq b) => MkT1 a b
2551        data T2 a where
2552         MkT2 :: (Num a, Eq b) => a -> b -> T2 a
2553
2554 All this behaviour contrasts with Haskell 98's peculiar treatment of
2555 contexts on a data type declaration (Section 4.2.1 of the Haskell 98
2556 Report). In Haskell 98 the definition ::
2557
2558       data Eq a => Set' a = MkSet' [a]
2559
2560 gives ``MkSet'`` the same type as ``MkSet`` above. But instead of
2561 *making available* an ``(Eq a)`` constraint, pattern-matching on
2562 ``MkSet'`` *requires* an ``(Eq a)`` constraint! GHC faithfully
2563 implements this behaviour, odd though it is. But for GADT-style
2564 declarations, GHC's behaviour is much more useful, as well as much more
2565 intuitive.
2566
2567 The rest of this section gives further details about GADT-style data
2568 type declarations.
2569
2570 -  The result type of each data constructor must begin with the type
2571    constructor being defined. If the result type of all constructors has
2572    the form ``T a1 ... an``, where ``a1 ... an`` are distinct type
2573    variables, then the data type is *ordinary*; otherwise is a
2574    *generalised* data type (:ref:`gadt`).
2575
2576 -  As with other type signatures, you can give a single signature for
2577    several data constructors. In this example we give a single signature
2578    for ``T1`` and ``T2``: ::
2579
2580          data T a where
2581            T1,T2 :: a -> T a
2582            T3 :: T a
2583
2584 -  The type signature of each constructor is independent, and is
2585    implicitly universally quantified as usual. In particular, the type
2586    variable(s) in the "``data T a where``" header have no scope, and
2587    different constructors may have different universally-quantified type
2588    variables: ::
2589
2590          data T a where        -- The 'a' has no scope
2591            T1,T2 :: b -> T b   -- Means forall b. b -> T b
2592            T3 :: T a           -- Means forall a. T a
2593
2594 -  A constructor signature may mention type class constraints, which can
2595    differ for different constructors. For example, this is fine: ::
2596
2597          data T a where
2598            T1 :: Eq b => b -> b -> T b
2599            T2 :: (Show c, Ix c) => c -> [c] -> T c
2600
2601    When pattern matching, these constraints are made available to
2602    discharge constraints in the body of the match. For example: ::
2603
2604          f :: T a -> String
2605          f (T1 x y) | x==y      = "yes"
2606                     | otherwise = "no"
2607          f (T2 a b)             = show a
2608
2609    Note that ``f`` is not overloaded; the ``Eq`` constraint arising from
2610    the use of ``==`` is discharged by the pattern match on ``T1`` and
2611    similarly the ``Show`` constraint arising from the use of ``show``.
2612
2613 -  Unlike a Haskell-98-style data type declaration, the type variable(s)
2614    in the "``data Set a where``" header have no scope. Indeed, one can
2615    write a kind signature instead: ::
2616
2617          data Set :: * -> * where ...
2618
2619    or even a mixture of the two: ::
2620
2621          data Bar a :: (* -> *) -> * where ...
2622
2623    The type variables (if given) may be explicitly kinded, so we could
2624    also write the header for ``Foo`` like this: ::
2625
2626          data Bar a (b :: * -> *) where ...
2627
2628 -  You can use strictness annotations, in the obvious places in the
2629    constructor type: ::
2630
2631          data Term a where
2632              Lit    :: !Int -> Term Int
2633              If     :: Term Bool -> !(Term a) -> !(Term a) -> Term a
2634              Pair   :: Term a -> Term b -> Term (a,b)
2635
2636 -  You can use a ``deriving`` clause on a GADT-style data type
2637    declaration. For example, these two declarations are equivalent ::
2638
2639          data Maybe1 a where {
2640              Nothing1 :: Maybe1 a ;
2641              Just1    :: a -> Maybe1 a
2642            } deriving( Eq, Ord )
2643
2644          data Maybe2 a = Nothing2 | Just2 a
2645               deriving( Eq, Ord )
2646
2647 -  The type signature may have quantified type variables that do not
2648    appear in the result type: ::
2649
2650          data Foo where
2651             MkFoo :: a -> (a->Bool) -> Foo
2652             Nil   :: Foo
2653
2654    Here the type variable ``a`` does not appear in the result type of
2655    either constructor. Although it is universally quantified in the type
2656    of the constructor, such a type variable is often called
2657    "existential". Indeed, the above declaration declares precisely the
2658    same type as the ``data Foo`` in :ref:`existential-quantification`.
2659
2660    The type may contain a class context too, of course: ::
2661
2662          data Showable where
2663            MkShowable :: Show a => a -> Showable
2664
2665 -  You can use record syntax on a GADT-style data type declaration: ::
2666
2667          data Person where
2668              Adult :: { name :: String, children :: [Person] } -> Person
2669              Child :: Show a => { name :: !String, funny :: a } -> Person
2670
2671    As usual, for every constructor that has a field ``f``, the type of
2672    field ``f`` must be the same (modulo alpha conversion). The ``Child``
2673    constructor above shows that the signature may have a context,
2674    existentially-quantified variables, and strictness annotations, just
2675    as in the non-record case. (NB: the "type" that follows the
2676    double-colon is not really a type, because of the record syntax and
2677    strictness annotations. A "type" of this form can appear only in a
2678    constructor signature.)
2679
2680 -  Record updates are allowed with GADT-style declarations, only fields
2681    that have the following property: the type of the field mentions no
2682    existential type variables.
2683
2684 -  As in the case of existentials declared using the Haskell-98-like
2685    record syntax (:ref:`existential-records`), record-selector functions
2686    are generated only for those fields that have well-typed selectors.
2687    Here is the example of that section, in GADT-style syntax: ::
2688
2689        data Counter a where
2690            NewCounter :: { _this    :: self
2691                          , _inc     :: self -> self
2692                          , _display :: self -> IO ()
2693                          , tag      :: a
2694                          } -> Counter a
2695
2696    As before, only one selector function is generated here, that for
2697    ``tag``. Nevertheless, you can still use all the field names in
2698    pattern matching and record construction.
2699
2700 -  In a GADT-style data type declaration there is no obvious way to
2701    specify that a data constructor should be infix, which makes a
2702    difference if you derive ``Show`` for the type. (Data constructors
2703    declared infix are displayed infix by the derived ``show``.) So GHC
2704    implements the following design: a data constructor declared in a
2705    GADT-style data type declaration is displayed infix by ``Show`` iff
2706    (a) it is an operator symbol, (b) it has two arguments, (c) it has a
2707    programmer-supplied fixity declaration. For example
2708
2709    ::
2710
2711           infix 6 (:--:)
2712           data T a where
2713             (:--:) :: Int -> Bool -> T Int
2714
2715 .. _gadt:
2716
2717 Generalised Algebraic Data Types (GADTs)
2718 ----------------------------------------
2719
2720 .. ghc-flag:: -XGADTs
2721
2722     :implies: :ghc-flag:`-XMonoLocalBinds`, :ghc-flag:`-XGADTSyntax`
2723
2724     Allow use of Generalised Algebraic Data Types (GADTs).
2725
2726 Generalised Algebraic Data Types generalise ordinary algebraic data
2727 types by allowing constructors to have richer return types. Here is an
2728 example: ::
2729
2730       data Term a where
2731           Lit    :: Int -> Term Int
2732           Succ   :: Term Int -> Term Int
2733           IsZero :: Term Int -> Term Bool
2734           If     :: Term Bool -> Term a -> Term a -> Term a
2735           Pair   :: Term a -> Term b -> Term (a,b)
2736
2737 Notice that the return type of the constructors is not always
2738 ``Term a``, as is the case with ordinary data types. This generality
2739 allows us to write a well-typed ``eval`` function for these ``Terms``: ::
2740
2741       eval :: Term a -> a
2742       eval (Lit i)      = i
2743       eval (Succ t)     = 1 + eval t
2744       eval (IsZero t)   = eval t == 0
2745       eval (If b e1 e2) = if eval b then eval e1 else eval e2
2746       eval (Pair e1 e2) = (eval e1, eval e2)
2747
2748 The key point about GADTs is that *pattern matching causes type
2749 refinement*. For example, in the right hand side of the equation ::
2750
2751       eval :: Term a -> a
2752       eval (Lit i) =  ...
2753
2754 the type ``a`` is refined to ``Int``. That's the whole point! A precise
2755 specification of the type rules is beyond what this user manual aspires
2756 to, but the design closely follows that described in the paper `Simple
2757 unification-based type inference for
2758 GADTs <http://research.microsoft.com/%7Esimonpj/papers/gadt/>`__, (ICFP
2759 2006). The general principle is this: *type refinement is only carried
2760 out based on user-supplied type annotations*. So if no type signature is
2761 supplied for ``eval``, no type refinement happens, and lots of obscure
2762 error messages will occur. However, the refinement is quite general. For
2763 example, if we had: ::
2764
2765       eval :: Term a -> a -> a
2766       eval (Lit i) j =  i+j
2767
2768 the pattern match causes the type ``a`` to be refined to ``Int``
2769 (because of the type of the constructor ``Lit``), and that refinement
2770 also applies to the type of ``j``, and the result type of the ``case``
2771 expression. Hence the addition ``i+j`` is legal.
2772
2773 These and many other examples are given in papers by Hongwei Xi, and Tim
2774 Sheard. There is a longer introduction `on the
2775 wiki <http://www.haskell.org/haskellwiki/GADT>`__, and Ralf Hinze's `Fun
2776 with phantom
2777 types <http://www.cs.ox.ac.uk/ralf.hinze/publications/With.pdf>`__ also
2778 has a number of examples. Note that papers may use different notation to
2779 that implemented in GHC.
2780
2781 The rest of this section outlines the extensions to GHC that support
2782 GADTs. The extension is enabled with :ghc-flag:`-XGADTs`. The :ghc-flag:`-XGADTs` flag
2783 also sets :ghc-flag:`-XGADTSyntax` and :ghc-flag:`-XMonoLocalBinds`.
2784
2785 -  A GADT can only be declared using GADT-style syntax
2786    (:ref:`gadt-style`); the old Haskell 98 syntax for data declarations
2787    always declares an ordinary data type. The result type of each
2788    constructor must begin with the type constructor being defined, but
2789    for a GADT the arguments to the type constructor can be arbitrary
2790    monotypes. For example, in the ``Term`` data type above, the type of
2791    each constructor must end with ``Term ty``, but the ``ty`` need not
2792    be a type variable (e.g. the ``Lit`` constructor).
2793
2794 -  It is permitted to declare an ordinary algebraic data type using
2795    GADT-style syntax. What makes a GADT into a GADT is not the syntax,
2796    but rather the presence of data constructors whose result type is not
2797    just ``T a b``.
2798
2799 -  You cannot use a ``deriving`` clause for a GADT; only for an ordinary
2800    data type.
2801
2802 -  As mentioned in :ref:`gadt-style`, record syntax is supported. For
2803    example:
2804
2805    ::
2806
2807          data Term a where
2808              Lit    :: { val  :: Int }      -> Term Int
2809              Succ   :: { num  :: Term Int } -> Term Int
2810              Pred   :: { num  :: Term Int } -> Term Int
2811              IsZero :: { arg  :: Term Int } -> Term Bool
2812              Pair   :: { arg1 :: Term a
2813                        , arg2 :: Term b
2814                        }                    -> Term (a,b)
2815              If     :: { cnd  :: Term Bool
2816                        , tru  :: Term a
2817                        , fls  :: Term a
2818                        }                    -> Term a
2819
2820    However, for GADTs there is the following additional constraint:
2821    every constructor that has a field ``f`` must have the same result
2822    type (modulo alpha conversion) Hence, in the above example, we cannot
2823    merge the ``num`` and ``arg`` fields above into a single name.
2824    Although their field types are both ``Term Int``, their selector
2825    functions actually have different types:
2826
2827    ::
2828
2829          num :: Term Int -> Term Int
2830          arg :: Term Bool -> Term Int
2831
2832 -  When pattern-matching against data constructors drawn from a GADT,
2833    for example in a ``case`` expression, the following rules apply:
2834
2835    -  The type of the scrutinee must be rigid.
2836
2837    -  The type of the entire ``case`` expression must be rigid.
2838
2839    -  The type of any free variable mentioned in any of the ``case``
2840       alternatives must be rigid.
2841
2842    A type is "rigid" if it is completely known to the compiler at its
2843    binding site. The easiest way to ensure that a variable a rigid type
2844    is to give it a type signature. For more precise details see `Simple
2845    unification-based type inference for
2846    GADTs <http://research.microsoft.com/%7Esimonpj/papers/gadt/>`__. The
2847    criteria implemented by GHC are given in the Appendix.
2848
2849 .. _record-system-extensions:
2850
2851 Extensions to the record system
2852 ===============================
2853
2854 .. _traditional-record-syntax:
2855
2856 Traditional record syntax
2857 -------------------------
2858
2859 .. ghc-flag:: -XNoTraditionalRecordSyntax
2860
2861     :since: 7.4.1
2862
2863     Disallow use of record syntax.
2864
2865 Traditional record syntax, such as ``C {f = x}``, is enabled by default.
2866 To disable it, you can use the :ghc-flag:`-XNoTraditionalRecordSyntax` flag.
2867
2868 .. _disambiguate-fields:
2869
2870 Record field disambiguation
2871 ---------------------------
2872
2873 .. ghc-flag:: -XDisambiguateRecordFields
2874
2875     Allow the compiler to automatically choose between identically-named
2876     record selectors based on type (if the choice is unambiguous).
2877
2878 In record construction and record pattern matching it is entirely
2879 unambiguous which field is referred to, even if there are two different
2880 data types in scope with a common field name. For example:
2881
2882 ::
2883
2884     module M where
2885       data S = MkS { x :: Int, y :: Bool }
2886
2887     module Foo where
2888       import M
2889
2890       data T = MkT { x :: Int }
2891
2892       ok1 (MkS { x = n }) = n+1   -- Unambiguous
2893       ok2 n = MkT { x = n+1 }     -- Unambiguous
2894
2895       bad1 k = k { x = 3 }        -- Ambiguous
2896       bad2 k = x k                -- Ambiguous
2897
2898 Even though there are two ``x``'s in scope, it is clear that the ``x``
2899 in the pattern in the definition of ``ok1`` can only mean the field
2900 ``x`` from type ``S``. Similarly for the function ``ok2``. However, in
2901 the record update in ``bad1`` and the record selection in ``bad2`` it is
2902 not clear which of the two types is intended.
2903
2904 Haskell 98 regards all four as ambiguous, but with the
2905 :ghc-flag:`-XDisambiguateRecordFields` flag, GHC will accept the former two. The
2906 rules are precisely the same as those for instance declarations in
2907 Haskell 98, where the method names on the left-hand side of the method
2908 bindings in an instance declaration refer unambiguously to the method of
2909 that class (provided they are in scope at all), even if there are other
2910 variables in scope with the same name. This reduces the clutter of
2911 qualified names when you import two records from different modules that
2912 use the same field name.
2913
2914 Some details:
2915
2916 -  Field disambiguation can be combined with punning (see
2917    :ref:`record-puns`). For example: ::
2918
2919        module Foo where
2920          import M
2921          x=True
2922          ok3 (MkS { x }) = x+1   -- Uses both disambiguation and punning
2923
2924 -  With :ghc-flag:`-XDisambiguateRecordFields` you can use *unqualified* field
2925    names even if the corresponding selector is only in scope *qualified*
2926    For example, assuming the same module ``M`` as in our earlier
2927    example, this is legal: ::
2928
2929        module Foo where
2930          import qualified M    -- Note qualified
2931
2932          ok4 (M.MkS { x = n }) = n+1   -- Unambiguous
2933
2934    Since the constructor ``MkS`` is only in scope qualified, you must
2935    name it ``M.MkS``, but the field ``x`` does not need to be qualified
2936    even though ``M.x`` is in scope but ``x`` is not (In effect, it is
2937    qualified by the constructor).
2938
2939 .. _duplicate-record-fields:
2940
2941 Duplicate record fields
2942 -----------------------
2943
2944 .. ghc-flag:: -XDuplicateRecordFields
2945
2946     :implies: :ghc-flag:`-XDisambiguateRecordFields`
2947     :since: 8.0.1
2948
2949     Allow definition of record types with identically-named fields.
2950
2951 Going beyond :ghc-flag:`-XDisambiguateRecordFields` (see :ref:`disambiguate-fields`),
2952 the :ghc-flag:`-XDuplicateRecordFields` extension allows multiple datatypes to be
2953 declared using the same field names in a single module. For example, it allows
2954 this: ::
2955
2956     module M where
2957       data S = MkS { x :: Int }
2958       data T = MkT { x :: Bool }
2959
2960 Uses of fields that are always unambiguous because they mention the constructor,
2961 including construction and pattern-matching, may freely use duplicated field
2962 names. For example, the following are permitted (just as with
2963 :ghc-flag:`-XDisambiguateRecordFields`): ::
2964
2965     s = MkS { x = 3 }
2966
2967     f (MkT { x = b }) = b
2968
2969 Field names used as selector functions or in record updates must be unambiguous,
2970 either because there is only one such field in scope, or because a type
2971 signature is supplied, as described in the following sections.
2972
2973 Selector functions
2974 ~~~~~~~~~~~~~~~~~~
2975
2976 Fields may be used as selector functions only if they are unambiguous, so this
2977 is still not allowed if both ``S(x)`` and ``T(x)`` are in scope: ::
2978
2979     bad r = x r
2980
2981 An ambiguous selector may be disambiguated by the type being "pushed down" to
2982 the occurrence of the selector (see :ref:`higher-rank-type-inference` for more
2983 details on what "pushed down" means). For example, the following are permitted: ::
2984
2985     ok1 = x :: S -> Int
2986
2987     ok2 :: S -> Int
2988     ok2 = x
2989
2990     ok3 = k x -- assuming we already have k :: (S -> Int) -> _
2991
2992 In addition, the datatype that is meant may be given as a type signature on the
2993 argument to the selector: ::
2994
2995     ok4 s = x (s :: S)
2996
2997 However, we do not infer the type of the argument to determine the datatype, or
2998 have any way of deferring the choice to the constraint solver. Thus the
2999 following is ambiguous: ::
3000
3001     bad :: S -> Int
3002     bad s = x s
3003
3004 Even though a field label is duplicated in its defining module, it may be
3005 possible to use the selector unambiguously elsewhere. For example, another
3006 module could import ``S(x)`` but not ``T(x)``, and then use ``x`` unambiguously.
3007
3008 Record updates
3009 ~~~~~~~~~~~~~~
3010
3011 In a record update such as ``e { x = 1 }``, if there are multiple ``x`` fields
3012 in scope, then the type of the context must fix which record datatype is
3013 intended, or a type annotation must be supplied. Consider the following
3014 definitions: ::
3015
3016     data S = MkS { foo :: Int }
3017     data T = MkT { foo :: Int, bar :: Int }
3018     data U = MkU { bar :: Int, baz :: Int }
3019
3020 Without :ghc-flag:`-XDuplicateRecordFields`, an update mentioning ``foo`` will always be
3021 ambiguous if all these definitions were in scope. When the extension is enabled,
3022 there are several options for disambiguating updates:
3023
3024 - Check for types that have all the fields being updated. For example: ::
3025
3026       f x = x { foo = 3, bar = 2 }
3027
3028   Here ``f`` must be updating ``T`` because neither ``S`` nor ``U`` have both
3029   fields.
3030
3031 - Use the type being pushed in to the record update, as in the following: ::
3032
3033       g1 :: T -> T
3034       g1 x = x { foo = 3 }
3035
3036       g2 x = x { foo = 3 } :: T
3037
3038       g3 = k (x { foo = 3 }) -- assuming we already have k :: T -> _
3039
3040 - Use an explicit type signature on the record expression, as in: ::
3041
3042       h x = (x :: T) { foo = 3 }
3043
3044 The type of the expression being updated will not be inferred, and no
3045 constraint-solving will be performed, so the following will be rejected as
3046 ambiguous: ::
3047
3048     let x :: T
3049         x = blah
3050     in x { foo = 3 }
3051
3052     \x -> [x { foo = 3 },  blah :: T ]
3053
3054     \ (x :: T) -> x { foo = 3 }
3055
3056 Import and export of record fields
3057 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3058
3059 When :ghc-flag:`-XDuplicateRecordFields` is enabled, an ambiguous field must be exported
3060 as part of its datatype, rather than at the top level. For example, the
3061 following is legal: ::
3062
3063     module M (S(x), T(..)) where
3064       data S = MkS { x :: Int }
3065       data T = MkT { x :: Bool }
3066
3067 However, this would not be permitted, because ``x`` is ambiguous: ::
3068
3069     module M (x) where ...
3070
3071 Similar restrictions apply on import.
3072
3073 .. _record-puns:
3074
3075 Record puns
3076 -----------
3077
3078 .. ghc-flag:: -XNamedFieldPuns
3079
3080     Allow use of record puns.
3081
3082 Record puns are enabled by the flag :ghc-flag:`-XNamedFieldPuns`.
3083
3084 When using records, it is common to write a pattern that binds a
3085 variable with the same name as a record field, such as: ::
3086
3087     data C = C {a :: Int}
3088     f (C {a = a}) = a
3089
3090 Record punning permits the variable name to be elided, so one can simply
3091 write ::
3092
3093     f (C {a}) = a
3094
3095 to mean the same pattern as above. That is, in a record pattern, the
3096 pattern ``a`` expands into the pattern ``a = a`` for the same name
3097 ``a``.
3098
3099 Note that:
3100
3101 -  Record punning can also be used in an expression, writing, for
3102    example, ::
3103
3104        let a = 1 in C {a}
3105
3106    instead of ::
3107
3108        let a = 1 in C {a = a}
3109
3110    The expansion is purely syntactic, so the expanded right-hand side
3111    expression refers to the nearest enclosing variable that is spelled
3112    the same as the field name.
3113
3114 -  Puns and other patterns can be mixed in the same record: ::
3115
3116        data C = C {a :: Int, b :: Int}
3117        f (C {a, b = 4}) = a
3118
3119 -  Puns can be used wherever record patterns occur (e.g. in ``let``
3120    bindings or at the top-level).
3121
3122 -  A pun on a qualified field name is expanded by stripping off the
3123    module qualifier. For example: ::
3124
3125        f (C {M.a}) = a
3126
3127    means ::
3128
3129        f (M.C {M.a = a}) = a
3130
3131    (This is useful if the field selector ``a`` for constructor ``M.C``
3132    is only in scope in qualified form.)
3133
3134 .. _record-wildcards:
3135
3136 Record wildcards
3137 ----------------
3138
3139 .. ghc-flag:: -XRecordWildCards
3140
3141     :implies: :ghc-flag:`-XDisambiguateRecordFields`.
3142
3143     Allow the use of wildcards in record construction and pattern matching.
3144
3145 Record wildcards are enabled by the flag :ghc-flag:`-XRecordWildCards`. This
3146 flag implies :ghc-flag:`-XDisambiguateRecordFields`.
3147
3148 For records with many fields, it can be tiresome to write out each field
3149 individually in a record pattern, as in ::
3150
3151     data C = C {a :: Int, b :: Int, c :: Int, d :: Int}
3152     f (C {a = 1, b = b, c = c, d = d}) = b + c + d
3153
3154 Record wildcard syntax permits a "``..``" in a record pattern, where
3155 each elided field ``f`` is replaced by the pattern ``f = f``. For
3156 example, the above pattern can be written as ::
3157
3158     f (C {a = 1, ..}) = b + c + d
3159
3160 More details:
3161
3162 -  Record wildcards in patterns can be mixed with other patterns,
3163    including puns (:ref:`record-puns`); for example, in a pattern
3164    ``(C {a = 1, b, ..})``. Additionally, record wildcards can be used
3165    wherever record patterns occur, including in ``let`` bindings and at
3166    the top-level. For example, the top-level binding ::
3167
3168        C {a = 1, ..} = e
3169
3170    defines ``b``, ``c``, and ``d``.
3171
3172 -  Record wildcards can also be used in an expression, when constructing
3173    a record. For example, ::
3174
3175        let {a = 1; b = 2; c = 3; d = 4} in C {..}
3176
3177    in place of ::
3178
3179        let {a = 1; b = 2; c = 3; d = 4} in C {a=a, b=b, c=c, d=d}
3180
3181    The expansion is purely syntactic, so the record wildcard expression
3182    refers to the nearest enclosing variables that are spelled the same
3183    as the omitted field names.
3184
3185 -  Record wildcards may *not* be used in record *updates*. For example
3186    this is illegal: ::
3187
3188        f r = r { x = 3, .. }
3189
3190 -  For both pattern and expression wildcards, the "``..``" expands to
3191    the missing *in-scope* record fields. Specifically the expansion of
3192    "``C {..}``" includes ``f`` if and only if:
3193
3194    -  ``f`` is a record field of constructor ``C``.
3195
3196    -  The record field ``f`` is in scope somehow (either qualified or
3197       unqualified).
3198
3199    -  In the case of expressions (but not patterns), the variable ``f``
3200       is in scope unqualified, and is not imported or bound at top level.
3201       For example, ``f`` can be bound by an enclosing pattern match or
3202       let/where-binding.  (The motivation here is that it should be
3203       easy for the reader to figure out what the "``..``" expands to.)
3204
3205    These rules restrict record wildcards to the situations in which the
3206    user could have written the expanded version. For example ::
3207
3208        module M where
3209          data R = R { a,b,c :: Int }
3210        module X where
3211          import M( R(a,c) )
3212          f b = R { .. }
3213
3214    The ``R{..}`` expands to ``R{M.a=a}``, omitting ``b`` since the
3215    record field is not in scope, and omitting ``c`` since the variable
3216    ``c`` is not in scope (apart from the binding of the record selector
3217    ``c``, of course).
3218
3219 -  Record wildcards cannot be used (a) in a record update construct, and
3220    (b) for data constructors that are not declared with record fields.
3221    For example: ::
3222
3223        f x = x { v=True, .. }   -- Illegal (a)
3224
3225        data T = MkT Int Bool
3226        g = MkT { .. }           -- Illegal (b)
3227        h (MkT { .. }) = True    -- Illegal (b)
3228
3229
3230 .. _record-field-selector-polymorphism:
3231
3232 Record field selector polymorphism
3233 ----------------------------------
3234
3235 The module :base-ref:`GHC.Records <GHC-Records.html>` defines the following: ::
3236
3237   class HasField (x :: k) r a | x r -> a where
3238     getField :: r -> a
3239
3240 A ``HasField x r a`` constraint represents the fact that ``x`` is a
3241 field of type ``a`` belonging to a record type ``r``.  The
3242 ``getField`` method gives the record selector function.
3243
3244 This allows definitions that are polymorphic over record types with a specified
3245 field.  For example, the following works with any record type that has a field
3246 ``name :: String``: ::
3247
3248   foo :: HasField "name" r String => r -> String
3249   foo r = reverse (getField @"name" r)
3250
3251 ``HasField`` is a magic built-in typeclass (similar to ``Coercible``, for
3252 example).  It is given special treatment by the constraint solver (see
3253 :ref:`solving-hasfield-constraints`).  Users may define their own instances of
3254 ``HasField`` also (see :ref:`virtual-record-fields`).
3255
3256 .. _solving-hasfield-constraints:
3257
3258 Solving HasField constraints
3259 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3260
3261 If the constraint solver encounters a constraint ``HasField x r a``
3262 where ``r`` is a concrete datatype with a field ``x`` in scope, it
3263 will automatically solve the constraint using the field selector as
3264 the dictionary, unifying ``a`` with the type of the field if
3265 necessary.  This happens irrespective of which extensions are enabled.
3266
3267 For example, if the following datatype is in scope ::
3268
3269   data Person = Person { name :: String }
3270
3271 the end result is rather like having an instance ::
3272
3273   instance HasField "name" Person String where
3274     getField = name
3275
3276 except that this instance is not actually generated anywhere, rather
3277 the constraint is solved directly by the constraint solver.
3278
3279 A field must be in scope for the corresponding ``HasField`` constraint
3280 to be solved.  This retains the existing representation hiding
3281 mechanism, whereby a module may choose not to export a field,
3282 preventing client modules from accessing or updating it directly.
3283
3284 Solving ``HasField`` constraints depends on the field selector functions that
3285 are generated for each datatype definition:
3286
3287 -  If a record field does not have a selector function because its type would allow
3288    an existential variable to escape, the corresponding ``HasField`` constraint
3289    will not be solved.  For example, ::
3290
3291      {-# LANGUAGE ExistentialQuantification #-}
3292      data Exists t = forall x . MkExists { unExists :: t x }
3293
3294    does not give rise to a selector ``unExists :: Exists t -> t x`` and we will not
3295    solve ``HasField "unExists" (Exists t) a`` automatically.
3296
3297 -  If a record field has a polymorphic type (and hence the selector function is
3298    higher-rank), the corresponding ``HasField`` constraint will not be solved,
3299    because doing so would violate the functional dependency on ``HasField`` and/or
3300    require impredicativity.  For example, ::
3301
3302      {-# LANGUAGE RankNTypes #-}
3303      data Higher = MkHigher { unHigher :: forall t . t -> t }
3304
3305    gives rise to a selector ``unHigher :: Higher -> (forall t . t -> t)`` but does
3306    not lead to solution of the constraint ``HasField "unHigher" Higher a``.
3307
3308 -  A record GADT may have a restricted type for a selector function, which may lead
3309    to additional unification when solving ``HasField`` constraints.  For example, ::
3310
3311      {-# LANGUAGE GADTs #-}
3312      data Gadt t where
3313        MkGadt :: { unGadt :: Maybe v } -> Gadt [v]
3314
3315    gives rise to a selector ``unGadt :: Gadt [v] -> Maybe v``, so the solver will reduce
3316    the constraint ``HasField "unGadt" (Gadt t) b`` by unifying ``t ~ [v]`` and
3317    ``b ~ Maybe v`` for some fresh metavariable ``v``, rather as if we had an instance ::
3318
3319      instance (t ~ [v], b ~ Maybe v) => HasField "unGadt" (Gadt t) b
3320
3321 -  If a record type has an old-fashioned datatype context, the ``HasField``
3322    constraint will be reduced to solving the constraints from the context.
3323    For example, ::
3324
3325      {-# LANGUAGE DatatypeContexts #-}
3326      data Eq a => Silly a = MkSilly { unSilly :: a }
3327
3328    gives rise to a selector ``unSilly :: Eq a => Silly a -> a``, so
3329    the solver will reduce the constraint ``HasField "unSilly" (Silly a) b`` to
3330    ``Eq a`` (and unify ``a`` with ``b``), rather as if we had an instance ::
3331
3332      instance (Eq a, a ~ b) => HasField "unSilly" (Silly a) b
3333
3334 .. _virtual-record-fields:
3335
3336 Virtual record fields
3337 ~~~~~~~~~~~~~~~~~~~~~
3338
3339 Users may define their own instances of ``HasField``, provided they do
3340 not conflict with the built-in constraint solving behaviour.  This
3341 allows "virtual" record fields to be defined for datatypes that do not
3342 otherwise have them.
3343
3344 For example, this instance would make the ``name`` field of ``Person``
3345 accessible using ``#fullname`` as well: ::
3346
3347   instance HasField "fullname" Person String where
3348     getField = name
3349
3350 More substantially, an anonymous records library could provide
3351 ``HasField`` instances for its anonymous records, and thus be
3352 compatible with the polymorphic record selectors introduced by this
3353 proposal.  For example, something like this makes it possible to use
3354 ``getField`` to access ``Record`` values with the appropriate
3355 string in the type-level list of fields: ::
3356
3357   data Record (xs :: [(k, Type)]) where
3358     Nil  :: Record '[]
3359     Cons :: Proxy x -> a -> Record xs -> Record ('(x, a) ': xs)
3360
3361   instance HasField x (Record ('(x, a) ': xs)) a where
3362     getField (Cons _ v _) = v
3363   instance HasField x (Record xs) a => HasField x (Record ('(y, b) ': xs)) a where
3364     getField (Cons _ _ r) = getField @x r
3365
3366   r :: Record '[ '("name", String) ]
3367   r = Cons Proxy "R" Nil)
3368
3369   x = getField @"name" r
3370
3371 Since representations such as this can support field labels with kinds other
3372 than ``Symbol``, the ``HasField`` class is poly-kinded (even though the built-in
3373 constraint solving works only at kind ``Symbol``).  In particular, this allows
3374 users to declare scoped field labels such as in the following example: ::
3375
3376   data PersonFields = Name
3377
3378   s :: Record '[ '(Name, String) ]
3379   s = Cons Proxy "S" Nil
3380
3381   y = getField @Name s
3382
3383 In order to avoid conflicting with the built-in constraint solving,
3384 the following user-defined ``HasField`` instances are prohibited (in
3385 addition to the usual rules, such as the prohibition on type
3386 families appearing in instance heads):
3387
3388 -  ``HasField _ r _`` where ``r`` is a variable;
3389
3390 -  ``HasField _ (T ...) _`` if ``T`` is a data family (because it
3391    might have fields introduced later, using data instance declarations);
3392
3393 -  ``HasField x (T ...) _`` if ``x`` is a variable and ``T`` has any
3394    fields at all (but this instance is permitted if ``T`` has no fields);
3395
3396 -  ``HasField "foo" (T ...) _`` if ``T`` has a field ``foo`` (but this
3397    instance is permitted if it does not).
3398
3399 If a field has a higher-rank or existential type, the corresponding ``HasField``
3400 constraint will not be solved automatically (as described above), but in the
3401 interests of simplicity we do not permit users to define their own instances
3402 either.  If a field is not in scope, the corresponding instance is still
3403 prohibited, to avoid conflicts in downstream modules.
3404
3405
3406 .. _deriving:
3407
3408 Extensions to the "deriving" mechanism
3409 ======================================
3410
3411 .. _deriving-inferred:
3412
3413 Inferred context for deriving clauses
3414 -------------------------------------
3415
3416 The Haskell Report is vague about exactly when a ``deriving`` clause is
3417 legal. For example: ::
3418
3419       data T0 f a = MkT0 a         deriving( Eq )
3420       data T1 f a = MkT1 (f a)     deriving( Eq )
3421       data T2 f a = MkT2 (f (f a)) deriving( Eq )
3422
3423 The natural generated ``Eq`` code would result in these instance
3424 declarations: ::
3425
3426       instance Eq a         => Eq (T0 f a) where ...
3427       instance Eq (f a)     => Eq (T1 f a) where ...
3428       instance Eq (f (f a)) => Eq (T2 f a) where ...
3429
3430 The first of these is obviously fine. The second is still fine, although
3431 less obviously. The third is not Haskell 98, and risks losing
3432 termination of instances.
3433
3434 GHC takes a conservative position: it accepts the first two, but not the
3435 third. The rule is this: each constraint in the inferred instance
3436 context must consist only of type variables, with no repetitions.
3437
3438 This rule is applied regardless of flags. If you want a more exotic
3439 context, you can write it yourself, using the `standalone deriving
3440 mechanism <#stand-alone-deriving>`__.
3441
3442 .. _stand-alone-deriving:
3443
3444 Stand-alone deriving declarations
3445 ---------------------------------
3446
3447 .. ghc-flag:: -XStandaloneDeriving
3448
3449     Allow the use of stand-alone ``deriving`` declarations.
3450
3451 GHC allows stand-alone ``deriving`` declarations, enabled by
3452 :ghc-flag:`-XStandaloneDeriving`: ::
3453
3454       data Foo a = Bar a | Baz String
3455
3456       deriving instance Eq a => Eq (Foo a)
3457
3458 The syntax is identical to that of an ordinary instance declaration
3459 apart from (a) the keyword ``deriving``, and (b) the absence of the
3460 ``where`` part.
3461
3462 However, standalone deriving differs from a ``deriving`` clause in a
3463 number of important ways:
3464
3465 -  The standalone deriving declaration does not need to be in the same
3466    module as the data type declaration. (But be aware of the dangers of
3467    orphan instances (:ref:`orphan-modules`).
3468
3469 -  You must supply an explicit context (in the example the context is
3470    ``(Eq a)``), exactly as you would in an ordinary instance
3471    declaration. (In contrast, in a ``deriving`` clause attached to a
3472    data type declaration, the context is inferred.)
3473
3474 -  Unlike a ``deriving`` declaration attached to a ``data`` declaration,
3475    the instance can be more specific than the data type (assuming you
3476    also use :ghc-flag:`-XFlexibleInstances`, :ref:`instance-rules`). Consider
3477    for example ::
3478
3479          data Foo a = Bar a | Baz String
3480
3481          deriving instance Eq a => Eq (Foo [a])
3482          deriving instance Eq a => Eq (Foo (Maybe a))
3483
3484    This will generate a derived instance for ``(Foo [a])`` and
3485    ``(Foo (Maybe a))``, but other types such as ``(Foo (Int,Bool))``
3486    will not be an instance of ``Eq``.
3487
3488 -  Unlike a ``deriving`` declaration attached to a ``data`` declaration,
3489    GHC does not restrict the form of the data type. Instead, GHC simply
3490    generates the appropriate boilerplate code for the specified class,
3491    and typechecks it. If there is a type error, it is your problem. (GHC
3492    will show you the offending code if it has a type error.)
3493
3494    The merit of this is that you can derive instances for GADTs and
3495    other exotic data types, providing only that the boilerplate code
3496    does indeed typecheck. For example: ::
3497
3498          data T a where
3499             T1 :: T Int
3500             T2 :: T Bool
3501
3502          deriving instance Show (T a)
3503
3504    In this example, you cannot say ``... deriving( Show )`` on the data
3505    type declaration for ``T``, because ``T`` is a GADT, but you *can*
3506    generate the instance declaration using stand-alone deriving.
3507
3508    The down-side is that, if the boilerplate code fails to typecheck,
3509    you will get an error message about that code, which you did not
3510    write. Whereas, with a ``deriving`` clause the side-conditions are
3511    necessarily more conservative, but any error message may be more
3512    comprehensible.
3513
3514 -  Under most circumstances, you cannot use standalone deriving to create an
3515    instance for a data type whose constructors are not all in scope. This is
3516    because the derived instance would generate code that uses the constructors
3517    behind the scenes, which would break abstraction.
3518
3519    The one exception to this rule is :ghc-flag:`-XDeriveAnyClass`, since
3520    deriving an instance via :ghc-flag:`-XDeriveAnyClass` simply generates
3521    an empty instance declaration, which does not require the use of any
3522    constructors. See the `deriving any class <#derive-any-class>`__ section
3523    for more details.
3524
3525 In other ways, however, a standalone deriving obeys the same rules as
3526 ordinary deriving:
3527
3528 -  A ``deriving instance`` declaration must obey the same rules
3529    concerning form and termination as ordinary instance declarations,
3530    controlled by the same flags; see :ref:`instance-decls`.
3531
3532 -  The stand-alone syntax is generalised for newtypes in exactly the
3533    same way that ordinary ``deriving`` clauses are generalised
3534    (:ref:`newtype-deriving`). For example: ::
3535
3536          newtype Foo a = MkFoo (State Int a)
3537
3538          deriving instance MonadState Int Foo
3539
3540    GHC always treats the *last* parameter of the instance (``Foo`` in
3541    this example) as the type whose instance is being derived.
3542
3543 .. _deriving-extra:
3544
3545 Deriving instances of extra classes (``Data``, etc.)
3546 ----------------------------------------------------
3547
3548 .. ghc-flag:: -XDeriveGeneric
3549
3550     :since: 7.2
3551
3552     Allow automatic deriving of instances for the ``Generic`` typeclass.
3553
3554 .. ghc-flag:: -XDeriveFunctor
3555
3556     :since: 6.12
3557
3558     Allow automatic deriving of instances for the ``Functor`` typeclass.
3559
3560 .. ghc-flag:: -XDeriveFoldable
3561
3562     :since: 6.12
3563
3564     Allow automatic deriving of instances for the ``Foldable`` typeclass.
3565
3566 .. ghc-flag:: -XDeriveTraversable
3567
3568     :since: 6.12
3569
3570     :implies: :ghc-flag:`-XDeriveFoldable`, :ghc-flag:`-XDeriveFunctor`
3571
3572     Allow automatic deriving of instances for the ``Traversable`` typeclass.
3573
3574 Haskell 98 allows the programmer to add "``deriving( Eq, Ord )``" to a
3575 data type declaration, to generate a standard instance declaration for
3576 classes specified in the ``deriving`` clause. In Haskell 98, the only
3577 classes that may appear in the ``deriving`` clause are the standard
3578 classes ``Eq``, ``Ord``, ``Enum``, ``Ix``, ``Bounded``, ``Read``, and
3579 ``Show``.
3580
3581 GHC extends this list with several more classes that may be
3582 automatically derived:
3583
3584 -  With :ghc-flag:`-XDeriveGeneric`, you can derive instances of the classes
3585    ``Generic`` and ``Generic1``, defined in ``GHC.Generics``. You can
3586    use these to define generic functions, as described in
3587    :ref:`generic-programming`.
3588
3589 -  With :ghc-flag:`-XDeriveFunctor`, you can derive instances of the class
3590    ``Functor``, defined in ``GHC.Base``. See :ref:`deriving-functor`.
3591
3592 -  With :ghc-flag:`-XDeriveDataTypeable`, you can derive instances of the class
3593    ``Data``, defined in ``Data.Data``. See :ref:`deriving-typeable` for
3594    deriving ``Typeable``.
3595
3596 -  With :ghc-flag:`-XDeriveFoldable`, you can derive instances of the class
3597    ``Foldable``, defined in ``Data.Foldable``. See
3598    :ref:`deriving-foldable`.
3599
3600 -  With :ghc-flag:`-XDeriveTraversable`, you can derive instances of the class
3601    ``Traversable``, defined in ``Data.Traversable``. Since the
3602    ``Traversable`` instance dictates the instances of ``Functor`` and
3603    ``Foldable``, you'll probably want to derive them too, so
3604    :ghc-flag:`-XDeriveTraversable` implies :ghc-flag:`-XDeriveFunctor` and
3605    :ghc-flag:`-XDeriveFoldable`. See :ref:`deriving-traversable`.
3606
3607 -  With :ghc-flag:`-XDeriveLift`, you can derive instances of the class ``Lift``,
3608    defined in the ``Language.Haskell.TH.Syntax`` module of the
3609    ``template-haskell`` package. See :ref:`deriving-lift`.
3610
3611 You can also use a standalone deriving declaration instead (see
3612 :ref:`stand-alone-deriving`).
3613
3614 In each case the appropriate class must be in scope before it can be
3615 mentioned in the ``deriving`` clause.
3616
3617 .. _deriving-functor:
3618
3619 Deriving ``Functor`` instances
3620 ------------------------------
3621
3622 With :ghc-flag:`-XDeriveFunctor`, one can derive ``Functor`` instances for data types
3623 of kind ``* -> *``. For example, this declaration::
3624
3625     data Example a = Ex a Char (Example a) (Example Char)
3626       deriving Functor
3627
3628 would generate the following instance: ::
3629
3630     instance Functor Example where
3631       fmap f (Ex a1 a2 a3 a4) = Ex (f a1) a2 (fmap f a3) a4
3632
3633 The basic algorithm for :ghc-flag:`-XDeriveFunctor` walks the arguments of each
3634 constructor of a data type, applying a mapping function depending on the type
3635 of each argument. If a plain type variable is found that is syntactically
3636 equivalent to the last type parameter of the data type (``a`` in the above
3637 example), then we apply the function ``f`` directly to it. If a type is
3638 encountered that is not syntactically equivalent to the last type parameter
3639 *but does mention* the last type parameter somewhere in it, then a recursive
3640 call to ``fmap`` is made. If a type is found which doesn't mention the last
3641 type parameter at all, then it is left alone.
3642
3643 The second of those cases, in which a type is unequal to the type parameter but
3644 does contain the type parameter, can be surprisingly tricky. For example, the
3645 following example compiles::
3646
3647     newtype Right a = Right (Either Int a) deriving Functor
3648
3649 Modifying the code slightly, however, produces code which will not compile::
3650
3651     newtype Wrong a = Wrong (Either a Int) deriving Functor
3652
3653 The difference involves the placement of the last type parameter, ``a``. In the
3654 ``Right`` case, ``a`` occurs within the type ``Either Int a``, and moreover, it
3655 appears as the last type argument of ``Either``. In the ``Wrong`` case,
3656 however, ``a`` is not the last type argument to ``Either``; rather, ``Int`` is.
3657
3658 This distinction is important because of the way :ghc-flag:`-XDeriveFunctor` works. The
3659 derived ``Functor Right`` instance would be::
3660
3661     instance Functor Right where
3662       fmap f (Right a) = Right (fmap f a)
3663
3664 Given a value of type ``Right a``, GHC must produce a value of type
3665 ``Right b``. Since the argument to the ``Right`` constructor has type
3666 ``Either Int a``, the code recursively calls ``fmap`` on it to produce a value
3667 of type ``Either Int b``, which is used in turn to construct a final value of
3668 type ``Right b``.
3669
3670 The generated code for the ``Functor Wrong`` instance would look exactly the
3671 same, except with ``Wrong`` replacing every occurrence of ``Right``. The
3672 problem is now that ``fmap`` is being applied recursively to a value of type
3673 ``Either a Int``. This cannot possibly produce a value of type
3674 ``Either b Int``, as ``fmap`` can only change the last type parameter! This
3675 causes the generated code to be ill-typed.
3676
3677 As a general rule, if a data type has a derived ``Functor`` instance and its
3678 last type parameter occurs on the right-hand side of the data declaration, then
3679 either it must (1) occur bare (e.g., ``newtype Id a = a``), or (2) occur as the
3680 last argument of a type constructor (as in ``Right`` above).
3681
3682 There are two exceptions to this rule:
3683
3684 #. Tuple types. When a non-unit tuple is used on the right-hand side of a data
3685    declaration, :ghc-flag:`-XDeriveFunctor` treats it as a product of distinct types.
3686    In other words, the following code::
3687
3688        newtype Triple a = Triple (a, Int, [a]) deriving Functor
3689
3690    Would result in a generated ``Functor`` instance like so::
3691
3692        instance Functor Triple where
3693          fmap f (Triple a) =
3694            Triple (case a of
3695                         (a1, a2, a3) -> (f a1, a2, fmap f a3))
3696
3697    That is, :ghc-flag:`-XDeriveFunctor` pattern-matches its way into tuples and maps
3698    over each type that constitutes the tuple. The generated code is
3699    reminiscient of what would be generated from
3700    ``data Triple a = Triple a Int [a]``, except with extra machinery to handle
3701    the tuple.
3702
3703 #. Function types. The last type parameter can appear anywhere in a function
3704    type as long as it occurs in a *covariant* position. To illustrate what this
3705    means, consider the following three examples::
3706
3707        newtype CovFun1 a = CovFun1 (Int -> a) deriving Functor
3708        newtype CovFun2 a = CovFun2 ((a -> Int) -> a) deriving Functor
3709        newtype CovFun3 a = CovFun3 (((Int -> a) -> Int) -> a) deriving Functor
3710
3711    All three of these examples would compile without issue. On the other hand::
3712
3713        newtype ContraFun1 a = ContraFun1 (a -> Int) deriving Functor
3714        newtype ContraFun2 a = ContraFun2 ((Int -> a) -> Int) deriving Functor
3715        newtype ContraFun3 a = ContraFun3 (((a -> Int) -> a) -> Int) deriving Functor
3716
3717    While these examples look similar, none of them would successfully compile.
3718    This is because all occurrences of the last type parameter ``a`` occur in *contravariant* positions, not covariant ones.
3719
3720    Intuitively, a covariant type is *produced*, and a contravariant type is
3721    *consumed*. Most types in Haskell are covariant, but the function type is
3722    special in that the lefthand side of a function arrow reverses variance. If
3723    a function type ``a -> b`` appears in a covariant position (e.g.,
3724    ``CovFun1`` above), then ``a`` is in a contravariant position and ``b`` is
3725    in a covariant position. Similarly, if ``a -> b`` appears in a contravariant
3726    position (e.g., ``CovFun2`` above), then ``a`` is in ``a`` covariant
3727    position and ``b`` is in a contravariant position.
3728
3729    To see why a data type with a contravariant occurrence of its last type
3730    parameter cannot have a derived ``Functor`` instance, let's suppose that a
3731    ``Functor ContraFun1`` instance exists. The implementation would look
3732    something like this::
3733
3734        instance Functor ContraFun1 where
3735          fmap f (ContraFun g) = ContraFun (\x -> _)
3736
3737    We have ``f :: a -> b``, ``g :: a -> Int``, and ``x :: b``. Using these, we
3738    must somehow fill in the hole (denoted with an underscore) with a value of
3739    type ``Int``. What are our options?
3740
3741    We could try applying ``g`` to ``x``. This won't work though, as ``g``
3742    expects an argument of type ``a``, and ``x :: b``. Even worse, we can't turn
3743    ``x`` into something of type ``a``, since ``f`` also needs an argument of
3744    type ``a``! In short, there's no good way to make this work.
3745
3746    On the other hand, a derived ``Functor`` instances for the ``CovFun``\ s are
3747    within the realm of possibility::
3748
3749        instance Functor CovFun1 where
3750          fmap f (CovFun1 g) = CovFun1 (\x -> f (g x))
3751
3752        instance Functor CovFun2 where
3753          fmap f (CovFun2 g) = CovFun2 (\h -> f (g (\x -> h (f x))))
3754
3755        instance Functor CovFun3 where
3756          fmap f (CovFun3 g) = CovFun3 (\h -> f (g (\k -> h (\x -> f (k x)))))
3757
3758 There are some other scenarios in which a derived ``Functor`` instance will
3759 fail to compile:
3760
3761 #. A data type has no type parameters (e.g., ``data Nothing = Nothing``).
3762
3763 #. A data type's last type variable is used in a :ghc-flag:`-XDatatypeContexts`
3764    constraint (e.g., ``data Ord a => O a = O a``).
3765
3766 #. A data type's last type variable is used in an
3767    :ghc-flag:`-XExistentialQuantification` constraint, or is refined in a GADT. For
3768    example, ::
3769
3770        data T a b where
3771            T4 :: Ord b => b -> T a b
3772            T5 :: b -> T b b
3773            T6 :: T a (b,b)
3774
3775        deriving instance Functor (T a)
3776
3777    would not compile successfully due to the way in which ``b`` is constrained.
3778
3779 .. _deriving-foldable:
3780
3781 Deriving ``Foldable`` instances
3782 -------------------------------
3783
3784 With :ghc-flag:`-XDeriveFoldable`, one can derive ``Foldable`` instances for data types
3785 of kind ``* -> *``. For example, this declaration::
3786
3787     data Example a = Ex a Char (Example a) (Example Char)
3788       deriving Foldable
3789
3790 would generate the following instance::
3791
3792     instance Foldable Example where
3793       foldr f z (Ex a1 a2 a3 a4) = f a1 (foldr f z a3)
3794       foldMap f (Ex a1 a2 a3 a4) = mappend (f a1) (foldMap f a3)
3795
3796 The algorithm for :ghc-flag:`-XDeriveFoldable` is adapted from the :ghc-flag:`-XDeriveFunctor`
3797 algorithm, but it generates definitions for ``foldMap`` and ``foldr`` instead
3798 of ``fmap``. In addition, :ghc-flag:`-XDeriveFoldable` filters out all
3799 constructor arguments on the RHS expression whose types do not mention the last
3800 type parameter, since those arguments do not need to be folded over.
3801
3802 Here are the differences between the generated code in each extension:
3803
3804 #. When a bare type variable ``a`` is encountered, :ghc-flag:`-XDeriveFunctor` would
3805    generate ``f a`` for an ``fmap`` definition. :ghc-flag:`-XDeriveFoldable` would
3806    generate ``f a z`` for ``foldr``, and ``f a`` for ``foldMap``.
3807
3808 #. When a type that is not syntactically equivalent to ``a``, but which does
3809    contain ``a``, is encountered, :ghc-flag:`-XDeriveFunctor` recursively calls
3810    ``fmap`` on it. Similarly, :ghc-flag:`-XDeriveFoldable` would recursively call
3811    ``foldr`` and ``foldMap``.
3812
3813 #. :ghc-flag:`-XDeriveFunctor` puts everything back together again at the end by
3814    invoking the constructor. :ghc-flag:`-XDeriveFoldable`, however, builds up a value
3815    of some type. For ``foldr``, this is accomplished by chaining applications
3816    of ``f`` and recursive ``foldr`` calls on the state value ``z``. For
3817    ``foldMap``, this happens by combining all values with ``mappend``.
3818
3819 There are some other differences regarding what data types can have derived
3820 ``Foldable`` instances:
3821
3822 #. Data types containing function types on the right-hand side cannot have
3823    derived ``Foldable`` instances.
3824
3825 #. ``Foldable`` instances can be derived for data types in which the last type
3826    parameter is existentially constrained or refined in a GADT. For example,
3827    this data type::
3828
3829        data E a where
3830            E1 :: (a ~ Int) => a   -> E a
3831            E2 ::              Int -> E Int
3832            E3 :: (a ~ Int) => a   -> E Int
3833            E4 :: (a ~ Int) => Int -> E a
3834
3835        deriving instance Foldable E
3836
3837    would have the following generated ``Foldable`` instance::
3838
3839        instance Foldable E where
3840            foldr f z (E1 e) = f e z
3841            foldr f z (E2 e) = z
3842            foldr f z (E3 e) = z
3843            foldr f z (E4 e) = z
3844
3845            foldMap f (E1 e) = f e
3846            foldMap f (E2 e) = mempty
3847            foldMap f (E3 e) = mempty
3848            foldMap f (E4 e) = mempty
3849
3850    Notice how every constructor of ``E`` utilizes some sort of existential
3851    quantification, but only the argument of ``E1`` is actually "folded over".
3852    This is because we make a deliberate choice to only fold over universally
3853    polymorphic types that are syntactically equivalent to the last type
3854    parameter. In particular:
3855
3856   -  We don't fold over the arguments of ``E1`` or ``E4`` beacause even though
3857      ``(a ~ Int)``, ``Int`` is not syntactically equivalent to ``a``.
3858
3859   -  We don't fold over the argument of ``E3`` because ``a`` is not universally
3860      polymorphic. The ``a`` in ``E3`` is (implicitly) existentially quantified,
3861      so it is not the same as the last type parameter of ``E``.
3862
3863 .. _deriving-traversable:
3864
3865 Deriving ``Traversable`` instances
3866 ----------------------------------
3867
3868 With :ghc-flag:`-XDeriveTraversable`, one can derive ``Traversable`` instances for data
3869 types of kind ``* -> *``. For example, this declaration::
3870
3871     data Example a = Ex a Char (Example a) (Example Char)
3872       deriving (Functor, Foldable, Traversable)
3873
3874 would generate the following ``Traversable`` instance::
3875
3876     instance Traversable Example where
3877       traverse f (Ex a1 a2 a3 a4)
3878         = fmap (\b1 b3 -> Ex b1 a2 b3 a4) (f a1) <*> traverse f a3
3879
3880 The algorithm for :ghc-flag:`-XDeriveTraversable` is adapted from the
3881 :ghc-flag:`-XDeriveFunctor` algorithm, but it generates a definition for ``traverse``
3882 instead of ``fmap``. In addition, :ghc-flag:`-XDeriveTraversable` filters out
3883 all constructor arguments on the RHS expression whose types do not mention the
3884 last type parameter, since those arguments do not produce any effects in a
3885 traversal. Here are the differences between the generated code in each
3886 extension:
3887
3888 #. When a bare type variable ``a`` is encountered, both :ghc-flag:`-XDeriveFunctor` and
3889    :ghc-flag:`-XDeriveTraversable` would generate ``f a`` for an ``fmap`` and
3890    ``traverse`` definition, respectively.
3891
3892 #. When a type that is not syntactically equivalent to ``a``, but which does
3893    contain ``a``, is encountered, :ghc-flag:`-XDeriveFunctor` recursively calls
3894    ``fmap`` on it. Similarly, :ghc-flag:`-XDeriveTraversable` would recursively call
3895    ``traverse``.
3896
3897 #. :ghc-flag:`-XDeriveFunctor` puts everything back together again at the end by
3898    invoking the constructor. :ghc-flag:`-XDeriveTraversable` does something similar,
3899    but it works in an ``Applicative`` context by chaining everything together
3900    with ``(<*>)``.
3901
3902 Unlike :ghc-flag:`-XDeriveFunctor`, :ghc-flag:`-XDeriveTraversable` cannot be used on data
3903 types containing a function type on the right-hand side.
3904
3905 For a full specification of the algorithms used in :ghc-flag:`-XDeriveFunctor`,
3906 :ghc-flag:`-XDeriveFoldable`, and :ghc-flag:`-XDeriveTraversable`, see
3907 :ghc-wiki:`this wiki page <Commentary/Compiler/DeriveFunctor>`.
3908
3909 .. _deriving-typeable:
3910
3911 Deriving ``Typeable`` instances
3912 -------------------------------
3913
3914 .. ghc-flag:: -XDeriveDataTypeable
3915
3916     Enable automatic deriving of instances for the ``Typeable`` typeclass
3917
3918 The class ``Typeable`` is very special:
3919
3920 -  ``Typeable`` is kind-polymorphic (see :ref:`kind-polymorphism`).
3921
3922 -  GHC has a custom solver for discharging constraints that involve
3923    class ``Typeable``, and handwritten instances are forbidden. This
3924    ensures that the programmer cannot subvert the type system by writing
3925    bogus instances.
3926
3927 -  Derived instances of ``Typeable`` are ignored, and may be reported as
3928    an error in a later version of the compiler.
3929
3930 -  The rules for solving \`Typeable\` constraints are as follows:
3931
3932    -  A concrete type constructor applied to some types. ::
3933
3934           instance (Typeable t1, .., Typeable t_n) =>
3935             Typeable (T t1 .. t_n)
3936
3937       This rule works for any concrete type constructor, including type
3938       constructors with polymorphic kinds. The only restriction is that
3939       if the type constructor has a polymorphic kind, then it has to be
3940       applied to all of its kinds parameters, and these kinds need to be
3941       concrete (i.e., they cannot mention kind variables).
3942
3943    -  ::
3944
3945           A type variable applied to some types.
3946           instance (Typeable f, Typeable t1, .., Typeable t_n) =>
3947             Typeable (f t1 .. t_n)
3948
3949    -  ::
3950
3951           A concrete type literal.
3952           instance Typeable 0       -- Type natural literals
3953           instance Typeable "Hello" -- Type-level symbols
3954
3955 .. _deriving-lift:
3956
3957 Deriving ``Lift`` instances
3958 ---------------------------
3959
3960 .. ghc-flag:: -XDeriveLift
3961
3962     :since: 8.0.1
3963
3964     Enable automatic deriving of instances for the ``Lift`` typeclass for
3965     Template Haskell.
3966
3967 The class ``Lift``, unlike other derivable classes, lives in
3968 ``template-haskell`` instead of ``base``. Having a data type be an instance of
3969 ``Lift`` permits its values to be promoted to Template Haskell expressions (of
3970 type ``ExpQ``), which can then be spliced into Haskell source code.
3971
3972 Here is an example of how one can derive ``Lift``:
3973
3974 ::
3975
3976     {-# LANGUAGE DeriveLift #-}
3977     module Bar where
3978
3979     import Language.Haskell.TH.Syntax
3980
3981     data Foo a = Foo a | a :^: a deriving Lift
3982
3983     {-
3984     instance (Lift a) => Lift (Foo a) where
3985         lift (Foo a)
3986         = appE
3987             (conE
3988                 (mkNameG_d "package-name" "Bar" "Foo"))
3989             (lift a)
3990         lift (u :^: v)
3991         = infixApp
3992             (lift u)
3993             (conE
3994                 (mkNameG_d "package-name" "Bar" ":^:"))
3995             (lift v)
3996     -}
3997
3998     -----
3999     {-# LANGUAGE TemplateHaskell #-}
4000     module Baz where
4001
4002     import Bar
4003     import Language.Haskell.TH.Lift
4004
4005     foo :: Foo String
4006     foo = $(lift $ Foo "foo")
4007
4008     fooExp :: Lift a => Foo a -> Q Exp
4009     fooExp f = [| f |]
4010
4011 :ghc-flag:`-XDeriveLift` also works for certain unboxed types (``Addr#``, ``Char#``,
4012 ``Double#``, ``Float#``, ``Int#``, and ``Word#``):
4013
4014 ::
4015
4016     {-# LANGUAGE DeriveLift, MagicHash #-}
4017     module Unboxed where
4018
4019     import GHC.Exts
4020     import Language.Haskell.TH.Syntax
4021
4022     data IntHash = IntHash Int# deriving Lift
4023
4024     {-
4025     instance Lift IntHash where
4026         lift (IntHash i)
4027         = appE
4028             (conE
4029                 (mkNameG_d "package-name" "Unboxed" "IntHash"))
4030             (litE
4031                 (intPrimL (toInteger (I# i))))
4032     -}
4033
4034
4035 .. _newtype-deriving:
4036
4037 Generalised derived instances for newtypes
4038 ------------------------------------------
4039
4040 .. ghc-flag:: -XGeneralisedNewtypeDeriving
4041               -XGeneralizedNewtypeDeriving
4042
4043     Enable GHC's cunning generalised deriving mechanism for ``newtype``\s
4044
4045 When you define an abstract type using ``newtype``, you may want the new
4046 type to inherit some instances from its representation. In Haskell 98,
4047 you can inherit instances of ``Eq``, ``Ord``, ``Enum`` and ``Bounded``
4048 by deriving them, but for any other classes you have to write an
4049 explicit instance declaration. For example, if you define ::
4050
4051       newtype Dollars = Dollars Int
4052
4053 and you want to use arithmetic on ``Dollars``, you have to explicitly
4054 define an instance of ``Num``: ::
4055
4056       instance Num Dollars where
4057         Dollars a + Dollars b = Dollars (a+b)
4058         ...
4059
4060 All the instance does is apply and remove the ``newtype`` constructor.
4061 It is particularly galling that, since the constructor doesn't appear at
4062 run-time, this instance declaration defines a dictionary which is
4063 *wholly equivalent* to the ``Int`` dictionary, only slower!
4064
4065 .. _generalized-newtype-deriving:
4066
4067 Generalising the deriving clause
4068 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
4069
4070 GHC now permits such instances to be derived instead, using the flag
4071 :ghc-flag:`-XGeneralizedNewtypeDeriving`, so one can write ::
4072
4073       newtype Dollars = Dollars { getDollars :: Int } deriving (Eq,Show,Num)
4074
4075 and the implementation uses the *same* ``Num`` dictionary for
4076 ``Dollars`` as for ``Int``. In other words, GHC will generate something that
4077 resembles the following code ::
4078
4079       instance Num Int => Num Dollars
4080
4081 and then attempt to simplify the ``Num Int`` context as much as possible.
4082 GHC knows that there is a ``Num Int`` instance in scope, so it is able to
4083 discharge the ``Num Int`` constraint, leaving the code that GHC actually
4084 generates ::
4085
4086       instance Num Dollars
4087
4088 One can think of this instance being implemented with the same code as the
4089 ``Num Int`` instance, but with ``Dollars`` and ``getDollars`` added wherever
4090 necessary in order to make it typecheck. (In practice, GHC uses a somewhat
4091 different approach to code generation. See the :ref:`precise-gnd-specification`
4092 section below for more details.)
4093
4094 We can also derive instances of constructor classes in a similar way.
4095 For example, suppose we have implemented state and failure monad
4096 transformers, such that ::
4097
4098       instance Monad m => Monad (State s m)
4099       instance Monad m => Monad (Failure m)
4100
4101 In Haskell 98, we can define a parsing monad by ::
4102
4103       type Parser tok m a = State [tok] (Failure m) a
4104
4105 which is automatically a monad thanks to the instance declarations
4106 above. With the extension, we can make the parser type abstract, without
4107 needing to write an instance of class ``Monad``, via ::
4108
4109       newtype Parser tok m a = Parser (State [tok] (Failure m) a)
4110                              deriving Monad
4111
4112 In this case the derived instance declaration is of the form ::
4113
4114       instance Monad (State [tok] (Failure m)) => Monad (Parser tok m)
4115
4116 Notice that, since ``Monad`` is a constructor class, the instance is a
4117 *partial application* of the new type, not the entire left hand side. We
4118 can imagine that the type declaration is "eta-converted" to generate the
4119 context of the instance declaration.
4120
4121 We can even derive instances of multi-parameter classes, provided the
4122 newtype is the last class parameter. In this case, a "partial