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