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