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