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