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