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