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