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