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