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