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