Implement BlockArguments (#10843)
[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 .. _block-arguments:
2102
2103 More liberal syntax for function arguments
2104 ------------------------------------------
2105
2106 .. extension:: BlockArguments
2107     :shortdesc: Allow ``do`` blocks and other constructs as function arguments.
2108
2109     :since: 8.6.1
2110
2111     Allow ``do`` expressions, lambda expressions, etc. to be directly used as
2112     a function argument.
2113
2114 In Haskell 2010, certain kinds of expressions can be used without parentheses
2115 as an argument to an operator, but not as an argument to a function.
2116 They include ``do``, lambda, ``if``, ``case``, and ``let``
2117 expressions. Some GHC extensions also define language constructs of this type:
2118 ``mdo`` (:ref:`recursive-do-notation`), ``\case`` (:ref:`lambda-case`), and
2119 ``proc`` (:ref:`arrow-notation`).
2120
2121 The :extension:`BlockArguments` extension allows these constructs to be directly
2122 used as a function argument. For example::
2123
2124     when (x > 0) do
2125       print x
2126       exitFailure
2127
2128 will be parsed as::
2129
2130     when (x > 0) (do
2131       print x
2132       exitFailure)
2133
2134 and
2135
2136 ::
2137
2138     withForeignPtr fptr \ptr -> c_memcpy buf ptr size
2139
2140 will be parsed as::
2141
2142     withForeignPtr fptr (\ptr -> c_memcpy buf ptr size)
2143
2144 Changes to the grammar
2145 ~~~~~~~~~~~~~~~~~~~~~~
2146
2147 The Haskell report `defines
2148 <https://www.haskell.org/onlinereport/haskell2010/haskellch3.html#x8-220003>`_
2149 the ``lexp`` nonterminal thus (``*`` indicates a rule of interest)::
2150
2151     lexp  →  \ apat1 … apatn -> exp            (lambda abstraction, n ≥ 1)  *
2152           |  let decls in exp                  (let expression)             *
2153           |  if exp [;] then exp [;] else exp  (conditional)                *
2154           |  case exp of { alts }              (case expression)            *
2155           |  do { stmts }                      (do expression)              *
2156           |  fexp
2157
2158     fexp  →  [fexp] aexp                       (function application)
2159
2160     aexp  →  qvar                              (variable)
2161           |  gcon                              (general constructor)
2162           |  literal
2163           |  ( exp )                           (parenthesized expression)
2164           |  qcon { fbind1 … fbindn }          (labeled construction)
2165           |  aexp { fbind1 … fbindn }          (labelled update)
2166           |  …
2167
2168 The :extension:`BlockArguments` extension moves these production rules under
2169 ``aexp``::
2170
2171     lexp  →  fexp
2172
2173     fexp  →  [fexp] aexp                       (function application)
2174
2175     aexp  →  qvar                              (variable)
2176           |  gcon                              (general constructor)
2177           |  literal
2178           |  ( exp )                           (parenthesized expression)
2179           |  qcon { fbind1 … fbindn }          (labeled construction)
2180           |  aexp { fbind1 … fbindn }          (labelled update)
2181           |  \ apat1 … apatn -> exp            (lambda abstraction, n ≥ 1)  *
2182           |  let decls in exp                  (let expression)             *
2183           |  if exp [;] then exp [;] else exp  (conditional)                *
2184           |  case exp of { alts }              (case expression)            *
2185           |  do { stmts }                      (do expression)              *
2186           |  …
2187
2188 Now the ``lexp`` nonterminal is redundant and can be dropped from the grammar.
2189
2190 Note that this change relies on an existing meta-rule to resolve ambiguities:
2191
2192     The grammar is ambiguous regarding the extent of lambda abstractions, let
2193     expressions, and conditionals. The ambiguity is resolved by the meta-rule
2194     that each of these constructs extends as far to the right as possible.
2195
2196 For example, ``f \a -> a b`` will be parsed as ``f (\a -> a b)``, not as ``f
2197 (\a -> a) b``.
2198
2199 .. _syntax-stolen:
2200
2201 Summary of stolen syntax
2202 ------------------------
2203
2204 Turning on an option that enables special syntax *might* cause working
2205 Haskell 98 code to fail to compile, perhaps because it uses a variable
2206 name which has become a reserved word. This section lists the syntax
2207 that is "stolen" by language extensions. We use notation and nonterminal
2208 names from the Haskell 98 lexical syntax (see the Haskell 98 Report). We
2209 only list syntax changes here that might affect existing working
2210 programs (i.e. "stolen" syntax). Many of these extensions will also
2211 enable new context-free syntax, but in all cases programs written to use
2212 the new syntax would not be compilable without the option enabled.
2213
2214 There are two classes of special syntax:
2215
2216 -  New reserved words and symbols: character sequences which are no
2217    longer available for use as identifiers in the program.
2218
2219 -  Other special syntax: sequences of characters that have a different
2220    meaning when this particular option is turned on.
2221
2222 The following syntax is stolen:
2223
2224 ``forall``
2225     .. index::
2226        single: forall
2227
2228     Stolen (in types) by: :extension:`ExplicitForAll`, and hence by
2229     :extension:`ScopedTypeVariables`, :extension:`LiberalTypeSynonyms`,
2230     :extension:`RankNTypes`, :extension:`ExistentialQuantification`
2231
2232 ``mdo``
2233     .. index::
2234        single: mdo
2235
2236     Stolen by: :extension:`RecursiveDo`
2237
2238 ``foreign``
2239     .. index::
2240        single: foreign
2241
2242     Stolen by: :extension:`ForeignFunctionInterface`
2243
2244 ``rec``, ``proc``, ``-<``, ``>-``, ``-<<``, ``>>-``, ``(|``, ``|)``
2245     .. index::
2246        single: proc
2247
2248     Stolen by: :extension:`Arrows`
2249
2250 ``?varid``
2251     .. index::
2252        single: implicit parameters
2253
2254     Stolen by: :extension:`ImplicitParams`
2255
2256 ``[|``, ``[e|``, ``[p|``, ``[d|``, ``[t|``, ``[||``, ``[e||``
2257     .. index::
2258        single: Quasi-quotes
2259
2260     Stolen by: :extension:`QuasiQuotes`. Moreover, this introduces an ambiguity
2261     with list comprehension syntax. See the
2262     :ref:`discussion on quasi-quoting <quasi-quotes-list-comprehension-ambiguity>`
2263     for details.
2264
2265 ``$(``, ``$$(``, ``$varid``, ``$$varid``
2266     .. index::
2267        single: Template Haskell
2268
2269     Stolen by: :extension:`TemplateHaskell`
2270
2271 ``[varid|``
2272     .. index::
2273        single: quasi-quotation
2274
2275     Stolen by: :extension:`QuasiQuotes`
2276
2277 ⟨varid⟩, ``#``\ ⟨char⟩, ``#``, ⟨string⟩, ``#``, ⟨integer⟩, ``#``, ⟨float⟩, ``#``, ⟨float⟩, ``##``
2278     Stolen by: :extension:`MagicHash`
2279
2280 ``(#``, ``#)``
2281     Stolen by: :extension:`UnboxedTuples`
2282
2283 ⟨varid⟩, ``!``, ⟨varid⟩
2284     Stolen by: :extension:`BangPatterns`
2285
2286 ``pattern``
2287     Stolen by: :extension:`PatternSynonyms`
2288
2289 .. _data-type-extensions:
2290
2291 Extensions to data types and type synonyms
2292 ==========================================
2293
2294 .. _nullary-types:
2295
2296 Data types with no constructors
2297 -------------------------------
2298
2299 .. extension:: EmptyDataDecls
2300     :shortdesc: Allow definition of empty ``data`` types.
2301
2302     :since: 6.8.1
2303
2304     Allow definition of empty ``data`` types.
2305
2306 With the :extension:`EmptyDataDecls` extension, GHC
2307 lets you declare a data type with no constructors. For example: ::
2308
2309       data S      -- S :: *
2310       data T a    -- T :: * -> *
2311
2312 Syntactically, the declaration lacks the "= constrs" part. The type can
2313 be parameterised over types of any kind, but if the kind is not ``*``
2314 then an explicit kind annotation must be used (see :ref:`kinding`).
2315
2316 Such data types have only one value, namely bottom. Nevertheless, they
2317 can be useful when defining "phantom types".
2318
2319 In conjunction with the :ghc-flag:`-XEmptyDataDeriving` extension, empty data
2320 declarations can also derive instances of standard type classes
2321 (see :ref:`empty-data-deriving`).
2322
2323 .. _datatype-contexts:
2324
2325 Data type contexts
2326 ------------------
2327
2328 .. extension:: DatatypeContexts
2329     :shortdesc: Allow contexts on ``data`` types.
2330
2331     :since: 7.0.1
2332
2333     Allow contexts on ``data`` types.
2334
2335 Haskell allows datatypes to be given contexts, e.g. ::
2336
2337     data Eq a => Set a = NilSet | ConsSet a (Set a)
2338
2339 give constructors with types: ::
2340
2341     NilSet :: Set a
2342     ConsSet :: Eq a => a -> Set a -> Set a
2343
2344 This is widely considered a misfeature, and is going to be removed from
2345 the language. In GHC, it is controlled by the deprecated extension
2346 ``DatatypeContexts``.
2347
2348 .. _infix-tycons:
2349
2350 Infix type constructors, classes, and type variables
2351 ----------------------------------------------------
2352
2353 GHC allows type constructors, classes, and type variables to be
2354 operators, and to be written infix, very much like expressions. More
2355 specifically:
2356
2357 -  A type constructor or class can be any non-reserved operator.
2358    Symbols used in types are always like capitalized identifiers; they
2359    are never variables. Note that this is different from the lexical
2360    syntax of data constructors, which are required to begin with a
2361    ``:``.
2362
2363 -  Data type and type-synonym declarations can be written infix,
2364    parenthesised if you want further arguments. E.g. ::
2365
2366          data a :*: b = Foo a b
2367          type a :+: b = Either a b
2368          class a :=: b where ...
2369
2370          data (a :**: b) x = Baz a b x
2371          type (a :++: b) y = Either (a,b) y
2372
2373 -  Types, and class constraints, can be written infix. For example ::
2374
2375          x :: Int :*: Bool
2376          f :: (a :=: b) => a -> b
2377
2378 -  Back-quotes work as for expressions, both for type constructors and
2379    type variables; e.g. ``Int `Either` Bool``, or ``Int `a` Bool``.
2380    Similarly, parentheses work the same; e.g. ``(:*:) Int Bool``.
2381
2382 -  Fixities may be declared for type constructors, or classes, just as
2383    for data constructors. However, one cannot distinguish between the
2384    two in a fixity declaration; a fixity declaration sets the fixity for
2385    a data constructor and the corresponding type constructor. For
2386    example: ::
2387
2388          infixl 7 T, :*:
2389
2390    sets the fixity for both type constructor ``T`` and data constructor
2391    ``T``, and similarly for ``:*:``. ``Int `a` Bool``.
2392
2393 -  Function arrow is ``infixr`` with fixity 0 (this might change; it's
2394    not clear what it should be).
2395
2396 .. _type-operators:
2397
2398 Type operators
2399 --------------
2400
2401 .. extension:: TypeOperators
2402     :shortdesc: Enable type operators.
2403         Implies :extension:`ExplicitNamespaces`.
2404
2405     :implies: :extension:`ExplicitNamespaces`
2406     :since: 6.8.1
2407
2408     Allow the use and definition of types with operator names.
2409
2410 In types, an operator symbol like ``(+)`` is normally treated as a type
2411 *variable*, just like ``a``. Thus in Haskell 98 you can say
2412
2413 ::
2414
2415     type T (+) = ((+), (+))
2416     -- Just like: type T a = (a,a)
2417
2418     f :: T Int -> Int
2419     f (x,y)= x
2420
2421 As you can see, using operators in this way is not very useful, and
2422 Haskell 98 does not even allow you to write them infix.
2423
2424 The language :extension:`TypeOperators` changes this behaviour:
2425
2426 -  Operator symbols become type *constructors* rather than type
2427    *variables*.
2428
2429 -  Operator symbols in types can be written infix, both in definitions
2430    and uses. For example: ::
2431
2432        data a + b = Plus a b
2433        type Foo = Int + Bool
2434
2435 -  There is now some potential ambiguity in import and export lists; for
2436    example if you write ``import M( (+) )`` do you mean the *function*
2437    ``(+)`` or the *type constructor* ``(+)``? The default is the former,
2438    but with :extension:`ExplicitNamespaces` (which is implied by
2439    :extension:`TypeOperators`) GHC allows you to specify the latter by
2440    preceding it with the keyword ``type``, thus: ::
2441
2442        import M( type (+) )
2443
2444    See :ref:`explicit-namespaces`.
2445
2446 -  The fixity of a type operator may be set using the usual fixity
2447    declarations but, as in :ref:`infix-tycons`, the function and type
2448    constructor share a single fixity.
2449
2450 .. _type-synonyms:
2451
2452 Liberalised type synonyms
2453 -------------------------
2454
2455 .. extension:: LiberalTypeSynonyms
2456     :shortdesc: Enable liberalised type synonyms.
2457
2458     :implies: :extension:`ExplicitForAll`
2459     :since: 6.8.1
2460
2461     Relax many of the Haskell 98 rules on type synonym definitions.
2462
2463 Type synonyms are like macros at the type level, but Haskell 98 imposes
2464 many rules on individual synonym declarations. With the
2465 :extension:`LiberalTypeSynonyms` extension, GHC does validity checking on types
2466 *only after expanding type synonyms*. That means that GHC can be very
2467 much more liberal about type synonyms than Haskell 98.
2468
2469 -  You can write a ``forall`` (including overloading) in a type synonym,
2470    thus: ::
2471
2472          type Discard a = forall b. Show b => a -> b -> (a, String)
2473
2474          f :: Discard a
2475          f x y = (x, show y)
2476
2477          g :: Discard Int -> (Int,String)    -- A rank-2 type
2478          g f = f 3 True
2479
2480 -  If you also use :extension:`UnboxedTuples`, you can write an unboxed tuple
2481    in a type synonym: ::
2482
2483          type Pr = (# Int, Int #)
2484
2485          h :: Int -> Pr
2486          h x = (# x, x #)
2487
2488 -  You can apply a type synonym to a forall type: ::
2489
2490          type Foo a = a -> a -> Bool
2491
2492          f :: Foo (forall b. b->b)
2493
2494    After expanding the synonym, ``f`` has the legal (in GHC) type: ::
2495
2496          f :: (forall b. b->b) -> (forall b. b->b) -> Bool
2497
2498 -  You can apply a type synonym to a partially applied type synonym: ::
2499
2500          type Generic i o = forall x. i x -> o x
2501          type Id x = x
2502
2503          foo :: Generic Id []
2504
2505    After expanding the synonym, ``foo`` has the legal (in GHC) type: ::
2506
2507          foo :: forall x. x -> [x]
2508
2509 GHC currently does kind checking before expanding synonyms (though even
2510 that could be changed).
2511
2512 After expanding type synonyms, GHC does validity checking on types,
2513 looking for the following malformedness which isn't detected simply by
2514 kind checking:
2515
2516 -  Type constructor applied to a type involving for-alls (if
2517    :extension:`ImpredicativeTypes` is off)
2518
2519 -  Partially-applied type synonym.
2520
2521 So, for example, this will be rejected: ::
2522
2523       type Pr = forall a. a
2524
2525       h :: [Pr]
2526       h = ...
2527
2528 because GHC does not allow type constructors applied to for-all types.
2529
2530 .. _existential-quantification:
2531
2532 Existentially quantified data constructors
2533 ------------------------------------------
2534
2535 .. extension:: ExistentialQuantification
2536     :shortdesc: Enable liberalised type synonyms.
2537
2538     :implies: :extension:`ExplicitForAll`
2539     :since: 6.8.1
2540
2541     Allow existentially quantified type variables in types.
2542
2543 The idea of using existential quantification in data type declarations
2544 was suggested by Perry, and implemented in Hope+ (Nigel Perry, *The
2545 Implementation of Practical Functional Programming Languages*, PhD
2546 Thesis, University of London, 1991). It was later formalised by Laufer
2547 and Odersky (*Polymorphic type inference and abstract data types*,
2548 TOPLAS, 16(5), pp. 1411-1430, 1994). It's been in Lennart Augustsson's
2549 ``hbc`` Haskell compiler for several years, and proved very useful.
2550 Here's the idea. Consider the declaration: ::
2551
2552       data Foo = forall a. MkFoo a (a -> Bool)
2553                | Nil
2554
2555 The data type ``Foo`` has two constructors with types: ::
2556
2557       MkFoo :: forall a. a -> (a -> Bool) -> Foo
2558       Nil   :: Foo
2559
2560 Notice that the type variable ``a`` in the type of ``MkFoo`` does not
2561 appear in the data type itself, which is plain ``Foo``. For example, the
2562 following expression is fine: ::
2563
2564       [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]
2565
2566 Here, ``(MkFoo 3 even)`` packages an integer with a function ``even``
2567 that maps an integer to ``Bool``; and ``MkFoo 'c'
2568 isUpper`` packages a character with a compatible function. These two
2569 things are each of type ``Foo`` and can be put in a list.
2570
2571 What can we do with a value of type ``Foo``? In particular, what
2572 happens when we pattern-match on ``MkFoo``? ::
2573
2574       f (MkFoo val fn) = ???
2575
2576 Since all we know about ``val`` and ``fn`` is that they are compatible,
2577 the only (useful) thing we can do with them is to apply ``fn`` to
2578 ``val`` to get a boolean. For example: ::
2579
2580       f :: Foo -> Bool
2581       f (MkFoo val fn) = fn val
2582
2583 What this allows us to do is to package heterogeneous values together
2584 with a bunch of functions that manipulate them, and then treat that
2585 collection of packages in a uniform manner. You can express quite a bit
2586 of object-oriented-like programming this way.
2587
2588 .. _existential:
2589
2590 Why existential?
2591 ~~~~~~~~~~~~~~~~
2592
2593 What has this to do with *existential* quantification? Simply that
2594 ``MkFoo`` has the (nearly) isomorphic type ::
2595
2596       MkFoo :: (exists a . (a, a -> Bool)) -> Foo
2597
2598 But Haskell programmers can safely think of the ordinary *universally*
2599 quantified type given above, thereby avoiding adding a new existential
2600 quantification construct.
2601
2602 .. _existential-with-context:
2603
2604 Existentials and type classes
2605 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2606
2607 An easy extension is to allow arbitrary contexts before the constructor.
2608 For example: ::
2609
2610     data Baz = forall a. Eq a => Baz1 a a
2611              | forall b. Show b => Baz2 b (b -> b)
2612
2613 The two constructors have the types you'd expect: ::
2614
2615     Baz1 :: forall a. Eq a => a -> a -> Baz
2616     Baz2 :: forall b. Show b => b -> (b -> b) -> Baz
2617
2618 But when pattern matching on ``Baz1`` the matched values can be compared
2619 for equality, and when pattern matching on ``Baz2`` the first matched
2620 value can be converted to a string (as well as applying the function to
2621 it). So this program is legal: ::
2622
2623       f :: Baz -> String
2624       f (Baz1 p q) | p == q    = "Yes"
2625                    | otherwise = "No"
2626       f (Baz2 v fn)            = show (fn v)
2627
2628 Operationally, in a dictionary-passing implementation, the constructors
2629 ``Baz1`` and ``Baz2`` must store the dictionaries for ``Eq`` and
2630 ``Show`` respectively, and extract it on pattern matching.
2631
2632 .. _existential-records:
2633
2634 Record Constructors
2635 ~~~~~~~~~~~~~~~~~~~
2636
2637 GHC allows existentials to be used with records syntax as well. For
2638 example: ::
2639
2640     data Counter a = forall self. NewCounter
2641         { _this    :: self
2642         , _inc     :: self -> self
2643         , _display :: self -> IO ()
2644         , tag      :: a
2645         }
2646
2647 Here ``tag`` is a public field, with a well-typed selector function
2648 ``tag :: Counter a -> a``. The ``self`` type is hidden from the outside;
2649 any attempt to apply ``_this``, ``_inc`` or ``_display`` as functions
2650 will raise a compile-time error. In other words, *GHC defines a record
2651 selector function only for fields whose type does not mention the
2652 existentially-quantified variables*. (This example used an underscore in
2653 the fields for which record selectors will not be defined, but that is
2654 only programming style; GHC ignores them.)
2655
2656 To make use of these hidden fields, we need to create some helper
2657 functions: ::
2658
2659     inc :: Counter a -> Counter a
2660     inc (NewCounter x i d t) = NewCounter
2661         { _this = i x, _inc = i, _display = d, tag = t }
2662
2663     display :: Counter a -> IO ()
2664     display NewCounter{ _this = x, _display = d } = d x
2665
2666 Now we can define counters with different underlying implementations: ::
2667
2668     counterA :: Counter String
2669     counterA = NewCounter
2670         { _this = 0, _inc = (1+), _display = print, tag = "A" }
2671
2672     counterB :: Counter String
2673     counterB = NewCounter
2674         { _this = "", _inc = ('#':), _display = putStrLn, tag = "B" }
2675
2676     main = do
2677         display (inc counterA)         -- prints "1"
2678         display (inc (inc counterB))   -- prints "##"
2679
2680 Record update syntax is supported for existentials (and GADTs): ::
2681
2682     setTag :: Counter a -> a -> Counter a
2683     setTag obj t = obj{ tag = t }
2684
2685 The rule for record update is this:
2686
2687     the types of the updated fields may mention only the universally-quantified
2688     type variables of the data constructor. For GADTs, the field may mention
2689     only types that appear as a simple type-variable argument in the
2690     constructor's result type.
2691
2692 For example: ::
2693
2694     data T a b where { T1 { f1::a, f2::b, f3::(b,c) } :: T a b } -- c is existential
2695     upd1 t x = t { f1=x }   -- OK:   upd1 :: T a b -> a' -> T a' b
2696     upd2 t x = t { f3=x }   -- BAD   (f3's type mentions c, which is
2697                             --        existentially quantified)
2698
2699     data G a b where { G1 { g1::a, g2::c } :: G a [c] }
2700     upd3 g x = g { g1=x }   -- OK:   upd3 :: G a b -> c -> G c b
2701     upd4 g x = g { g2=x }   -- BAD (f2's type mentions c, which is not a simple
2702                             --      type-variable argument in G1's result type)
2703
2704 Restrictions
2705 ~~~~~~~~~~~~
2706
2707 There are several restrictions on the ways in which existentially-quantified
2708 constructors can be used.
2709
2710 -  When pattern matching, each pattern match introduces a new, distinct,
2711    type for each existential type variable. These types cannot be
2712    unified with any other type, nor can they escape from the scope of
2713    the pattern match. For example, these fragments are incorrect: ::
2714
2715        f1 (MkFoo a f) = a
2716
2717    Here, the type bound by ``MkFoo`` "escapes", because ``a`` is the
2718    result of ``f1``. One way to see why this is wrong is to ask what
2719    type ``f1`` has: ::
2720
2721          f1 :: Foo -> a             -- Weird!
2722
2723    What is this "``a``" in the result type? Clearly we don't mean this: ::
2724
2725          f1 :: forall a. Foo -> a   -- Wrong!
2726
2727    The original program is just plain wrong. Here's another sort of
2728    error ::
2729
2730          f2 (Baz1 a b) (Baz1 p q) = a==q
2731
2732    It's ok to say ``a==b`` or ``p==q``, but ``a==q`` is wrong because it
2733    equates the two distinct types arising from the two ``Baz1``
2734    constructors.
2735
2736 -  You can't pattern-match on an existentially quantified constructor in
2737    a ``let`` or ``where`` group of bindings. So this is illegal: ::
2738
2739          f3 x = a==b where { Baz1 a b = x }
2740
2741    Instead, use a ``case`` expression: ::
2742
2743          f3 x = case x of Baz1 a b -> a==b
2744
2745    In general, you can only pattern-match on an existentially-quantified
2746    constructor in a ``case`` expression or in the patterns of a function
2747    definition. The reason for this restriction is really an
2748    implementation one. Type-checking binding groups is already a
2749    nightmare without existentials complicating the picture. Also an
2750    existential pattern binding at the top level of a module doesn't make
2751    sense, because it's not clear how to prevent the
2752    existentially-quantified type "escaping". So for now, there's a
2753    simple-to-state restriction. We'll see how annoying it is.
2754
2755 -  You can't use existential quantification for ``newtype``
2756    declarations. So this is illegal: ::
2757
2758          newtype T = forall a. Ord a => MkT a
2759
2760    Reason: a value of type ``T`` must be represented as a pair of a
2761    dictionary for ``Ord t`` and a value of type ``t``. That contradicts
2762    the idea that ``newtype`` should have no concrete representation. You
2763    can get just the same efficiency and effect by using ``data`` instead
2764    of ``newtype``. If there is no overloading involved, then there is
2765    more of a case for allowing an existentially-quantified ``newtype``,
2766    because the ``data`` version does carry an implementation cost, but
2767    single-field existentially quantified constructors aren't much use.
2768    So the simple restriction (no existential stuff on ``newtype``)
2769    stands, unless there are convincing reasons to change it.
2770
2771 -  You can't use ``deriving`` to define instances of a data type with
2772    existentially quantified data constructors. Reason: in most cases it
2773    would not make sense. For example:; ::
2774
2775        data T = forall a. MkT [a] deriving( Eq )
2776
2777    To derive ``Eq`` in the standard way we would need to have equality
2778    between the single component of two ``MkT`` constructors: ::
2779
2780        instance Eq T where
2781          (MkT a) == (MkT b) = ???
2782
2783    But ``a`` and ``b`` have distinct types, and so can't be compared.
2784    It's just about possible to imagine examples in which the derived
2785    instance would make sense, but it seems altogether simpler simply to
2786    prohibit such declarations. Define your own instances!
2787
2788 .. _gadt-style:
2789
2790 Declaring data types with explicit constructor signatures
2791 ---------------------------------------------------------
2792
2793 .. extension:: GADTSyntax
2794     :shortdesc: Enable generalised algebraic data type syntax.
2795
2796     :since: 7.2.1
2797
2798     Allow the use of GADT syntax in data type definitions (but not GADTs
2799     themselves; for this see :extension:`GADTs`)
2800
2801 When the ``GADTSyntax`` extension is enabled, GHC allows you to declare
2802 an algebraic data type by giving the type signatures of constructors
2803 explicitly. For example: ::
2804
2805       data Maybe a where
2806           Nothing :: Maybe a
2807           Just    :: a -> Maybe a
2808
2809 The form is called a "GADT-style declaration" because Generalised
2810 Algebraic Data Types, described in :ref:`gadt`, can only be declared
2811 using this form.
2812
2813 Notice that GADT-style syntax generalises existential types
2814 (:ref:`existential-quantification`). For example, these two declarations
2815 are equivalent: ::
2816
2817       data Foo = forall a. MkFoo a (a -> Bool)
2818       data Foo' where { MKFoo :: a -> (a->Bool) -> Foo' }
2819
2820 Any data type that can be declared in standard Haskell 98 syntax can
2821 also be declared using GADT-style syntax. The choice is largely
2822 stylistic, but GADT-style declarations differ in one important respect:
2823 they treat class constraints on the data constructors differently.
2824 Specifically, if the constructor is given a type-class context, that
2825 context is made available by pattern matching. For example: ::
2826
2827       data Set a where
2828         MkSet :: Eq a => [a] -> Set a
2829
2830       makeSet :: Eq a => [a] -> Set a
2831       makeSet xs = MkSet (nub xs)
2832
2833       insert :: a -> Set a -> Set a
2834       insert a (MkSet as) | a `elem` as = MkSet as
2835                           | otherwise   = MkSet (a:as)
2836
2837 A use of ``MkSet`` as a constructor (e.g. in the definition of
2838 ``makeSet``) gives rise to a ``(Eq a)`` constraint, as you would expect.
2839 The new feature is that pattern-matching on ``MkSet`` (as in the
2840 definition of ``insert``) makes *available* an ``(Eq a)`` context. In
2841 implementation terms, the ``MkSet`` constructor has a hidden field that
2842 stores the ``(Eq a)`` dictionary that is passed to ``MkSet``; so when
2843 pattern-matching that dictionary becomes available for the right-hand
2844 side of the match. In the example, the equality dictionary is used to
2845 satisfy the equality constraint generated by the call to ``elem``, so
2846 that the type of ``insert`` itself has no ``Eq`` constraint.
2847
2848 For example, one possible application is to reify dictionaries: ::
2849
2850        data NumInst a where
2851          MkNumInst :: Num a => NumInst a
2852
2853        intInst :: NumInst Int
2854        intInst = MkNumInst
2855
2856        plus :: NumInst a -> a -> a -> a
2857        plus MkNumInst p q = p + q
2858
2859 Here, a value of type ``NumInst a`` is equivalent to an explicit
2860 ``(Num a)`` dictionary.
2861
2862 All this applies to constructors declared using the syntax of
2863 :ref:`existential-with-context`. For example, the ``NumInst`` data type
2864 above could equivalently be declared like this: ::
2865
2866        data NumInst a
2867           = Num a => MkNumInst (NumInst a)
2868
2869 Notice that, unlike the situation when declaring an existential, there
2870 is no ``forall``, because the ``Num`` constrains the data type's
2871 universally quantified type variable ``a``. A constructor may have both
2872 universal and existential type variables: for example, the following two
2873 declarations are equivalent: ::
2874
2875        data T1 a
2876         = forall b. (Num a, Eq b) => MkT1 a b
2877        data T2 a where
2878         MkT2 :: (Num a, Eq b) => a -> b -> T2 a
2879
2880 All this behaviour contrasts with Haskell 98's peculiar treatment of
2881 contexts on a data type declaration (Section 4.2.1 of the Haskell 98
2882 Report). In Haskell 98 the definition ::
2883
2884       data Eq a => Set' a = MkSet' [a]
2885
2886 gives ``MkSet'`` the same type as ``MkSet`` above. But instead of
2887 *making available* an ``(Eq a)`` constraint, pattern-matching on
2888 ``MkSet'`` *requires* an ``(Eq a)`` constraint! GHC faithfully
2889 implements this behaviour, odd though it is. But for GADT-style
2890 declarations, GHC's behaviour is much more useful, as well as much more
2891 intuitive.
2892
2893 The rest of this section gives further details about GADT-style data
2894 type declarations.
2895
2896 -  The result type of each data constructor must begin with the type
2897    constructor being defined. If the result type of all constructors has
2898    the form ``T a1 ... an``, where ``a1 ... an`` are distinct type
2899    variables, then the data type is *ordinary*; otherwise is a
2900    *generalised* data type (:ref:`gadt`).
2901
2902 -  As with other type signatures, you can give a single signature for
2903    several data constructors. In this example we give a single signature
2904    for ``T1`` and ``T2``: ::
2905
2906          data T a where
2907            T1,T2 :: a -> T a
2908            T3 :: T a
2909
2910 -  The type signature of each constructor is independent, and is
2911    implicitly universally quantified as usual. In particular, the type
2912    variable(s) in the "``data T a where``" header have no scope, and
2913    different constructors may have different universally-quantified type
2914    variables: ::
2915
2916          data T a where        -- The 'a' has no scope
2917            T1,T2 :: b -> T b   -- Means forall b. b -> T b
2918            T3 :: T a           -- Means forall a. T a
2919
2920 -  A constructor signature may mention type class constraints, which can
2921    differ for different constructors. For example, this is fine: ::
2922
2923          data T a where
2924            T1 :: Eq b => b -> b -> T b
2925            T2 :: (Show c, Ix c) => c -> [c] -> T c
2926
2927    When pattern matching, these constraints are made available to
2928    discharge constraints in the body of the match. For example: ::
2929
2930          f :: T a -> String
2931          f (T1 x y) | x==y      = "yes"
2932                     | otherwise = "no"
2933          f (T2 a b)             = show a
2934
2935    Note that ``f`` is not overloaded; the ``Eq`` constraint arising from
2936    the use of ``==`` is discharged by the pattern match on ``T1`` and
2937    similarly the ``Show`` constraint arising from the use of ``show``.
2938
2939 -  Unlike a Haskell-98-style data type declaration, the type variable(s)
2940    in the "``data Set a where``" header have no scope. Indeed, one can
2941    write a kind signature instead: ::
2942
2943          data Set :: * -> * where ...
2944
2945    or even a mixture of the two: ::
2946
2947          data Bar a :: (* -> *) -> * where ...
2948
2949    The type variables (if given) may be explicitly kinded, so we could
2950    also write the header for ``Foo`` like this: ::
2951
2952          data Bar a (b :: * -> *) where ...
2953
2954 -  You can use strictness annotations, in the obvious places in the
2955    constructor type: ::
2956
2957          data Term a where
2958              Lit    :: !Int -> Term Int
2959              If     :: Term Bool -> !(Term a) -> !(Term a) -> Term a
2960              Pair   :: Term a -> Term b -> Term (a,b)
2961
2962 -  You can use a ``deriving`` clause on a GADT-style data type
2963    declaration. For example, these two declarations are equivalent ::
2964
2965          data Maybe1 a where {
2966              Nothing1 :: Maybe1 a ;
2967              Just1    :: a -> Maybe1 a
2968            } deriving( Eq, Ord )
2969
2970          data Maybe2 a = Nothing2 | Just2 a
2971               deriving( Eq, Ord )
2972
2973 -  The type signature may have quantified type variables that do not
2974    appear in the result type: ::
2975
2976          data Foo where
2977             MkFoo :: a -> (a->Bool) -> Foo
2978             Nil   :: Foo
2979
2980    Here the type variable ``a`` does not appear in the result type of
2981    either constructor. Although it is universally quantified in the type
2982    of the constructor, such a type variable is often called
2983    "existential". Indeed, the above declaration declares precisely the
2984    same type as the ``data Foo`` in :ref:`existential-quantification`.
2985
2986    The type may contain a class context too, of course: ::
2987
2988          data Showable where
2989            MkShowable :: Show a => a -> Showable
2990
2991 -  You can use record syntax on a GADT-style data type declaration: ::
2992
2993          data Person where
2994              Adult :: { name :: String, children :: [Person] } -> Person
2995              Child :: Show a => { name :: !String, funny :: a } -> Person
2996
2997    As usual, for every constructor that has a field ``f``, the type of
2998    field ``f`` must be the same (modulo alpha conversion). The ``Child``
2999    constructor above shows that the signature may have a context,
3000    existentially-quantified variables, and strictness annotations, just
3001    as in the non-record case. (NB: the "type" that follows the
3002    double-colon is not really a type, because of the record syntax and
3003    strictness annotations. A "type" of this form can appear only in a
3004    constructor signature.)
3005
3006 -  Record updates are allowed with GADT-style declarations, only fields
3007    that have the following property: the type of the field mentions no
3008    existential type variables.
3009
3010 -  As in the case of existentials declared using the Haskell-98-like
3011    record syntax (:ref:`existential-records`), record-selector functions
3012    are generated only for those fields that have well-typed selectors.
3013    Here is the example of that section, in GADT-style syntax: ::
3014
3015        data Counter a where
3016            NewCounter :: { _this    :: self
3017                          , _inc     :: self -> self
3018                          , _display :: self -> IO ()
3019                          , tag      :: a
3020                          } -> Counter a
3021
3022    As before, only one selector function is generated here, that for
3023    ``tag``. Nevertheless, you can still use all the field names in
3024    pattern matching and record construction.
3025
3026 -  In a GADT-style data type declaration there is no obvious way to
3027    specify that a data constructor should be infix, which makes a
3028    difference if you derive ``Show`` for the type. (Data constructors
3029    declared infix are displayed infix by the derived ``show``.) So GHC
3030    implements the following design: a data constructor declared in a
3031    GADT-style data type declaration is displayed infix by ``Show`` iff
3032    (a) it is an operator symbol, (b) it has two arguments, (c) it has a
3033    programmer-supplied fixity declaration. For example
3034
3035    ::
3036
3037           infix 6 (:--:)
3038           data T a where
3039             (:--:) :: Int -> Bool -> T Int
3040
3041 .. _gadt:
3042
3043 Generalised Algebraic Data Types (GADTs)
3044 ----------------------------------------
3045
3046 .. extension:: GADTs
3047     :shortdesc: Enable generalised algebraic data types.
3048         Implies :extension:`GADTSyntax` and :extension:`MonoLocalBinds`.
3049
3050     :implies: :extension:`MonoLocalBinds`, :extension:`GADTSyntax`
3051     :since: 6.8.1
3052
3053     Allow use of Generalised Algebraic Data Types (GADTs).
3054
3055 Generalised Algebraic Data Types generalise ordinary algebraic data
3056 types by allowing constructors to have richer return types. Here is an
3057 example: ::
3058
3059       data Term a where
3060           Lit    :: Int -> Term Int
3061           Succ   :: Term Int -> Term Int
3062           IsZero :: Term Int -> Term Bool
3063           If     :: Term Bool -> Term a -> Term a -> Term a
3064           Pair   :: Term a -> Term b -> Term (a,b)
3065
3066 Notice that the return type of the constructors is not always
3067 ``Term a``, as is the case with ordinary data types. This generality
3068 allows us to write a well-typed ``eval`` function for these ``Terms``: ::
3069
3070       eval :: Term a -> a
3071       eval (Lit i)      = i
3072       eval (Succ t)     = 1 + eval t
3073       eval (IsZero t)   = eval t == 0
3074       eval (If b e1 e2) = if eval b then eval e1 else eval e2
3075       eval (Pair e1 e2) = (eval e1, eval e2)
3076
3077 The key point about GADTs is that *pattern matching causes type
3078 refinement*. For example, in the right hand side of the equation ::
3079
3080       eval :: Term a -> a
3081       eval (Lit i) =  ...
3082
3083 the type ``a`` is refined to ``Int``. That's the whole point! A precise
3084 specification of the type rules is beyond what this user manual aspires
3085 to, but the design closely follows that described in the paper `Simple
3086 unification-based type inference for
3087 GADTs <http://research.microsoft.com/%7Esimonpj/papers/gadt/>`__, (ICFP
3088 2006). The general principle is this: *type refinement is only carried
3089 out based on user-supplied type annotations*. So if no type signature is
3090 supplied for ``eval``, no type refinement happens, and lots of obscure
3091 error messages will occur. However, the refinement is quite general. For
3092 example, if we had: ::
3093
3094       eval :: Term a -> a -> a
3095       eval (Lit i) j =  i+j
3096
3097 the pattern match causes the type ``a`` to be refined to ``Int``
3098 (because of the type of the constructor ``Lit``), and that refinement
3099 also applies to the type of ``j``, and the result type of the ``case``
3100 expression. Hence the addition ``i+j`` is legal.
3101
3102 These and many other examples are given in papers by Hongwei Xi, and Tim
3103 Sheard. There is a longer introduction `on the
3104 wiki <http://www.haskell.org/haskellwiki/GADT>`__, and Ralf Hinze's `Fun
3105 with phantom
3106 types <http://www.cs.ox.ac.uk/ralf.hinze/publications/With.pdf>`__ also
3107 has a number of examples. Note that papers may use different notation to
3108 that implemented in GHC.
3109
3110 The rest of this section outlines the extensions to GHC that support
3111 GADTs. The extension is enabled with :extension:`GADTs`. The :extension:`GADTs` extension
3112 also sets :extension:`GADTSyntax` and :extension:`MonoLocalBinds`.
3113
3114 -  A GADT can only be declared using GADT-style syntax
3115    (:ref:`gadt-style`); the old Haskell 98 syntax for data declarations
3116    always declares an ordinary data type. The result type of each
3117    constructor must begin with the type constructor being defined, but
3118    for a GADT the arguments to the type constructor can be arbitrary
3119    monotypes. For example, in the ``Term`` data type above, the type of
3120    each constructor must end with ``Term ty``, but the ``ty`` need not
3121    be a type variable (e.g. the ``Lit`` constructor).
3122
3123 -  It is permitted to declare an ordinary algebraic data type using
3124    GADT-style syntax. What makes a GADT into a GADT is not the syntax,
3125    but rather the presence of data constructors whose result type is not
3126    just ``T a b``.
3127
3128 -  You cannot use a ``deriving`` clause for a GADT; only for an ordinary
3129    data type.
3130
3131 -  As mentioned in :ref:`gadt-style`, record syntax is supported. For
3132    example:
3133
3134    ::
3135
3136          data Term a where
3137              Lit    :: { val  :: Int }      -> Term Int
3138              Succ   :: { num  :: Term Int } -> Term Int
3139              Pred   :: { num  :: Term Int } -> Term Int
3140              IsZero :: { arg  :: Term Int } -> Term Bool
3141              Pair   :: { arg1 :: Term a
3142                        , arg2 :: Term b
3143                        }                    -> Term (a,b)
3144              If     :: { cnd  :: Term Bool
3145                        , tru  :: Term a
3146                        , fls  :: Term a
3147                        }                    -> Term a
3148
3149    However, for GADTs there is the following additional constraint:
3150    every constructor that has a field ``f`` must have the same result
3151    type (modulo alpha conversion) Hence, in the above example, we cannot
3152    merge the ``num`` and ``arg`` fields above into a single name.
3153    Although their field types are both ``Term Int``, their selector
3154    functions actually have different types:
3155
3156    ::
3157
3158          num :: Term Int -> Term Int
3159          arg :: Term Bool -> Term Int
3160
3161 -  When pattern-matching against data constructors drawn from a GADT,
3162    for example in a ``case`` expression, the following rules apply:
3163
3164    -  The type of the scrutinee must be rigid.
3165
3166    -  The type of the entire ``case`` expression must be rigid.
3167
3168    -  The type of any free variable mentioned in any of the ``case``
3169       alternatives must be rigid.
3170
3171    A type is "rigid" if it is completely known to the compiler at its
3172    binding site. The easiest way to ensure that a variable a rigid type
3173    is to give it a type signature. For more precise details see `Simple
3174    unification-based type inference for
3175    GADTs <http://research.microsoft.com/%7Esimonpj/papers/gadt/>`__. The
3176    criteria implemented by GHC are given in the Appendix.
3177
3178 .. _record-system-extensions:
3179
3180 Extensions to the record system
3181 ===============================
3182
3183 .. _traditional-record-syntax:
3184
3185 Traditional record syntax
3186 -------------------------
3187
3188 .. extension:: NoTraditionalRecordSyntax
3189     :shortdesc: Disable support for traditional record syntax
3190         (as supported by Haskell 98) ``C {f = x}``
3191
3192     :since: 7.4.1
3193
3194     Disallow use of record syntax.
3195
3196 Traditional record syntax, such as ``C {f = x}``, is enabled by default.
3197 To disable it, you can use the :extension:`NoTraditionalRecordSyntax` extension.
3198
3199 .. _disambiguate-fields:
3200
3201 Record field disambiguation
3202 ---------------------------
3203
3204 .. extension:: DisambiguateRecordFields
3205     :shortdesc: Enable record field disambiguation.
3206         Implied by :extension:`RecordWildCards`.
3207
3208     :since: 6.8.1
3209
3210     :since: 6.8.1
3211
3212     Allow the compiler to automatically choose between identically-named
3213     record selectors based on type (if the choice is unambiguous).
3214
3215 In record construction and record pattern matching it is entirely
3216 unambiguous which field is referred to, even if there are two different
3217 data types in scope with a common field name. For example:
3218
3219 ::
3220
3221     module M where
3222       data S = MkS { x :: Int, y :: Bool }
3223
3224     module Foo where
3225       import M
3226
3227       data T = MkT { x :: Int }
3228
3229       ok1 (MkS { x = n }) = n+1   -- Unambiguous
3230       ok2 n = MkT { x = n+1 }     -- Unambiguous
3231
3232       bad1 k = k { x = 3 }        -- Ambiguous
3233       bad2 k = x k                -- Ambiguous
3234
3235 Even though there are two ``x``'s in scope, it is clear that the ``x``
3236 in the pattern in the definition of ``ok1`` can only mean the field
3237 ``x`` from type ``S``. Similarly for the function ``ok2``. However, in
3238 the record update in ``bad1`` and the record selection in ``bad2`` it is
3239 not clear which of the two types is intended.
3240
3241 Haskell 98 regards all four as ambiguous, but with the
3242 :extension:`DisambiguateRecordFields` extension, GHC will accept the former two. The
3243 rules are precisely the same as those for instance declarations in
3244 Haskell 98, where the method names on the left-hand side of the method
3245 bindings in an instance declaration refer unambiguously to the method of
3246 that class (provided they are in scope at all), even if there are other
3247 variables in scope with the same name. This reduces the clutter of
3248 qualified names when you import two records from different modules that
3249 use the same field name.
3250
3251 Some details:
3252
3253 -  Field disambiguation can be combined with punning (see
3254    :ref:`record-puns`). For example: ::
3255
3256        module Foo where
3257          import M
3258          x=True
3259          ok3 (MkS { x }) = x+1   -- Uses both disambiguation and punning
3260
3261 -  With :extension:`DisambiguateRecordFields` you can use *unqualified* field
3262    names even if the corresponding selector is only in scope *qualified*
3263    For example, assuming the same module ``M`` as in our earlier
3264    example, this is legal: ::
3265
3266        module Foo where
3267          import qualified M    -- Note qualified
3268
3269          ok4 (M.MkS { x = n }) = n+1   -- Unambiguous
3270
3271    Since the constructor ``MkS`` is only in scope qualified, you must
3272    name it ``M.MkS``, but the field ``x`` does not need to be qualified
3273    even though ``M.x`` is in scope but ``x`` is not (In effect, it is
3274    qualified by the constructor).
3275
3276 .. _duplicate-record-fields:
3277
3278 Duplicate record fields
3279 -----------------------
3280
3281 .. extension:: DuplicateRecordFields
3282     :shortdesc: Allow definition of record types with identically-named fields.
3283
3284     :implies: :extension:`DisambiguateRecordFields`
3285     :since: 8.0.1
3286
3287     Allow definition of record types with identically-named fields.
3288
3289 Going beyond :extension:`DisambiguateRecordFields` (see :ref:`disambiguate-fields`),
3290 the :extension:`DuplicateRecordFields` extension allows multiple datatypes to be
3291 declared using the same field names in a single module. For example, it allows
3292 this: ::
3293
3294     module M where
3295       data S = MkS { x :: Int }
3296       data T = MkT { x :: Bool }
3297
3298 Uses of fields that are always unambiguous because they mention the constructor,
3299 including construction and pattern-matching, may freely use duplicated field
3300 names. For example, the following are permitted (just as with
3301 :extension:`DisambiguateRecordFields`): ::
3302
3303     s = MkS { x = 3 }
3304
3305     f (MkT { x = b }) = b
3306
3307 Field names used as selector functions or in record updates must be unambiguous,
3308 either because there is only one such field in scope, or because a type
3309 signature is supplied, as described in the following sections.
3310
3311 Selector functions
3312 ~~~~~~~~~~~~~~~~~~
3313
3314 Fields may be used as selector functions only if they are unambiguous, so this
3315 is still not allowed if both ``S(x)`` and ``T(x)`` are in scope: ::
3316
3317     bad r = x r
3318
3319 An ambiguous selector may be disambiguated by the type being "pushed down" to
3320 the occurrence of the selector (see :ref:`higher-rank-type-inference` for more
3321 details on what "pushed down" means). For example, the following are permitted: ::
3322
3323     ok1 = x :: S -> Int
3324
3325     ok2 :: S -> Int
3326     ok2 = x
3327
3328     ok3 = k x -- assuming we already have k :: (S -> Int) -> _
3329
3330 In addition, the datatype that is meant may be given as a type signature on the
3331 argument to the selector: ::
3332
3333     ok4 s = x (s :: S)
3334
3335 However, we do not infer the type of the argument to determine the datatype, or
3336 have any way of deferring the choice to the constraint solver. Thus the
3337 following is ambiguous: ::
3338
3339     bad :: S -> Int
3340     bad s = x s
3341
3342 Even though a field label is duplicated in its defining module, it may be
3343 possible to use the selector unambiguously elsewhere. For example, another
3344 module could import ``S(x)`` but not ``T(x)``, and then use ``x`` unambiguously.
3345
3346 Record updates
3347 ~~~~~~~~~~~~~~
3348
3349 In a record update such as ``e { x = 1 }``, if there are multiple ``x`` fields
3350 in scope, then the type of the context must fix which record datatype is
3351 intended, or a type annotation must be supplied. Consider the following
3352 definitions: ::
3353
3354     data S = MkS { foo :: Int }
3355     data T = MkT { foo :: Int, bar :: Int }
3356     data U = MkU { bar :: Int, baz :: Int }
3357
3358 Without :extension:`DuplicateRecordFields`, an update mentioning ``foo`` will always be
3359 ambiguous if all these definitions were in scope. When the extension is enabled,
3360 there are several options for disambiguating updates:
3361
3362 - Check for types that have all the fields being updated. For example: ::
3363
3364       f x = x { foo = 3, bar = 2 }
3365
3366   Here ``f`` must be updating ``T`` because neither ``S`` nor ``U`` have both
3367   fields.
3368
3369 - Use the type being pushed in to the record update, as in the following: ::
3370
3371       g1 :: T -> T
3372       g1 x = x { foo = 3 }
3373
3374       g2 x = x { foo = 3 } :: T
3375
3376       g3 = k (x { foo = 3 }) -- assuming we already have k :: T -> _
3377
3378 - Use an explicit type signature on the record expression, as in: ::
3379
3380       h x = (x :: T) { foo = 3 }
3381
3382 The type of the expression being updated will not be inferred, and no
3383 constraint-solving will be performed, so the following will be rejected as
3384 ambiguous: ::
3385
3386     let x :: T
3387         x = blah
3388     in x { foo = 3 }
3389
3390     \x -> [x { foo = 3 },  blah :: T ]
3391
3392     \ (x :: T) -> x { foo = 3 }
3393
3394 Import and export of record fields
3395 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3396
3397 When :extension:`DuplicateRecordFields` is enabled, an ambiguous field must be exported
3398 as part of its datatype, rather than at the top level. For example, the
3399 following is legal: ::
3400
3401     module M (S(x), T(..)) where
3402       data S = MkS { x :: Int }
3403       data T = MkT { x :: Bool }
3404
3405 However, this would not be permitted, because ``x`` is ambiguous: ::
3406
3407     module M (x) where ...
3408
3409 Similar restrictions apply on import.
3410
3411 .. _record-puns:
3412
3413 Record puns
3414 -----------
3415
3416 .. extension:: NamedFieldPuns
3417     :shortdesc: Enable record puns.
3418
3419     :since: 6.10.1
3420
3421     Allow use of record puns.
3422
3423 Record puns are enabled by the language extension :extension:`NamedFieldPuns`.
3424
3425 When using records, it is common to write a pattern that binds a
3426 variable with the same name as a record field, such as: ::
3427
3428     data C = C {a :: Int}
3429     f (C {a = a}) = a
3430
3431 Record punning permits the variable name to be elided, so one can simply
3432 write ::
3433
3434     f (C {a}) = a
3435
3436 to mean the same pattern as above. That is, in a record pattern, the
3437 pattern ``a`` expands into the pattern ``a = a`` for the same name
3438 ``a``.
3439
3440 Note that:
3441
3442 -  Record punning can also be used in an expression, writing, for
3443    example, ::
3444
3445        let a = 1 in C {a}
3446
3447    instead of ::
3448
3449        let a = 1 in C {a = a}
3450
3451    The expansion is purely syntactic, so the expanded right-hand side
3452    expression refers to the nearest enclosing variable that is spelled
3453    the same as the field name.
3454
3455 -  Puns and other patterns can be mixed in the same record: ::
3456
3457        data C = C {a :: Int, b :: Int}
3458        f (C {a, b = 4}) = a
3459
3460 -  Puns can be used wherever record patterns occur (e.g. in ``let``
3461    bindings or at the top-level).
3462
3463 -  A pun on a qualified field name is expanded by stripping off the
3464    module qualifier. For example: ::
3465
3466        f (C {M.a}) = a
3467
3468    means ::
3469
3470        f (M.C {M.a = a}) = a
3471
3472    (This is useful if the field selector ``a`` for constructor ``M.C``
3473    is only in scope in qualified form.)
3474
3475 .. _record-wildcards:
3476
3477 Record wildcards
3478 ----------------
3479
3480 .. extension:: RecordWildCards
3481     :shortdesc: Enable record wildcards.
3482         Implies :extension:`DisambiguateRecordFields`.
3483
3484     :implies: :extension:`DisambiguateRecordFields`.
3485     :since: 6.8.1
3486
3487     Allow the use of wildcards in record construction and pattern matching.
3488
3489 Record wildcards are enabled by the language extension :extension:`RecordWildCards`. This
3490 exension implies :extension:`DisambiguateRecordFields`.
3491
3492 For records with many fields, it can be tiresome to write out each field
3493 individually in a record pattern, as in ::
3494
3495     data C = C {a :: Int, b :: Int, c :: Int, d :: Int}
3496     f (C {a = 1, b = b, c = c, d = d}) = b + c + d
3497
3498 Record wildcard syntax permits a "``..``" in a record pattern, where
3499 each elided field ``f`` is replaced by the pattern ``f = f``. For
3500 example, the above pattern can be written as ::
3501
3502     f (C {a = 1, ..}) = b + c + d
3503
3504 More details:
3505
3506 -  Record wildcards in patterns can be mixed with other patterns,
3507    including puns (:ref:`record-puns`); for example, in a pattern
3508    ``(C {a = 1, b, ..})``. Additionally, record wildcards can be used
3509    wherever record patterns occur, including in ``let`` bindings and at
3510    the top-level. For example, the top-level binding ::
3511
3512        C {a = 1, ..} = e
3513
3514    defines ``b``, ``c``, and ``d``.
3515
3516 -  Record wildcards can also be used in an expression, when constructing
3517    a record. For example, ::
3518
3519        let {a = 1; b = 2; c = 3; d = 4} in C {..}
3520
3521    in place of ::
3522
3523        let {a = 1; b = 2; c = 3; d = 4} in C {a=a, b=b, c=c, d=d}
3524
3525    The expansion is purely syntactic, so the record wildcard expression
3526    refers to the nearest enclosing variables that are spelled the same
3527    as the omitted field names.
3528
3529 -  For both pattern and expression wildcards, the "``..``" expands to
3530    the missing *in-scope* record fields. Specifically the expansion of
3531    "``C {..}``" includes ``f`` if and only if:
3532
3533    -  ``f`` is a record field of constructor ``C``.
3534
3535    -  The record field ``f`` is in scope somehow (either qualified or
3536       unqualified).
3537
3538    These rules restrict record wildcards to the situations in which the
3539    user could have written the expanded version. For example ::
3540
3541        module M where
3542          data R = R { a,b,c :: Int }
3543        module X where
3544          import M( R(a,c) )
3545          f b = R { .. }
3546
3547    The ``R{..}`` expands to ``R{M.a=a}``, omitting ``b`` since the
3548    record field is not in scope, and omitting ``c`` since the variable
3549    ``c`` is not in scope (apart from the binding of the record selector
3550    ``c``, of course).
3551
3552 -  When record wildcards are use in record construction, a field ``f``
3553    is initialised only if ``f`` is in scope,
3554    and is not imported or bound at top level.
3555    For example, ``f`` can be bound by an enclosing pattern match or
3556    let/where-binding. For example ::
3557
3558         module M where
3559           import A( a )
3560
3561           data R = R { a,b,c,d :: Int }
3562
3563           c = 3 :: Int
3564
3565           f b = R { .. }  -- Expands to R { b = b, d = d }
3566             where
3567               d = b+1
3568
3569    Here, ``a`` is imported, and ``c`` is bound at top level, so neither
3570    contribute to the expansion of the "``..``".
3571    The motivation here is that it should be
3572    easy for the reader to figure out what the "``..``" expands to.
3573
3574 -  Record wildcards cannot be used (a) in a record update construct, and
3575    (b) for data constructors that are not declared with record fields.
3576    For example: ::
3577
3578        f x = x { v=True, .. }   -- Illegal (a)
3579
3580        data T = MkT Int Bool
3581        g = MkT { .. }           -- Illegal (b)
3582        h (MkT { .. }) = True    -- Illegal (b)
3583
3584
3585 .. _record-field-selector-polymorphism:
3586
3587 Record field selector polymorphism
3588 ----------------------------------
3589
3590 The module :base-ref:`GHC.Records.` defines the following: ::
3591
3592   class HasField (x :: k) r a | x r -> a where
3593     getField :: r -> a
3594
3595 A ``HasField x r a`` constraint represents the fact that ``x`` is a
3596 field of type ``a`` belonging to a record type ``r``.  The
3597 ``getField`` method gives the record selector function.
3598
3599 This allows definitions that are polymorphic over record types with a specified
3600 field.  For example, the following works with any record type that has a field
3601 ``name :: String``: ::
3602
3603   foo :: HasField "name" r String => r -> String
3604   foo r = reverse (getField @"name" r)
3605
3606 ``HasField`` is a magic built-in typeclass (similar to ``Coercible``, for
3607 example).  It is given special treatment by the constraint solver (see
3608 :ref:`solving-hasfield-constraints`).  Users may define their own instances of
3609 ``HasField`` also (see :ref:`virtual-record-fields`).
3610
3611 .. _solving-hasfield-constraints:
3612
3613 Solving HasField constraints
3614 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3615
3616 If the constraint solver encounters a constraint ``HasField x r a``
3617 where ``r`` is a concrete datatype with a field ``x`` in scope, it
3618 will automatically solve the constraint using the field selector as
3619 the dictionary, unifying ``a`` with the type of the field if
3620 necessary.  This happens irrespective of which extensions are enabled.
3621
3622 For example, if the following datatype is in scope ::
3623
3624   data Person = Person { name :: String }
3625
3626 the end result is rather like having an instance ::
3627
3628   instance HasField "name" Person String where
3629     getField = name
3630
3631 except that this instance is not actually generated anywhere, rather
3632 the constraint is solved directly by the constraint solver.
3633
3634 A field must be in scope for the corresponding ``HasField`` constraint
3635 to be solved.  This retains the existing representation hiding
3636 mechanism, whereby a module may choose not to export a field,
3637 preventing client modules from accessing or updating it directly.
3638
3639 Solving ``HasField`` constraints depends on the field selector functions that
3640 are generated for each datatype definition:
3641
3642 -  If a record field does not have a selector function because its type would allow
3643    an existential variable to escape, the corresponding ``HasField`` constraint
3644    will not be solved.  For example, ::
3645
3646      {-# LANGUAGE ExistentialQuantification #-}
3647      data Exists t = forall x . MkExists { unExists :: t x }
3648
3649    does not give rise to a selector ``unExists :: Exists t -> t x`` and we will not
3650    solve ``HasField "unExists" (Exists t) a`` automatically.
3651
3652 -  If a record field has a polymorphic type (and hence the selector function is
3653    higher-rank), the corresponding ``HasField`` constraint will not be solved,
3654    because doing so would violate the functional dependency on ``HasField`` and/or
3655    require impredicativity.  For example, ::
3656
3657      {-# LANGUAGE RankNTypes #-}
3658      data Higher = MkHigher { unHigher :: forall t . t -> t }
3659
3660    gives rise to a selector ``unHigher :: Higher -> (forall t . t -> t)`` but does
3661    not lead to solution of the constraint ``HasField "unHigher" Higher a``.
3662
3663 -  A record GADT may have a restricted type for a selector function, which may lead
3664    to additional unification when solving ``HasField`` constraints.  For example, ::
3665
3666      {-# LANGUAGE GADTs #-}
3667      data Gadt t where
3668        MkGadt :: { unGadt :: Maybe v } -> Gadt [v]
3669
3670    gives rise to a selector ``unGadt :: Gadt [v] -> Maybe v``, so the solver will reduce
3671    the constraint ``HasField "unGadt" (Gadt t) b`` by unifying ``t ~ [v]`` and
3672    ``b ~ Maybe v`` for some fresh metavariable ``v``, rather as if we had an instance ::
3673
3674      instance (t ~ [v], b ~ Maybe v) => HasField "unGadt" (Gadt t) b
3675
3676 -  If a record type has an old-fashioned datatype context, the ``HasField``
3677    constraint will be reduced to solving the constraints from the context.
3678    For example, ::
3679
3680      {-# LANGUAGE DatatypeContexts #-}
3681      data Eq a => Silly a = MkSilly { unSilly :: a }
3682
3683    gives rise to a selector ``unSilly :: Eq a => Silly a -> a``, so
3684    the solver will reduce the constraint ``HasField "unSilly" (Silly a) b`` to
3685    ``Eq a`` (and unify ``a`` with ``b``), rather as if we had an instance ::
3686
3687      instance (Eq a, a ~ b) => HasField "unSilly" (Silly a) b
3688
3689 .. _virtual-record-fields:
3690
3691 Virtual record fields
3692 ~~~~~~~~~~~~~~~~~~~~~
3693
3694 Users may define their own instances of ``HasField``, provided they do
3695 not conflict with the built-in constraint solving behaviour.  This
3696 allows "virtual" record fields to be defined for datatypes that do not
3697 otherwise have them.
3698
3699 For example, this instance would make the ``name`` field of ``Person``
3700 accessible using ``#fullname`` as well: ::
3701
3702   instance HasField "fullname" Person String where
3703     getField = name
3704
3705 More substantially, an anonymous records library could provide
3706 ``HasField`` instances for its anonymous records, and thus be
3707 compatible with the polymorphic record selectors introduced by this
3708 proposal.  For example, something like this makes it possible to use
3709 ``getField`` to access ``Record`` values with the appropriate
3710 string in the type-level list of fields: ::
3711
3712   data Record (xs :: [(k, Type)]) where
3713     Nil  :: Record '[]
3714     Cons :: Proxy x -> a -> Record xs -> Record ('(x, a) ': xs)
3715
3716   instance HasField x (Record ('(x, a) ': xs)) a where
3717     getField (Cons _ v _) = v
3718   instance HasField x (Record xs) a => HasField x (Record ('(y, b) ': xs)) a where
3719     getField (Cons _ _ r) = getField @x r
3720
3721   r :: Record '[ '("name", String) ]
3722   r = Cons Proxy "R" Nil)
3723
3724   x = getField @"name" r
3725
3726 Since representations such as this can support field labels with kinds other
3727 than ``Symbol``, the ``HasField`` class is poly-kinded (even though the built-in
3728 constraint solving works only at kind ``Symbol``).  In particular, this allows
3729 users to declare scoped field labels such as in the following example: ::
3730
3731   data PersonFields = Name
3732
3733   s :: Record '[ '(Name, String) ]
3734   s = Cons Proxy "S" Nil
3735
3736   y = getField @Name s
3737
3738 In order to avoid conflicting with the built-in constraint solving,
3739 the following user-defined ``HasField`` instances are prohibited (in
3740 addition to the usual rules, such as the prohibition on type
3741 families appearing in instance heads):
3742
3743 -  ``HasField _ r _`` where ``r`` is a variable;
3744
3745 -  ``HasField _ (T ...) _`` if ``T`` is a data family (because it
3746    might have fields introduced later, using data instance declarations);
3747
3748 -  ``HasField x (T ...) _`` if ``x`` is a variable and ``T`` has any
3749    fields at all (but this instance is permitted if ``T`` has no fields);
3750
3751 -  ``HasField "foo" (T ...) _`` if ``T`` has a field ``foo`` (but this
3752    instance is permitted if it does not).
3753
3754 If a field has a higher-rank or existential type, the corresponding ``HasField``
3755 constraint will not be solved automatically (as described above), but in the
3756 interests of simplicity we do not permit users to define their own instances
3757 either.  If a field is not in scope, the corresponding instance is still
3758 prohibited, to avoid conflicts in downstream modules.
3759
3760
3761 .. _deriving:
3762
3763 Extensions to the "deriving" mechanism
3764 ======================================
3765
3766 Haskell 98 allows the programmer to add a deriving clause to a data type
3767 declaration, to generate a standard instance declaration for specified class.
3768 GHC extends this mechanism along several axes:
3769
3770 * The derivation mechanism can be used separtely from the data type
3771   declaration, using the `standalone deriving mechanism
3772   <#stand-alone-deriving>`__.
3773
3774 * In Haskell 98, the only derivable classes are ``Eq``,
3775   ``Ord``, ``Enum``, ``Ix``, ``Bounded``, ``Read``, and ``Show``. `Various
3776   langauge extensions <#deriving-extra>`__ extend this list.
3777
3778 * Besides the stock approach to deriving instances by generating all method
3779   definitions, GHC supports two additional deriving strategies, which can
3780   derive arbitrary classes:
3781
3782   * `Generalised newtype deriving <#newtype-deriving>`__ for newtypes and
3783   * `deriving any class <#derive-any-class>`__ using an empty instance
3784     declaration.
3785
3786   The user can optionally declare the desired `deriving strategy
3787   <#deriving-stragies>`__, especially if the compiler chooses the wrong
3788   one `by default <#default-deriving-strategy>`__.
3789
3790 .. _empty-data-deriving:
3791
3792 Deriving instances for empty data types
3793 ---------------------------------------
3794
3795 .. ghc-flag:: -XEmptyDataDeriving
3796     :shortdesc: Allow deriving instances of standard type classes for
3797                 empty data types.
3798     :type: dynamic
3799     :reverse: -XNoEmptyDataDeriving
3800     :category:
3801
3802     :since: 8.4.1
3803
3804     Allow deriving instances of standard type classes for empty data types.
3805
3806 One can write data types with no constructors using the
3807 :ghc-flag:`-XEmptyDataDecls` flag (see :ref:`nullary-types`), which is on by
3808 default in Haskell 2010. What is not on by default is the ability to derive
3809 type class instances for these types. This ability is enabled through use of
3810 the :ghc-flag:`-XEmptyDataDeriving` flag. For instance, this lets one write: ::
3811
3812     data Empty deriving (Eq, Ord, Read, Show)
3813
3814 This would generate the following instances: ::
3815
3816     instance Eq Empty where
3817       _ == _ = True
3818
3819     instance Ord Empty where
3820       compare _ _ = EQ
3821
3822     instance Read Empty where
3823       readPrec = pfail
3824
3825     instance Show Empty where
3826       showsPrec _ x = case x of {}
3827
3828 The :ghc-flag:`-XEmptyDataDeriving` flag is only required to enable deriving
3829 of these four "standard" type classes (which are mentioned in the Haskell
3830 Report). Other extensions to the ``deriving`` mechanism, which are explained
3831 below in greater detail, do not require :ghc-flag:`-XEmptyDataDeriving` to be
3832 used in conjunction with empty data types. These include:
3833
3834 * :ghc-flag:`-XStandaloneDeriving` (see :ref:`stand-alone-deriving`)
3835 * Type classes which require their own extensions to be enabled to be derived,
3836   such as :ghc-flag:`-XDeriveFunctor` (see :ref:`deriving-extra`)
3837 * :ghc-flag:`-XDeriveAnyClass` (see :ref:`derive-any-class`)
3838
3839 .. _deriving-inferred:
3840
3841 Inferred context for deriving clauses
3842 -------------------------------------
3843
3844 The Haskell Report is vague about exactly when a ``deriving`` clause is
3845 legal. For example: ::
3846
3847       data T0 f a = MkT0 a         deriving( Eq )
3848       data T1 f a = MkT1 (f a)     deriving( Eq )
3849       data T2 f a = MkT2 (f (f a)) deriving( Eq )
3850
3851 The natural generated ``Eq`` code would result in these instance
3852 declarations: ::
3853
3854       instance Eq a         => Eq (T0 f a) where ...
3855       instance Eq (f a)     => Eq (T1 f a) where ...
3856       instance Eq (f (f a)) => Eq (T2 f a) where ...
3857
3858 The first of these is obviously fine. The second is still fine, although
3859 less obviously. The third is not Haskell 98, and risks losing
3860 termination of instances.
3861
3862 GHC takes a conservative position: it accepts the first two, but not the
3863 third. The rule is this: each constraint in the inferred instance
3864 context must consist only of type variables, with no repetitions.
3865
3866 This rule is applied regardless of flags. If you want a more exotic
3867 context, you can write it yourself, using the `standalone deriving
3868 mechanism <#stand-alone-deriving>`__.
3869
3870 .. _stand-alone-deriving:
3871
3872 Stand-alone deriving declarations
3873 ---------------------------------
3874
3875 .. extension:: StandaloneDeriving
3876     :shortdesc: Enable standalone deriving.
3877
3878     :since: 6.8.1
3879
3880     Allow the use of stand-alone ``deriving`` declarations.
3881
3882 GHC allows stand-alone ``deriving`` declarations, enabled by
3883 :extension:`StandaloneDeriving`: ::
3884
3885       data Foo a = Bar a | Baz String
3886
3887       deriving instance Eq a => Eq (Foo a)
3888
3889 The syntax is identical to that of an ordinary instance declaration
3890 apart from (a) the keyword ``deriving``, and (b) the absence of the
3891 ``where`` part.
3892
3893 However, standalone deriving differs from a ``deriving`` clause in a
3894 number of important ways:
3895
3896 -  The standalone deriving declaration does not need to be in the same
3897    module as the data type declaration. (But be aware of the dangers of
3898    orphan instances (:ref:`orphan-modules`).
3899
3900 -  You must supply an explicit context (in the example the context is
3901    ``(Eq a)``), exactly as you would in an ordinary instance
3902    declaration. (In contrast, in a ``deriving`` clause attached to a
3903    data type declaration, the context is inferred.)
3904
3905 -  Unlike a ``deriving`` declaration attached to a ``data`` declaration,
3906    the instance can be more specific than the data type (assuming you
3907    also use :extension:`FlexibleInstances`, :ref:`instance-rules`). Consider
3908    for example ::
3909
3910          data Foo a = Bar a | Baz String
3911
3912          deriving instance Eq a => Eq (Foo [a])
3913          deriving instance Eq a => Eq (Foo (Maybe a))
3914
3915    This will generate a derived instance for ``(Foo [a])`` and
3916    ``(Foo (Maybe a))``, but other types such as ``(Foo (Int,Bool))``
3917    will not be an instance of ``Eq``.
3918
3919 -  Unlike a ``deriving`` declaration attached to a ``data`` declaration,
3920    GHC does not restrict the form of the data type. Instead, GHC simply
3921    generates the appropriate boilerplate code for the specified class,
3922    and typechecks it. If there is a type error, it is your problem. (GHC
3923    will show you the offending code if it has a type error.)
3924
3925    The merit of this is that you can derive instances for GADTs and
3926    other exotic data types, providing only that the boilerplate code
3927    does indeed typecheck. For example: ::
3928
3929          data T a where
3930             T1 :: T Int
3931             T2 :: T Bool
3932
3933          deriving instance Show (T a)
3934
3935    In this example, you cannot say ``... deriving( Show )`` on the data
3936    type declaration for ``T``, because ``T`` is a GADT, but you *can*
3937    generate the instance declaration using stand-alone deriving.
3938
3939    The down-side is that, if the boilerplate code fails to typecheck,
3940    you will get an error message about that code, which you did not
3941    write. Whereas, with a ``deriving`` clause the side-conditions are
3942    necessarily more conservative, but any error message may be more
3943    comprehensible.
3944
3945 -  Under most circumstances, you cannot use standalone deriving to create an
3946    instance for a data type whose constructors are not all in scope. This is
3947    because the derived instance would generate code that uses the constructors
3948    behind the scenes, which would break abstraction.
3949
3950    The one exception to this rule is :extension:`DeriveAnyClass`, since
3951    deriving an instance via :extension:`DeriveAnyClass` simply generates
3952    an empty instance declaration, which does not require the use of any
3953    constructors. See the `deriving any class <#derive-any-class>`__ section
3954    for more details.
3955
3956 In other ways, however, a standalone deriving obeys the same rules as
3957 ordinary deriving:
3958
3959 -  A ``deriving instance`` declaration must obey the same rules
3960    concerning form and termination as ordinary instance declarations,
3961    controlled by the same flags; see :ref:`instance-decls`.
3962
3963 -  The stand-alone syntax is generalised for newtypes in exactly the
3964    same way that ordinary ``deriving`` clauses are generalised
3965    (:ref:`newtype-deriving`). For example: ::
3966
3967          newtype Foo a = MkFoo (State Int a)
3968
3969          deriving instance MonadState Int Foo
3970
3971    GHC always treats the *last* parameter of the instance (``Foo`` in
3972    this example) as the type whose instance is being derived.
3973
3974 .. _deriving-extra:
3975
3976 Deriving instances of extra classes (``Data``, etc.)
3977 ----------------------------------------------------
3978
3979 Haskell 98 allows the programmer to add "``deriving( Eq, Ord )``" to a
3980 data type declaration, to generate a standard instance declaration for
3981 classes specified in the ``deriving`` clause. In Haskell 98, the only
3982 classes that may appear in the ``deriving`` clause are the standard
3983 classes ``Eq``, ``Ord``, ``Enum``, ``Ix``, ``Bounded``, ``Read``, and
3984 ``Show``.
3985
3986 GHC extends this list with several more classes that may be
3987 automatically derived:
3988
3989 -  With :extension:`DeriveGeneric`, you can derive instances of the classes
3990    ``Generic`` and ``Generic1``, defined in ``GHC.Generics``. You can
3991    use these to define generic functions, as described in
3992    :ref:`generic-programming`.
3993
3994 -  With :extension:`DeriveFunctor`, you can derive instances of the class
3995    ``Functor``, defined in ``GHC.Base``.
3996
3997 -  With :extension:`DeriveDataTypeable`, you can derive instances of the class
3998    ``Data``, defined in ``Data.Data``.
3999
4000 -  With :extension:`DeriveFoldable`, you can derive instances of the class
4001    ``Foldable``, defined in ``Data.Foldable``.
4002
4003 -  With :extension:`DeriveTraversable`, you can derive instances of the class
4004    ``Traversable``, defined in ``Data.Traversable``. Since the
4005    ``Traversable`` instance dictates the instances of ``Functor`` and
4006    ``Foldable``, you'll probably want to derive them too, so
4007    :extension:`DeriveTraversable` implies :extension:`DeriveFunctor` and
4008    :extension:`DeriveFoldable`.
4009
4010 -  With :extension:`DeriveLift`, you can derive instances of the class ``Lift``,
4011    defined in the ``Language.Haskell.TH.Syntax`` module of the
4012    ``template-haskell`` package.
4013
4014 You can also use a standalone deriving declaration instead (see
4015 :ref:`stand-alone-deriving`).
4016
4017 In each case the appropriate class must be in scope before it can be
4018 mentioned in the ``deriving`` clause.
4019
4020 .. _deriving-functor:
4021
4022 Deriving ``Functor`` instances
4023 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
4024
4025 .. extension:: DeriveFunctor
4026     :shortdesc: Enable deriving for the Functor class.
4027         Implied by :extension:`DeriveTraversable`.
4028
4029     :since: 7.10.1
4030
4031     Allow automatic deriving of instances for the ``Functor`` typeclass.
4032
4033
4034 With :extension:`DeriveFunctor`, one can derive ``Functor`` instances for data types
4035 of kind ``* -> *``. For example, this declaration::
4036
4037     data Example a = Ex a Char (Example a) (Example Char)
4038       deriving Functor
4039
4040 would generate the following instance: ::
4041
4042     instance Functor Example where
4043       fmap f (Ex a1 a2 a3 a4) = Ex (f a1) a2 (fmap f a3) a4
4044
4045 The basic algorithm for :extension:`DeriveFunctor` walks the arguments of each
4046 constructor of a data type, applying a mapping function depending on the type
4047 of each argument. If a plain type variable is found that is syntactically
4048 equivalent to the last type parameter of the data type (``a`` in the above
4049 example), then we apply the function ``f`` directly to it. If a type is
4050 encountered that is not syntactically equivalent to the last type parameter
4051 *but does mention* the last type parameter somewhere in it, then a recursive
4052 call to ``fmap`` is made. If a type is found which doesn't mention the last
4053 type parameter at all, then it is left alone.
4054
4055 The second of those cases, in which a type is unequal to the type parameter but
4056 does contain the type parameter, can be surprisingly tricky. For example, the
4057 following example compiles::
4058
4059     newtype Right a = Right (Either Int a) deriving Functor
4060
4061 Modifying the code slightly, however, produces code which will not compile::
4062
4063     newtype Wrong a = Wrong (Either a Int) deriving Functor
4064
4065 The difference involves the placement of the last type parameter, ``a``. In the
4066 ``Right`` case, ``a`` occurs within the type ``Either Int a``, and moreover, it
4067 appears as the last type argument of ``Either``. In the ``Wrong`` case,
4068 however, ``a`` is not the last type argument to ``Either``; rather, ``Int`` is.
4069
4070 This distinction is important because of the way :extension:`DeriveFunctor` works. The
4071 derived ``Functor Right`` instance would be::
4072
4073     instance Functor Right where
4074       fmap f (Right a) = Right (fmap f a)
4075
4076 Given a value of type ``Right a``, GHC must produce a value of type
4077 ``Right b``. Since the argument to the ``Right`` constructor has type
4078 ``Either Int a``, the code recursively calls ``fmap`` on it to produce a value
4079 of type ``Either Int b``, which is used in turn to construct a final value of
4080 type ``Right b``.
4081
4082 The generated code for the ``Functor Wrong`` instance would look exactly the
4083 same, except with ``Wrong`` replacing every occurrence of ``Right``. The
4084 problem is now that ``fmap`` is being applied recursively to a value of type
4085 ``Either a Int``. This cannot possibly produce a value of type
4086 ``Either b Int``, as ``fmap`` can only change the last type parameter! This
4087 causes the generated code to be ill-typed.
4088
4089 As a general rule, if a data type has a derived ``Functor`` instance and its
4090 last type parameter occurs on the right-hand side of the data declaration, then
4091 either it must (1) occur bare (e.g., ``newtype Id a = a``), or (2) occur as the
4092 last argument of a type constructor (as in ``Right`` above).
4093
4094 There are two exceptions to this rule:
4095
4096 #. Tuple types. When a non-unit tuple is used on the right-hand side of a data
4097    declaration, :extension:`DeriveFunctor` treats it as a product of distinct types.
4098    In other words, the following code::
4099
4100        newtype Triple a = Triple (a, Int, [a]) deriving Functor
4101
4102    Would result in a generated ``Functor`` instance like so::
4103
4104        instance Functor Triple where
4105          fmap f (Triple a) =
4106            Triple (case a of
4107                         (a1, a2, a3) -> (f a1, a2, fmap f a3))
4108
4109    That is, :extension:`DeriveFunctor` pattern-matches its way into tuples and maps
4110    over each type that constitutes the tuple. The generated code is
4111    reminiscient of what would be generated from
4112    ``data Triple a = Triple a Int [a]``, except with extra machinery to handle
4113    the tuple.
4114
4115 #. Function types. The last type parameter can appear anywhere in a function
4116    type as long as it occurs in a *covariant* position. To illustrate what this
4117    means, consider the following three examples::
4118
4119        newtype CovFun1 a = CovFun1 (Int -> a) deriving Functor
4120        newtype CovFun2 a = CovFun2 ((a -> Int) -> a) deriving Functor
4121        newtype CovFun3 a = CovFun3 (((Int -> a) -> Int) -> a) deriving Functor
4122
4123    All three of these examples would compile without issue. On the other hand::
4124
4125        newtype ContraFun1 a = ContraFun1 (a -> Int) deriving Functor
4126        newtype ContraFun2 a = ContraFun2 ((Int -> a) -> Int) deriving Functor