Remove the Unicode alternative for ".." (#3894)
[ghc-hetmet.git] / docs / users_guide / glasgow_exts.xml
1 <?xml version="1.0" encoding="iso-8859-1"?>
2 <para>
3 <indexterm><primary>language, GHC</primary></indexterm>
4 <indexterm><primary>extensions, GHC</primary></indexterm>
5 As with all known Haskell systems, GHC implements some extensions to
6 the language.  They are all enabled by options; by default GHC
7 understands only plain Haskell 98.
8 </para>
9
10 <para>
11 Some of the Glasgow extensions serve to give you access to the
12 underlying facilities with which we implement Haskell.  Thus, you can
13 get at the Raw Iron, if you are willing to write some non-portable
14 code at a more primitive level.  You need not be &ldquo;stuck&rdquo;
15 on performance because of the implementation costs of Haskell's
16 &ldquo;high-level&rdquo; features&mdash;you can always code
17 &ldquo;under&rdquo; them.  In an extreme case, you can write all your
18 time-critical code in C, and then just glue it together with Haskell!
19 </para>
20
21 <para>
22 Before you get too carried away working at the lowest level (e.g.,
23 sloshing <literal>MutableByteArray&num;</literal>s around your
24 program), you may wish to check if there are libraries that provide a
25 &ldquo;Haskellised veneer&rdquo; over the features you want.  The
26 separate <ulink url="../libraries/index.html">libraries
27 documentation</ulink> describes all the libraries that come with GHC.
28 </para>
29
30 <!-- LANGUAGE OPTIONS -->
31   <sect1 id="options-language">
32     <title>Language options</title>
33
34     <indexterm><primary>language</primary><secondary>option</secondary>
35     </indexterm>
36     <indexterm><primary>options</primary><secondary>language</secondary>
37     </indexterm>
38     <indexterm><primary>extensions</primary><secondary>options controlling</secondary>
39     </indexterm>
40
41     <para>The language option flags control what variation of the language are
42     permitted.  Leaving out all of them gives you standard Haskell
43     98.</para>
44
45     <para>Language options can be controlled in two ways:
46     <itemizedlist>
47       <listitem><para>Every language option can switched on by a command-line flag "<option>-X...</option>" 
48         (e.g. <option>-XTemplateHaskell</option>), and switched off by the flag "<option>-XNo...</option>"; 
49         (e.g. <option>-XNoTemplateHaskell</option>).</para></listitem>
50       <listitem><para>
51           Language options recognised by Cabal can also be enabled using the <literal>LANGUAGE</literal> pragma,
52           thus <literal>{-# LANGUAGE TemplateHaskell #-}</literal> (see <xref linkend="language-pragma"/>). </para>
53           </listitem>
54       </itemizedlist></para>
55
56     <para>The flag <option>-fglasgow-exts</option>
57           <indexterm><primary><option>-fglasgow-exts</option></primary></indexterm>
58           is equivalent to enabling the following extensions: 
59           <option>-XPrintExplicitForalls</option>,
60           <option>-XForeignFunctionInterface</option>,
61           <option>-XUnliftedFFITypes</option>,
62           <option>-XGADTs</option>,
63           <option>-XImplicitParams</option>,
64           <option>-XScopedTypeVariables</option>,
65           <option>-XUnboxedTuples</option>,
66           <option>-XTypeSynonymInstances</option>,
67           <option>-XStandaloneDeriving</option>,
68           <option>-XDeriveDataTypeable</option>,
69           <option>-XFlexibleContexts</option>,
70           <option>-XFlexibleInstances</option>,
71           <option>-XConstrainedClassMethods</option>,
72           <option>-XMultiParamTypeClasses</option>,
73           <option>-XFunctionalDependencies</option>,
74           <option>-XMagicHash</option>,
75           <option>-XPolymorphicComponents</option>,
76           <option>-XExistentialQuantification</option>,
77           <option>-XUnicodeSyntax</option>,
78           <option>-XPostfixOperators</option>,
79           <option>-XPatternGuards</option>,
80           <option>-XLiberalTypeSynonyms</option>,
81           <option>-XExplicitForAll</option>,
82           <option>-XRankNTypes</option>,
83           <option>-XImpredicativeTypes</option>,
84           <option>-XTypeOperators</option>,
85           <option>-XDoRec</option>,
86           <option>-XParallelListComp</option>,
87           <option>-XEmptyDataDecls</option>,
88           <option>-XKindSignatures</option>,
89           <option>-XGeneralizedNewtypeDeriving</option>,
90           <option>-XTypeFamilies</option>.
91             Enabling these options is the <emphasis>only</emphasis> 
92             effect of <option>-fglasgow-exts</option>.
93           We are trying to move away from this portmanteau flag, 
94           and towards enabling features individually.</para>
95
96   </sect1>
97
98 <!-- UNBOXED TYPES AND PRIMITIVE OPERATIONS -->
99 <sect1 id="primitives">
100   <title>Unboxed types and primitive operations</title>
101
102 <para>GHC is built on a raft of primitive data types and operations;
103 "primitive" in the sense that they cannot be defined in Haskell itself.
104 While you really can use this stuff to write fast code,
105   we generally find it a lot less painful, and more satisfying in the
106   long run, to use higher-level language features and libraries.  With
107   any luck, the code you write will be optimised to the efficient
108   unboxed version in any case.  And if it isn't, we'd like to know
109   about it.</para>
110
111 <para>All these primitive data types and operations are exported by the 
112 library <literal>GHC.Prim</literal>, for which there is 
113 <ulink url="&libraryGhcPrimLocation;/GHC-Prim.html">detailed online documentation</ulink>.
114 (This documentation is generated from the file <filename>compiler/prelude/primops.txt.pp</filename>.)
115 </para>
116 <para>
117 If you want to mention any of the primitive data types or operations in your
118 program, you must first import <literal>GHC.Prim</literal> to bring them
119 into scope.  Many of them have names ending in "&num;", and to mention such
120 names you need the <option>-XMagicHash</option> extension (<xref linkend="magic-hash"/>).
121 </para>
122
123 <para>The primops make extensive use of <link linkend="glasgow-unboxed">unboxed types</link> 
124 and <link linkend="unboxed-tuples">unboxed tuples</link>, which
125 we briefly summarise here. </para>
126   
127 <sect2 id="glasgow-unboxed">
128 <title>Unboxed types
129 </title>
130
131 <para>
132 <indexterm><primary>Unboxed types (Glasgow extension)</primary></indexterm>
133 </para>
134
135 <para>Most types in GHC are <firstterm>boxed</firstterm>, which means
136 that values of that type are represented by a pointer to a heap
137 object.  The representation of a Haskell <literal>Int</literal>, for
138 example, is a two-word heap object.  An <firstterm>unboxed</firstterm>
139 type, however, is represented by the value itself, no pointers or heap
140 allocation are involved.
141 </para>
142
143 <para>
144 Unboxed types correspond to the &ldquo;raw machine&rdquo; types you
145 would use in C: <literal>Int&num;</literal> (long int),
146 <literal>Double&num;</literal> (double), <literal>Addr&num;</literal>
147 (void *), etc.  The <emphasis>primitive operations</emphasis>
148 (PrimOps) on these types are what you might expect; e.g.,
149 <literal>(+&num;)</literal> is addition on
150 <literal>Int&num;</literal>s, and is the machine-addition that we all
151 know and love&mdash;usually one instruction.
152 </para>
153
154 <para>
155 Primitive (unboxed) types cannot be defined in Haskell, and are
156 therefore built into the language and compiler.  Primitive types are
157 always unlifted; that is, a value of a primitive type cannot be
158 bottom.  We use the convention (but it is only a convention) 
159 that primitive types, values, and
160 operations have a <literal>&num;</literal> suffix (see <xref linkend="magic-hash"/>).
161 For some primitive types we have special syntax for literals, also
162 described in the <link linkend="magic-hash">same section</link>.
163 </para>
164
165 <para>
166 Primitive values are often represented by a simple bit-pattern, such
167 as <literal>Int&num;</literal>, <literal>Float&num;</literal>,
168 <literal>Double&num;</literal>.  But this is not necessarily the case:
169 a primitive value might be represented by a pointer to a
170 heap-allocated object.  Examples include
171 <literal>Array&num;</literal>, the type of primitive arrays.  A
172 primitive array is heap-allocated because it is too big a value to fit
173 in a register, and would be too expensive to copy around; in a sense,
174 it is accidental that it is represented by a pointer.  If a pointer
175 represents a primitive value, then it really does point to that value:
176 no unevaluated thunks, no indirections&hellip;nothing can be at the
177 other end of the pointer than the primitive value.
178 A numerically-intensive program using unboxed types can
179 go a <emphasis>lot</emphasis> faster than its &ldquo;standard&rdquo;
180 counterpart&mdash;we saw a threefold speedup on one example.
181 </para>
182
183 <para>
184 There are some restrictions on the use of primitive types:
185 <itemizedlist>
186 <listitem><para>The main restriction
187 is that you can't pass a primitive value to a polymorphic
188 function or store one in a polymorphic data type.  This rules out
189 things like <literal>[Int&num;]</literal> (i.e. lists of primitive
190 integers).  The reason for this restriction is that polymorphic
191 arguments and constructor fields are assumed to be pointers: if an
192 unboxed integer is stored in one of these, the garbage collector would
193 attempt to follow it, leading to unpredictable space leaks.  Or a
194 <function>seq</function> operation on the polymorphic component may
195 attempt to dereference the pointer, with disastrous results.  Even
196 worse, the unboxed value might be larger than a pointer
197 (<literal>Double&num;</literal> for instance).
198 </para>
199 </listitem>
200 <listitem><para> You cannot define a newtype whose representation type
201 (the argument type of the data constructor) is an unboxed type.  Thus,
202 this is illegal:
203 <programlisting>
204   newtype A = MkA Int#
205 </programlisting>
206 </para></listitem>
207 <listitem><para> You cannot bind a variable with an unboxed type
208 in a <emphasis>top-level</emphasis> binding.
209 </para></listitem>
210 <listitem><para> You cannot bind a variable with an unboxed type
211 in a <emphasis>recursive</emphasis> binding.
212 </para></listitem>
213 <listitem><para> You may bind unboxed variables in a (non-recursive,
214 non-top-level) pattern binding, but you must make any such pattern-match
215 strict.  For example, rather than:
216 <programlisting>
217   data Foo = Foo Int Int#
218
219   f x = let (Foo a b, w) = ..rhs.. in ..body..
220 </programlisting>
221 you must write:
222 <programlisting>
223   data Foo = Foo Int Int#
224
225   f x = let !(Foo a b, w) = ..rhs.. in ..body..
226 </programlisting>
227 since <literal>b</literal> has type <literal>Int#</literal>.
228 </para>
229 </listitem>
230 </itemizedlist>
231 </para>
232
233 </sect2>
234
235 <sect2 id="unboxed-tuples">
236 <title>Unboxed Tuples
237 </title>
238
239 <para>
240 Unboxed tuples aren't really exported by <literal>GHC.Exts</literal>,
241 they're available by default with <option>-fglasgow-exts</option>.  An
242 unboxed tuple looks like this:
243 </para>
244
245 <para>
246
247 <programlisting>
248 (# e_1, ..., e_n #)
249 </programlisting>
250
251 </para>
252
253 <para>
254 where <literal>e&lowbar;1..e&lowbar;n</literal> are expressions of any
255 type (primitive or non-primitive).  The type of an unboxed tuple looks
256 the same.
257 </para>
258
259 <para>
260 Unboxed tuples are used for functions that need to return multiple
261 values, but they avoid the heap allocation normally associated with
262 using fully-fledged tuples.  When an unboxed tuple is returned, the
263 components are put directly into registers or on the stack; the
264 unboxed tuple itself does not have a composite representation.  Many
265 of the primitive operations listed in <literal>primops.txt.pp</literal> return unboxed
266 tuples.
267 In particular, the <literal>IO</literal> and <literal>ST</literal> monads use unboxed
268 tuples to avoid unnecessary allocation during sequences of operations.
269 </para>
270
271 <para>
272 There are some pretty stringent restrictions on the use of unboxed tuples:
273 <itemizedlist>
274 <listitem>
275
276 <para>
277 Values of unboxed tuple types are subject to the same restrictions as
278 other unboxed types; i.e. they may not be stored in polymorphic data
279 structures or passed to polymorphic functions.
280
281 </para>
282 </listitem>
283 <listitem>
284
285 <para>
286 No variable can have an unboxed tuple type, nor may a constructor or function
287 argument have an unboxed tuple type.  The following are all illegal:
288
289
290 <programlisting>
291   data Foo = Foo (# Int, Int #)
292
293   f :: (# Int, Int #) -&#62; (# Int, Int #)
294   f x = x
295
296   g :: (# Int, Int #) -&#62; Int
297   g (# a,b #) = a
298
299   h x = let y = (# x,x #) in ...
300 </programlisting>
301 </para>
302 </listitem>
303 </itemizedlist>
304 </para>
305 <para>
306 The typical use of unboxed tuples is simply to return multiple values,
307 binding those multiple results with a <literal>case</literal> expression, thus:
308 <programlisting>
309   f x y = (# x+1, y-1 #)
310   g x = case f x x of { (# a, b #) -&#62; a + b }
311 </programlisting>
312 You can have an unboxed tuple in a pattern binding, thus
313 <programlisting>
314   f x = let (# p,q #) = h x in ..body..
315 </programlisting>
316 If the types of <literal>p</literal> and <literal>q</literal> are not unboxed,
317 the resulting binding is lazy like any other Haskell pattern binding.  The 
318 above example desugars like this:
319 <programlisting>
320   f x = let t = case h x o f{ (# p,q #) -> (p,q)
321             p = fst t
322             q = snd t
323         in ..body..
324 </programlisting>
325 Indeed, the bindings can even be recursive.
326 </para>
327
328 </sect2>
329 </sect1>
330
331
332 <!-- ====================== SYNTACTIC EXTENSIONS =======================  -->
333
334 <sect1 id="syntax-extns">
335 <title>Syntactic extensions</title>
336  
337     <sect2 id="unicode-syntax">
338       <title>Unicode syntax</title>
339       <para>The language
340       extension <option>-XUnicodeSyntax</option><indexterm><primary><option>-XUnicodeSyntax</option></primary></indexterm>
341       enables Unicode characters to be used to stand for certain ASCII
342       character sequences.  The following alternatives are provided:</para>
343
344       <informaltable>
345         <tgroup cols="2" align="left" colsep="1" rowsep="1">
346           <thead>
347             <row>
348               <entry>ASCII</entry>
349               <entry>Unicode alternative</entry>
350               <entry>Code point</entry>
351               <entry>Name</entry>
352             </row>
353           </thead>
354
355 <!--
356                to find the DocBook entities for these characters, find
357                the Unicode code point (e.g. 0x2237), and grep for it in
358                /usr/share/sgml/docbook/xml-dtd-*/ent/* (or equivalent on
359                your system.  Some of these Unicode code points don't have
360                equivalent DocBook entities.
361             -->
362
363           <tbody>
364             <row>
365               <entry><literal>::</literal></entry>
366               <entry>::</entry> <!-- no special char, apparently -->
367               <entry>0x2237</entry>
368               <entry>PROPORTION</entry>
369             </row>
370           </tbody>
371           <tbody>
372             <row>
373               <entry><literal>=&gt;</literal></entry>
374               <entry>&rArr;</entry>
375               <entry>0x21D2</entry>
376               <entry>RIGHTWARDS DOUBLE ARROW</entry>
377             </row>
378           </tbody>
379           <tbody>
380             <row>
381               <entry><literal>forall</literal></entry>
382               <entry>&forall;</entry>
383               <entry>0x2200</entry>
384               <entry>FOR ALL</entry>
385             </row>
386           </tbody>
387           <tbody>
388             <row>
389               <entry><literal>-&gt;</literal></entry>
390               <entry>&rarr;</entry>
391               <entry>0x2192</entry>
392               <entry>RIGHTWARDS ARROW</entry>
393             </row>
394           </tbody>
395           <tbody>
396             <row>
397               <entry><literal>&lt;-</literal></entry>
398               <entry>&larr;</entry>
399               <entry>0x2190</entry>
400               <entry>LEFTWARDS ARROW</entry>
401             </row>
402           </tbody>
403
404           <tbody>
405             <row>
406               <entry>-&lt;</entry>
407               <entry>&larrtl;</entry>
408               <entry>0x2919</entry>
409               <entry>LEFTWARDS ARROW-TAIL</entry>
410             </row>
411           </tbody>
412
413           <tbody>
414             <row>
415               <entry>&gt;-</entry>
416               <entry>&rarrtl;</entry>
417               <entry>0x291A</entry>
418               <entry>RIGHTWARDS ARROW-TAIL</entry>
419             </row>
420           </tbody>
421
422           <tbody>
423             <row>
424               <entry>-&lt;&lt;</entry>
425               <entry></entry>
426               <entry>0x291B</entry>
427               <entry>LEFTWARDS DOUBLE ARROW-TAIL</entry>
428             </row>
429           </tbody>
430
431           <tbody>
432             <row>
433               <entry>&gt;&gt;-</entry>
434               <entry></entry>
435               <entry>0x291C</entry>
436               <entry>RIGHTWARDS DOUBLE ARROW-TAIL</entry>
437             </row>
438           </tbody>
439
440           <tbody>
441             <row>
442               <entry>*</entry>
443               <entry>&starf;</entry>
444               <entry>0x2605</entry>
445               <entry>BLACK STAR</entry>
446             </row>
447           </tbody>
448
449         </tgroup>
450       </informaltable>
451     </sect2>
452
453     <sect2 id="magic-hash">
454       <title>The magic hash</title>
455       <para>The language extension <option>-XMagicHash</option> allows "&num;" as a
456         postfix modifier to identifiers.  Thus, "x&num;" is a valid variable, and "T&num;" is
457         a valid type constructor or data constructor.</para>
458
459       <para>The hash sign does not change sematics at all.  We tend to use variable
460         names ending in "&num;" for unboxed values or types (e.g. <literal>Int&num;</literal>), 
461         but there is no requirement to do so; they are just plain ordinary variables.
462         Nor does the <option>-XMagicHash</option> extension bring anything into scope.
463         For example, to bring <literal>Int&num;</literal> into scope you must 
464         import <literal>GHC.Prim</literal> (see <xref linkend="primitives"/>); 
465         the <option>-XMagicHash</option> extension
466         then allows you to <emphasis>refer</emphasis> to the <literal>Int&num;</literal>
467         that is now in scope.</para>
468       <para> The <option>-XMagicHash</option> also enables some new forms of literals (see <xref linkend="glasgow-unboxed"/>):
469         <itemizedlist> 
470           <listitem><para> <literal>'x'&num;</literal> has type <literal>Char&num;</literal></para> </listitem>
471           <listitem><para> <literal>&quot;foo&quot;&num;</literal> has type <literal>Addr&num;</literal></para> </listitem>
472           <listitem><para> <literal>3&num;</literal> has type <literal>Int&num;</literal>. In general,
473           any Haskell 98 integer lexeme followed by a <literal>&num;</literal> is an <literal>Int&num;</literal> literal, e.g.
474             <literal>-0x3A&num;</literal> as well as <literal>32&num;</literal></para>.</listitem>
475           <listitem><para> <literal>3&num;&num;</literal> has type <literal>Word&num;</literal>. In general,
476           any non-negative Haskell 98 integer lexeme followed by <literal>&num;&num;</literal> 
477               is a <literal>Word&num;</literal>. </para> </listitem>
478           <listitem><para> <literal>3.2&num;</literal> has type <literal>Float&num;</literal>.</para> </listitem>
479           <listitem><para> <literal>3.2&num;&num;</literal> has type <literal>Double&num;</literal></para> </listitem>
480           </itemizedlist>
481       </para>
482    </sect2>
483
484     <sect2 id="new-qualified-operators">
485       <title>New qualified operator syntax</title>
486
487       <para>A new syntax for referencing qualified operators is
488         planned to be introduced by Haskell', and is enabled in GHC
489         with
490         the <option>-XNewQualifiedOperators</option><indexterm><primary><option>-XNewQualifiedOperators</option></primary></indexterm>
491         option.  In the new syntax, the prefix form of a qualified
492         operator is
493         written <literal><replaceable>module</replaceable>.(<replaceable>symbol</replaceable>)</literal>
494         (in Haskell 98 this would
495         be <literal>(<replaceable>module</replaceable>.<replaceable>symbol</replaceable>)</literal>),
496         and the infix form is
497         written <literal>`<replaceable>module</replaceable>.(<replaceable>symbol</replaceable>)`</literal>
498         (in Haskell 98 this would
499         be <literal>`<replaceable>module</replaceable>.<replaceable>symbol</replaceable>`</literal>.
500         For example:
501 <programlisting>
502   add x y = Prelude.(+) x y
503   subtract y = (`Prelude.(-)` y)
504 </programlisting>
505         The new form of qualified operators is intended to regularise
506         the syntax by eliminating odd cases
507         like <literal>Prelude..</literal>.  For example,
508         when <literal>NewQualifiedOperators</literal> is on, it is possible to
509         write the enumerated sequence <literal>[Monday..]</literal>
510         without spaces, whereas in Haskell 98 this would be a
511         reference to the operator &lsquo;<literal>.</literal>&lsquo;
512         from module <literal>Monday</literal>.</para>
513
514       <para>When <option>-XNewQualifiedOperators</option> is on, the old Haskell
515         98 syntax for qualified operators is not accepted, so this
516         option may cause existing Haskell 98 code to break.</para>
517
518     </sect2>
519         
520
521     <!-- ====================== HIERARCHICAL MODULES =======================  -->
522
523
524     <sect2 id="hierarchical-modules">
525       <title>Hierarchical Modules</title>
526
527       <para>GHC supports a small extension to the syntax of module
528       names: a module name is allowed to contain a dot
529       <literal>&lsquo;.&rsquo;</literal>.  This is also known as the
530       &ldquo;hierarchical module namespace&rdquo; extension, because
531       it extends the normally flat Haskell module namespace into a
532       more flexible hierarchy of modules.</para>
533
534       <para>This extension has very little impact on the language
535       itself; modules names are <emphasis>always</emphasis> fully
536       qualified, so you can just think of the fully qualified module
537       name as <quote>the module name</quote>.  In particular, this
538       means that the full module name must be given after the
539       <literal>module</literal> keyword at the beginning of the
540       module; for example, the module <literal>A.B.C</literal> must
541       begin</para>
542
543 <programlisting>module A.B.C</programlisting>
544
545
546       <para>It is a common strategy to use the <literal>as</literal>
547       keyword to save some typing when using qualified names with
548       hierarchical modules.  For example:</para>
549
550 <programlisting>
551 import qualified Control.Monad.ST.Strict as ST
552 </programlisting>
553
554       <para>For details on how GHC searches for source and interface
555       files in the presence of hierarchical modules, see <xref
556       linkend="search-path"/>.</para>
557
558       <para>GHC comes with a large collection of libraries arranged
559       hierarchically; see the accompanying <ulink
560       url="../libraries/index.html">library
561       documentation</ulink>.  More libraries to install are available
562       from <ulink
563       url="http://hackage.haskell.org/packages/hackage.html">HackageDB</ulink>.</para>
564     </sect2>
565
566     <!-- ====================== PATTERN GUARDS =======================  -->
567
568 <sect2 id="pattern-guards">
569 <title>Pattern guards</title>
570
571 <para>
572 <indexterm><primary>Pattern guards (Glasgow extension)</primary></indexterm>
573 The discussion that follows is an abbreviated version of Simon Peyton Jones's original <ulink url="http://research.microsoft.com/~simonpj/Haskell/guards.html">proposal</ulink>. (Note that the proposal was written before pattern guards were implemented, so refers to them as unimplemented.)
574 </para>
575
576 <para>
577 Suppose we have an abstract data type of finite maps, with a
578 lookup operation:
579
580 <programlisting>
581 lookup :: FiniteMap -> Int -> Maybe Int
582 </programlisting>
583
584 The lookup returns <function>Nothing</function> if the supplied key is not in the domain of the mapping, and <function>(Just v)</function> otherwise,
585 where <varname>v</varname> is the value that the key maps to.  Now consider the following definition:
586 </para>
587
588 <programlisting>
589 clunky env var1 var2 | ok1 &amp;&amp; ok2 = val1 + val2
590 | otherwise  = var1 + var2
591 where
592   m1 = lookup env var1
593   m2 = lookup env var2
594   ok1 = maybeToBool m1
595   ok2 = maybeToBool m2
596   val1 = expectJust m1
597   val2 = expectJust m2
598 </programlisting>
599
600 <para>
601 The auxiliary functions are 
602 </para>
603
604 <programlisting>
605 maybeToBool :: Maybe a -&gt; Bool
606 maybeToBool (Just x) = True
607 maybeToBool Nothing  = False
608
609 expectJust :: Maybe a -&gt; a
610 expectJust (Just x) = x
611 expectJust Nothing  = error "Unexpected Nothing"
612 </programlisting>
613
614 <para>
615 What is <function>clunky</function> doing? The guard <literal>ok1 &amp;&amp;
616 ok2</literal> checks that both lookups succeed, using
617 <function>maybeToBool</function> to convert the <function>Maybe</function>
618 types to booleans. The (lazily evaluated) <function>expectJust</function>
619 calls extract the values from the results of the lookups, and binds the
620 returned values to <varname>val1</varname> and <varname>val2</varname>
621 respectively.  If either lookup fails, then clunky takes the
622 <literal>otherwise</literal> case and returns the sum of its arguments.
623 </para>
624
625 <para>
626 This is certainly legal Haskell, but it is a tremendously verbose and
627 un-obvious way to achieve the desired effect.  Arguably, a more direct way
628 to write clunky would be to use case expressions:
629 </para>
630
631 <programlisting>
632 clunky env var1 var2 = case lookup env var1 of
633   Nothing -&gt; fail
634   Just val1 -&gt; case lookup env var2 of
635     Nothing -&gt; fail
636     Just val2 -&gt; val1 + val2
637 where
638   fail = var1 + var2
639 </programlisting>
640
641 <para>
642 This is a bit shorter, but hardly better.  Of course, we can rewrite any set
643 of pattern-matching, guarded equations as case expressions; that is
644 precisely what the compiler does when compiling equations! The reason that
645 Haskell provides guarded equations is because they allow us to write down
646 the cases we want to consider, one at a time, independently of each other. 
647 This structure is hidden in the case version.  Two of the right-hand sides
648 are really the same (<function>fail</function>), and the whole expression
649 tends to become more and more indented. 
650 </para>
651
652 <para>
653 Here is how I would write clunky:
654 </para>
655
656 <programlisting>
657 clunky env var1 var2
658   | Just val1 &lt;- lookup env var1
659   , Just val2 &lt;- lookup env var2
660   = val1 + val2
661 ...other equations for clunky...
662 </programlisting>
663
664 <para>
665 The semantics should be clear enough.  The qualifiers are matched in order. 
666 For a <literal>&lt;-</literal> qualifier, which I call a pattern guard, the
667 right hand side is evaluated and matched against the pattern on the left. 
668 If the match fails then the whole guard fails and the next equation is
669 tried.  If it succeeds, then the appropriate binding takes place, and the
670 next qualifier is matched, in the augmented environment.  Unlike list
671 comprehensions, however, the type of the expression to the right of the
672 <literal>&lt;-</literal> is the same as the type of the pattern to its
673 left.  The bindings introduced by pattern guards scope over all the
674 remaining guard qualifiers, and over the right hand side of the equation.
675 </para>
676
677 <para>
678 Just as with list comprehensions, boolean expressions can be freely mixed
679 with among the pattern guards.  For example:
680 </para>
681
682 <programlisting>
683 f x | [y] &lt;- x
684     , y > 3
685     , Just z &lt;- h y
686     = ...
687 </programlisting>
688
689 <para>
690 Haskell's current guards therefore emerge as a special case, in which the
691 qualifier list has just one element, a boolean expression.
692 </para>
693 </sect2>
694
695     <!-- ===================== View patterns ===================  -->
696
697 <sect2 id="view-patterns">
698 <title>View patterns
699 </title>
700
701 <para>
702 View patterns are enabled by the flag <literal>-XViewPatterns</literal>.
703 More information and examples of view patterns can be found on the
704 <ulink url="http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns">Wiki
705 page</ulink>.
706 </para>
707
708 <para>
709 View patterns are somewhat like pattern guards that can be nested inside
710 of other patterns.  They are a convenient way of pattern-matching
711 against values of abstract types. For example, in a programming language
712 implementation, we might represent the syntax of the types of the
713 language as follows:
714
715 <programlisting>
716 type Typ
717  
718 data TypView = Unit
719              | Arrow Typ Typ
720
721 view :: Type -> TypeView
722
723 -- additional operations for constructing Typ's ...
724 </programlisting>
725
726 The representation of Typ is held abstract, permitting implementations
727 to use a fancy representation (e.g., hash-consing to manage sharing).
728
729 Without view patterns, using this signature a little inconvenient: 
730 <programlisting>
731 size :: Typ -> Integer
732 size t = case view t of
733   Unit -> 1
734   Arrow t1 t2 -> size t1 + size t2
735 </programlisting>
736
737 It is necessary to iterate the case, rather than using an equational
738 function definition. And the situation is even worse when the matching
739 against <literal>t</literal> is buried deep inside another pattern.
740 </para>
741
742 <para>
743 View patterns permit calling the view function inside the pattern and
744 matching against the result: 
745 <programlisting>
746 size (view -> Unit) = 1
747 size (view -> Arrow t1 t2) = size t1 + size t2
748 </programlisting>
749
750 That is, we add a new form of pattern, written
751 <replaceable>expression</replaceable> <literal>-></literal>
752 <replaceable>pattern</replaceable> that means "apply the expression to
753 whatever we're trying to match against, and then match the result of
754 that application against the pattern". The expression can be any Haskell
755 expression of function type, and view patterns can be used wherever
756 patterns are used.
757 </para>
758
759 <para>
760 The semantics of a pattern <literal>(</literal>
761 <replaceable>exp</replaceable> <literal>-></literal>
762 <replaceable>pat</replaceable> <literal>)</literal> are as follows:
763
764 <itemizedlist>
765
766 <listitem> Scoping:
767
768 <para>The variables bound by the view pattern are the variables bound by
769 <replaceable>pat</replaceable>.
770 </para>
771
772 <para>
773 Any variables in <replaceable>exp</replaceable> are bound occurrences,
774 but variables bound "to the left" in a pattern are in scope.  This
775 feature permits, for example, one argument to a function to be used in
776 the view of another argument.  For example, the function
777 <literal>clunky</literal> from <xref linkend="pattern-guards" /> can be
778 written using view patterns as follows:
779
780 <programlisting>
781 clunky env (lookup env -> Just val1) (lookup env -> Just val2) = val1 + val2
782 ...other equations for clunky...
783 </programlisting>
784 </para>
785
786 <para>
787 More precisely, the scoping rules are: 
788 <itemizedlist>
789 <listitem>
790 <para>
791 In a single pattern, variables bound by patterns to the left of a view
792 pattern expression are in scope. For example:
793 <programlisting>
794 example :: Maybe ((String -> Integer,Integer), String) -> Bool
795 example Just ((f,_), f -> 4) = True
796 </programlisting>
797
798 Additionally, in function definitions, variables bound by matching earlier curried
799 arguments may be used in view pattern expressions in later arguments:
800 <programlisting>
801 example :: (String -> Integer) -> String -> Bool
802 example f (f -> 4) = True
803 </programlisting>
804 That is, the scoping is the same as it would be if the curried arguments
805 were collected into a tuple.  
806 </para>
807 </listitem>
808
809 <listitem>
810 <para>
811 In mutually recursive bindings, such as <literal>let</literal>,
812 <literal>where</literal>, or the top level, view patterns in one
813 declaration may not mention variables bound by other declarations.  That
814 is, each declaration must be self-contained.  For example, the following
815 program is not allowed:
816 <programlisting>
817 let {(x -> y) = e1 ;
818      (y -> x) = e2 } in x
819 </programlisting>
820
821 (We may lift this
822 restriction in the future; the only cost is that type checking patterns
823 would get a little more complicated.)  
824
825
826 </para>
827 </listitem>
828 </itemizedlist>
829
830 </para>
831 </listitem>
832
833 <listitem><para> Typing: If <replaceable>exp</replaceable> has type
834 <replaceable>T1</replaceable> <literal>-></literal>
835 <replaceable>T2</replaceable> and <replaceable>pat</replaceable> matches
836 a <replaceable>T2</replaceable>, then the whole view pattern matches a
837 <replaceable>T1</replaceable>.
838 </para></listitem>
839
840 <listitem><para> Matching: To the equations in Section 3.17.3 of the
841 <ulink url="http://www.haskell.org/onlinereport/">Haskell 98
842 Report</ulink>, add the following:
843 <programlisting>
844 case v of { (e -> p) -> e1 ; _ -> e2 } 
845  = 
846 case (e v) of { p -> e1 ; _ -> e2 }
847 </programlisting>
848 That is, to match a variable <replaceable>v</replaceable> against a pattern
849 <literal>(</literal> <replaceable>exp</replaceable>
850 <literal>-></literal> <replaceable>pat</replaceable>
851 <literal>)</literal>, evaluate <literal>(</literal>
852 <replaceable>exp</replaceable> <replaceable> v</replaceable>
853 <literal>)</literal> and match the result against
854 <replaceable>pat</replaceable>.  
855 </para></listitem>
856
857 <listitem><para> Efficiency: When the same view function is applied in
858 multiple branches of a function definition or a case expression (e.g.,
859 in <literal>size</literal> above), GHC makes an attempt to collect these
860 applications into a single nested case expression, so that the view
861 function is only applied once.  Pattern compilation in GHC follows the
862 matrix algorithm described in Chapter 4 of <ulink
863 url="http://research.microsoft.com/~simonpj/Papers/slpj-book-1987/">The
864 Implementation of Functional Programming Languages</ulink>.  When the
865 top rows of the first column of a matrix are all view patterns with the
866 "same" expression, these patterns are transformed into a single nested
867 case.  This includes, for example, adjacent view patterns that line up
868 in a tuple, as in
869 <programlisting>
870 f ((view -> A, p1), p2) = e1
871 f ((view -> B, p3), p4) = e2
872 </programlisting>
873 </para>
874
875 <para> The current notion of when two view pattern expressions are "the
876 same" is very restricted: it is not even full syntactic equality.
877 However, it does include variables, literals, applications, and tuples;
878 e.g., two instances of <literal>view ("hi", "there")</literal> will be
879 collected.  However, the current implementation does not compare up to
880 alpha-equivalence, so two instances of <literal>(x, view x ->
881 y)</literal> will not be coalesced.
882 </para>
883
884 </listitem>
885
886 </itemizedlist>
887 </para>
888
889 </sect2>
890
891     <!-- ===================== n+k patterns ===================  -->
892
893 <sect2 id="n-k-patterns">
894 <title>n+k patterns</title>
895 <indexterm><primary><option>-XNoNPlusKPatterns</option></primary></indexterm>
896
897 <para>
898 <literal>n+k</literal> pattern support is enabled by default. To disable
899 it, you can use the <option>-XNoNPlusKPatterns</option> flag.
900 </para>
901
902 </sect2>
903
904     <!-- ===================== Recursive do-notation ===================  -->
905
906 <sect2 id="recursive-do-notation">
907 <title>The recursive do-notation
908 </title>
909
910 <para>
911 The do-notation of Haskell 98 does not allow <emphasis>recursive bindings</emphasis>,
912 that is, the variables bound in a do-expression are visible only in the textually following 
913 code block. Compare this to a let-expression, where bound variables are visible in the entire binding
914 group. It turns out that several applications can benefit from recursive bindings in
915 the do-notation.  The <option>-XDoRec</option> flag provides the necessary syntactic support.
916 </para>
917 <para>
918 Here is a simple (albeit contrived) example:
919 <programlisting>
920 {-# LANGUAGE DoRec #-}
921 justOnes = do { rec { xs &lt;- Just (1:xs) }
922               ; return (map negate xs) }
923 </programlisting>
924 As you can guess <literal>justOnes</literal> will evaluate to <literal>Just [-1,-1,-1,...</literal>.
925 </para>
926 <para>
927 The background and motivation for recursive do-notation is described in
928 <ulink url="http://sites.google.com/site/leventerkok/">A recursive do for Haskell</ulink>,
929 by Levent Erkok, John Launchbury,
930 Haskell Workshop 2002, pages: 29-37. Pittsburgh, Pennsylvania. 
931 The theory behind monadic value recursion is explained further in Erkok's thesis
932 <ulink url="http://sites.google.com/site/leventerkok/erkok-thesis.pdf">Value Recursion in Monadic Computations</ulink>.
933 However, note that GHC uses a different syntax than the one described in these documents.
934 </para>
935
936 <sect3>
937 <title>Details of recursive do-notation</title>
938 <para>
939 The recursive do-notation is enabled with the flag <option>-XDoRec</option> or, equivalently,
940 the LANGUAGE pragma <option>DoRec</option>.  It introduces the single new keyword "<literal>rec</literal>",
941 which wraps a mutually-recursive group of monadic statements,
942 producing a single statement.
943 </para>
944 <para>Similar to a <literal>let</literal>
945 statement, the variables bound in the <literal>rec</literal> are 
946 visible throughout the <literal>rec</literal> group, and below it.
947 For example, compare
948 <programlisting>
949 do { a &lt;- getChar              do { a &lt;- getChar                    
950    ; let { r1 = f a r2             ; rec { r1 &lt;- f a r2      
951          ; r2 = g r1 }                   ; r2 &lt;- g r1 }      
952    ; return (r1 ++ r2) }          ; return (r1 ++ r2) }
953 </programlisting>
954 In both cases, <literal>r1</literal> and <literal>r2</literal> are 
955 available both throughout the <literal>let</literal> or <literal>rec</literal> block, and
956 in the statements that follow it.  The difference is that <literal>let</literal> is non-monadic,
957 while <literal>rec</literal> is monadic.  (In Haskell <literal>let</literal> is 
958 really <literal>letrec</literal>, of course.)
959 </para>
960 <para>
961 The static and dynamic semantics of <literal>rec</literal> can be described as follows:  
962 <itemizedlist>
963 <listitem><para>
964 First,
965 similar to let-bindings, the <literal>rec</literal> is broken into 
966 minimal recursive groups, a process known as <emphasis>segmentation</emphasis>.
967 For example:
968 <programlisting>
969 rec { a &lt;- getChar      ===>     a &lt;- getChar
970     ; b &lt;- f a c                 rec { b &lt;- f a c
971     ; c &lt;- f b a                     ; c &lt;- f b a }
972     ; putChar c }                putChar c 
973 </programlisting>
974 The details of segmentation are described in Section 3.2 of
975 <ulink url="http://sites.google.com/site/leventerkok/">A recursive do for Haskell</ulink>.
976 Segmentation improves polymorphism, reduces the size of the recursive "knot", and, as the paper 
977 describes, also has a semantic effect (unless the monad satisfies the right-shrinking law).
978 </para></listitem>
979 <listitem><para>
980 Then each resulting <literal>rec</literal> is desugared, using a call to <literal>Control.Monad.Fix.mfix</literal>.
981 For example, the <literal>rec</literal> group in the preceding example is desugared like this:
982 <programlisting>
983 rec { b &lt;- f a c     ===>    (b,c) &lt;- mfix (\~(b,c) -> do { b &lt;- f a c
984     ; c &lt;- f b a }                                        ; c &lt;- f b a
985                                                           ; return (b,c) })
986 </programlisting>
987 In general, the statment <literal>rec <replaceable>ss</replaceable></literal>
988 is desugared to the statement
989 <programlisting>
990 <replaceable>vs</replaceable> &lt;- mfix (\~<replaceable>vs</replaceable> -&gt; do { <replaceable>ss</replaceable>; return <replaceable>vs</replaceable> })
991 </programlisting>
992 where <replaceable>vs</replaceable> is a tuple of the variables bound by <replaceable>ss</replaceable>.
993 </para><para>
994 The original <literal>rec</literal> typechecks exactly 
995 when the above desugared version would do so.  For example, this means that 
996 the variables <replaceable>vs</replaceable> are all monomorphic in the statements
997 following the <literal>rec</literal>, because they are bound by a lambda.
998 </para>
999 <para>
1000 The <literal>mfix</literal> function is defined in the <literal>MonadFix</literal> 
1001 class, in <literal>Control.Monad.Fix</literal>, thus:
1002 <programlisting>
1003 class Monad m => MonadFix m where
1004    mfix :: (a -> m a) -> m a
1005 </programlisting>
1006 </para>
1007 </listitem>
1008 </itemizedlist>
1009 </para>
1010 <para>
1011 Here are some other important points in using the recursive-do notation:
1012 <itemizedlist>
1013 <listitem><para>
1014 It is enabled with the flag <literal>-XDoRec</literal>, which is in turn implied by
1015 <literal>-fglasgow-exts</literal>.
1016 </para></listitem>
1017
1018 <listitem><para>
1019 If recursive bindings are required for a monad,
1020 then that monad must be declared an instance of the <literal>MonadFix</literal> class.
1021 </para></listitem>
1022
1023 <listitem><para>
1024 The following instances of <literal>MonadFix</literal> are automatically provided: List, Maybe, IO. 
1025 Furthermore, the Control.Monad.ST and Control.Monad.ST.Lazy modules provide the instances of the MonadFix class 
1026 for Haskell's internal state monad (strict and lazy, respectively).
1027 </para></listitem>
1028
1029 <listitem><para>
1030 Like <literal>let</literal> and <literal>where</literal> bindings,
1031 name shadowing is not allowed within a <literal>rec</literal>; 
1032 that is, all the names bound in a single <literal>rec</literal> must
1033 be distinct (Section 3.3 of the paper).
1034 </para></listitem>
1035 <listitem><para>
1036 It supports rebindable syntax (see <xref linkend="rebindable-syntax"/>).
1037 </para></listitem>
1038 </itemizedlist>
1039 </para>
1040 </sect3>
1041
1042 <sect3 id="mdo-notation"> <title> Mdo-notation (deprecated) </title>
1043
1044 <para> GHC used to support the flag <option>-XRecursiveDo</option>,
1045 which enabled the keyword <literal>mdo</literal>, precisely as described in
1046 <ulink url="http://sites.google.com/site/leventerkok/">A recursive do for Haskell</ulink>,
1047 but this is now deprecated.  Instead of <literal>mdo { Q; e }</literal>, write
1048 <literal>do { rec Q; e }</literal>.
1049 </para>
1050 <para>
1051 Historical note: The old implementation of the mdo-notation (and most
1052 of the existing documents) used the name
1053 <literal>MonadRec</literal> for the class and the corresponding library.
1054 This name is not supported by GHC.
1055 </para>
1056 </sect3>
1057
1058 </sect2>
1059
1060
1061    <!-- ===================== PARALLEL LIST COMPREHENSIONS ===================  -->
1062
1063   <sect2 id="parallel-list-comprehensions">
1064     <title>Parallel List Comprehensions</title>
1065     <indexterm><primary>list comprehensions</primary><secondary>parallel</secondary>
1066     </indexterm>
1067     <indexterm><primary>parallel list comprehensions</primary>
1068     </indexterm>
1069
1070     <para>Parallel list comprehensions are a natural extension to list
1071     comprehensions.  List comprehensions can be thought of as a nice
1072     syntax for writing maps and filters.  Parallel comprehensions
1073     extend this to include the zipWith family.</para>
1074
1075     <para>A parallel list comprehension has multiple independent
1076     branches of qualifier lists, each separated by a `|' symbol.  For
1077     example, the following zips together two lists:</para>
1078
1079 <programlisting>
1080    [ (x, y) | x &lt;- xs | y &lt;- ys ] 
1081 </programlisting>
1082
1083     <para>The behavior of parallel list comprehensions follows that of
1084     zip, in that the resulting list will have the same length as the
1085     shortest branch.</para>
1086
1087     <para>We can define parallel list comprehensions by translation to
1088     regular comprehensions.  Here's the basic idea:</para>
1089
1090     <para>Given a parallel comprehension of the form: </para>
1091
1092 <programlisting>
1093    [ e | p1 &lt;- e11, p2 &lt;- e12, ... 
1094        | q1 &lt;- e21, q2 &lt;- e22, ... 
1095        ... 
1096    ] 
1097 </programlisting>
1098
1099     <para>This will be translated to: </para>
1100
1101 <programlisting>
1102    [ e | ((p1,p2), (q1,q2), ...) &lt;- zipN [(p1,p2) | p1 &lt;- e11, p2 &lt;- e12, ...] 
1103                                          [(q1,q2) | q1 &lt;- e21, q2 &lt;- e22, ...] 
1104                                          ... 
1105    ] 
1106 </programlisting>
1107
1108     <para>where `zipN' is the appropriate zip for the given number of
1109     branches.</para>
1110
1111   </sect2>
1112   
1113   <!-- ===================== TRANSFORM LIST COMPREHENSIONS ===================  -->
1114
1115   <sect2 id="generalised-list-comprehensions">
1116     <title>Generalised (SQL-Like) List Comprehensions</title>
1117     <indexterm><primary>list comprehensions</primary><secondary>generalised</secondary>
1118     </indexterm>
1119     <indexterm><primary>extended list comprehensions</primary>
1120     </indexterm>
1121     <indexterm><primary>group</primary></indexterm>
1122     <indexterm><primary>sql</primary></indexterm>
1123
1124
1125     <para>Generalised list comprehensions are a further enhancement to the
1126     list comprehension syntactic sugar to allow operations such as sorting
1127     and grouping which are familiar from SQL.   They are fully described in the
1128         paper <ulink url="http://research.microsoft.com/~simonpj/papers/list-comp">
1129           Comprehensive comprehensions: comprehensions with "order by" and "group by"</ulink>,
1130     except that the syntax we use differs slightly from the paper.</para>
1131 <para>The extension is enabled with the flag <option>-XTransformListComp</option>.</para>
1132 <para>Here is an example: 
1133 <programlisting>
1134 employees = [ ("Simon", "MS", 80)
1135 , ("Erik", "MS", 100)
1136 , ("Phil", "Ed", 40)
1137 , ("Gordon", "Ed", 45)
1138 , ("Paul", "Yale", 60)]
1139
1140 output = [ (the dept, sum salary)
1141 | (name, dept, salary) &lt;- employees
1142 , then group by dept
1143 , then sortWith by (sum salary)
1144 , then take 5 ]
1145 </programlisting>
1146 In this example, the list <literal>output</literal> would take on 
1147     the value:
1148     
1149 <programlisting>
1150 [("Yale", 60), ("Ed", 85), ("MS", 180)]
1151 </programlisting>
1152 </para>
1153 <para>There are three new keywords: <literal>group</literal>, <literal>by</literal>, and <literal>using</literal>.
1154 (The function <literal>sortWith</literal> is not a keyword; it is an ordinary
1155 function that is exported by <literal>GHC.Exts</literal>.)</para>
1156
1157 <para>There are five new forms of comprehension qualifier,
1158 all introduced by the (existing) keyword <literal>then</literal>:
1159     <itemizedlist>
1160     <listitem>
1161     
1162 <programlisting>
1163 then f
1164 </programlisting>
1165
1166     This statement requires that <literal>f</literal> have the type <literal>
1167     forall a. [a] -> [a]</literal>. You can see an example of its use in the
1168     motivating example, as this form is used to apply <literal>take 5</literal>.
1169     
1170     </listitem>
1171     
1172     
1173     <listitem>
1174 <para>
1175 <programlisting>
1176 then f by e
1177 </programlisting>
1178
1179     This form is similar to the previous one, but allows you to create a function
1180     which will be passed as the first argument to f. As a consequence f must have 
1181     the type <literal>forall a. (a -> t) -> [a] -> [a]</literal>. As you can see
1182     from the type, this function lets f &quot;project out&quot; some information 
1183     from the elements of the list it is transforming.</para>
1184
1185     <para>An example is shown in the opening example, where <literal>sortWith</literal> 
1186     is supplied with a function that lets it find out the <literal>sum salary</literal> 
1187     for any item in the list comprehension it transforms.</para>
1188
1189     </listitem>
1190
1191
1192     <listitem>
1193
1194 <programlisting>
1195 then group by e using f
1196 </programlisting>
1197
1198     <para>This is the most general of the grouping-type statements. In this form,
1199     f is required to have type <literal>forall a. (a -> t) -> [a] -> [[a]]</literal>.
1200     As with the <literal>then f by e</literal> case above, the first argument
1201     is a function supplied to f by the compiler which lets it compute e on every
1202     element of the list being transformed. However, unlike the non-grouping case,
1203     f additionally partitions the list into a number of sublists: this means that
1204     at every point after this statement, binders occurring before it in the comprehension
1205     refer to <emphasis>lists</emphasis> of possible values, not single values. To help understand
1206     this, let's look at an example:</para>
1207     
1208 <programlisting>
1209 -- This works similarly to groupWith in GHC.Exts, but doesn't sort its input first
1210 groupRuns :: Eq b => (a -> b) -> [a] -> [[a]]
1211 groupRuns f = groupBy (\x y -> f x == f y)
1212
1213 output = [ (the x, y)
1214 | x &lt;- ([1..3] ++ [1..2])
1215 , y &lt;- [4..6]
1216 , then group by x using groupRuns ]
1217 </programlisting>
1218
1219     <para>This results in the variable <literal>output</literal> taking on the value below:</para>
1220
1221 <programlisting>
1222 [(1, [4, 5, 6]), (2, [4, 5, 6]), (3, [4, 5, 6]), (1, [4, 5, 6]), (2, [4, 5, 6])]
1223 </programlisting>
1224
1225     <para>Note that we have used the <literal>the</literal> function to change the type 
1226     of x from a list to its original numeric type. The variable y, in contrast, is left 
1227     unchanged from the list form introduced by the grouping.</para>
1228
1229     </listitem>
1230
1231     <listitem>
1232
1233 <programlisting>
1234 then group by e
1235 </programlisting>
1236
1237     <para>This form of grouping is essentially the same as the one described above. However,
1238     since no function to use for the grouping has been supplied it will fall back on the
1239     <literal>groupWith</literal> function defined in 
1240     <ulink url="&libraryBaseLocation;/GHC-Exts.html"><literal>GHC.Exts</literal></ulink>. This
1241     is the form of the group statement that we made use of in the opening example.</para>
1242
1243     </listitem>
1244     
1245     
1246     <listitem>
1247
1248 <programlisting>
1249 then group using f
1250 </programlisting>
1251
1252     <para>With this form of the group statement, f is required to simply have the type
1253     <literal>forall a. [a] -> [[a]]</literal>, which will be used to group up the
1254     comprehension so far directly. An example of this form is as follows:</para>
1255     
1256 <programlisting>
1257 output = [ x
1258 | y &lt;- [1..5]
1259 , x &lt;- "hello"
1260 , then group using inits]
1261 </programlisting>
1262
1263     <para>This will yield a list containing every prefix of the word "hello" written out 5 times:</para>
1264
1265 <programlisting>
1266 ["","h","he","hel","hell","hello","helloh","hellohe","hellohel","hellohell","hellohello","hellohelloh",...]
1267 </programlisting>
1268
1269     </listitem>
1270 </itemizedlist>
1271 </para>
1272   </sect2>
1273
1274    <!-- ===================== REBINDABLE SYNTAX ===================  -->
1275
1276 <sect2 id="rebindable-syntax">
1277 <title>Rebindable syntax and the implicit Prelude import</title>
1278
1279  <para><indexterm><primary>-XNoImplicitPrelude
1280  option</primary></indexterm> GHC normally imports
1281  <filename>Prelude.hi</filename> files for you.  If you'd
1282  rather it didn't, then give it a
1283  <option>-XNoImplicitPrelude</option> option.  The idea is
1284  that you can then import a Prelude of your own.  (But don't
1285  call it <literal>Prelude</literal>; the Haskell module
1286  namespace is flat, and you must not conflict with any
1287  Prelude module.)</para>
1288
1289             <para>Suppose you are importing a Prelude of your own
1290               in order to define your own numeric class
1291             hierarchy.  It completely defeats that purpose if the
1292             literal "1" means "<literal>Prelude.fromInteger
1293             1</literal>", which is what the Haskell Report specifies.
1294             So the <option>-XNoImplicitPrelude</option> 
1295               flag <emphasis>also</emphasis> causes
1296             the following pieces of built-in syntax to refer to
1297             <emphasis>whatever is in scope</emphasis>, not the Prelude
1298             versions:
1299             <itemizedlist>
1300               <listitem>
1301                 <para>An integer literal <literal>368</literal> means
1302                 "<literal>fromInteger (368::Integer)</literal>", rather than
1303                 "<literal>Prelude.fromInteger (368::Integer)</literal>".
1304 </para> </listitem>         
1305
1306       <listitem><para>Fractional literals are handed in just the same way,
1307           except that the translation is 
1308               <literal>fromRational (3.68::Rational)</literal>.
1309 </para> </listitem>         
1310
1311           <listitem><para>The equality test in an overloaded numeric pattern
1312               uses whatever <literal>(==)</literal> is in scope.
1313 </para> </listitem>         
1314
1315           <listitem><para>The subtraction operation, and the
1316           greater-than-or-equal test, in <literal>n+k</literal> patterns
1317               use whatever <literal>(-)</literal> and <literal>(>=)</literal> are in scope.
1318               </para></listitem>
1319
1320               <listitem>
1321                 <para>Negation (e.g. "<literal>- (f x)</literal>")
1322                 means "<literal>negate (f x)</literal>", both in numeric
1323                 patterns, and expressions.
1324               </para></listitem>
1325
1326               <listitem>
1327           <para>"Do" notation is translated using whatever
1328               functions <literal>(>>=)</literal>,
1329               <literal>(>>)</literal>, and <literal>fail</literal>,
1330               are in scope (not the Prelude
1331               versions).  List comprehensions, mdo (<xref linkend="mdo-notation"/>), and parallel array
1332               comprehensions, are unaffected.  </para></listitem>
1333
1334               <listitem>
1335                 <para>Arrow
1336                 notation (see <xref linkend="arrow-notation"/>)
1337                 uses whatever <literal>arr</literal>,
1338                 <literal>(>>>)</literal>, <literal>first</literal>,
1339                 <literal>app</literal>, <literal>(|||)</literal> and
1340                 <literal>loop</literal> functions are in scope. But unlike the
1341                 other constructs, the types of these functions must match the
1342                 Prelude types very closely.  Details are in flux; if you want
1343                 to use this, ask!
1344               </para></listitem>
1345             </itemizedlist>
1346 In all cases (apart from arrow notation), the static semantics should be that of the desugared form,
1347 even if that is a little unexpected. For example, the 
1348 static semantics of the literal <literal>368</literal>
1349 is exactly that of <literal>fromInteger (368::Integer)</literal>; it's fine for
1350 <literal>fromInteger</literal> to have any of the types:
1351 <programlisting>
1352 fromInteger :: Integer -> Integer
1353 fromInteger :: forall a. Foo a => Integer -> a
1354 fromInteger :: Num a => a -> Integer
1355 fromInteger :: Integer -> Bool -> Bool
1356 </programlisting>
1357 </para>
1358                 
1359              <para>Be warned: this is an experimental facility, with
1360              fewer checks than usual.  Use <literal>-dcore-lint</literal>
1361              to typecheck the desugared program.  If Core Lint is happy
1362              you should be all right.</para>
1363
1364 </sect2>
1365
1366 <sect2 id="postfix-operators">
1367 <title>Postfix operators</title>
1368
1369 <para>
1370   The <option>-XPostfixOperators</option> flag enables a small
1371 extension to the syntax of left operator sections, which allows you to
1372 define postfix operators.  The extension is this: the left section
1373 <programlisting>
1374   (e !)
1375 </programlisting>
1376 is equivalent (from the point of view of both type checking and execution) to the expression
1377 <programlisting>
1378   ((!) e)
1379 </programlisting>
1380 (for any expression <literal>e</literal> and operator <literal>(!)</literal>.
1381 The strict Haskell 98 interpretation is that the section is equivalent to
1382 <programlisting>
1383   (\y -> (!) e y)
1384 </programlisting>
1385 That is, the operator must be a function of two arguments.  GHC allows it to
1386 take only one argument, and that in turn allows you to write the function
1387 postfix.
1388 </para>
1389 <para>The extension does not extend to the left-hand side of function
1390 definitions; you must define such a function in prefix form.</para>
1391
1392 </sect2>
1393
1394 <sect2 id="tuple-sections">
1395 <title>Tuple sections</title>
1396
1397 <para>
1398   The <option>-XTupleSections</option> flag enables Python-style partially applied
1399   tuple constructors. For example, the following program
1400 <programlisting>
1401   (, True)
1402 </programlisting>
1403   is considered to be an alternative notation for the more unwieldy alternative
1404 <programlisting>
1405   \x -> (x, True)
1406 </programlisting>
1407 You can omit any combination of arguments to the tuple, as in the following
1408 <programlisting>
1409   (, "I", , , "Love", , 1337)
1410 </programlisting>
1411 which translates to
1412 <programlisting>
1413   \a b c d -> (a, "I", b, c, "Love", d, 1337)
1414 </programlisting>
1415 </para>
1416
1417 <para>
1418   If you have <link linkend="unboxed-tuples">unboxed tuples</link> enabled, tuple sections
1419   will also be available for them, like so
1420 <programlisting>
1421   (# , True #)
1422 </programlisting>
1423 Because there is no unboxed unit tuple, the following expression
1424 <programlisting>
1425   (# #)
1426 </programlisting>
1427 continues to stand for the unboxed singleton tuple data constructor.
1428 </para>
1429
1430 </sect2>
1431
1432 <sect2 id="disambiguate-fields">
1433 <title>Record field disambiguation</title>
1434 <para>
1435 In record construction and record pattern matching
1436 it is entirely unambiguous which field is referred to, even if there are two different
1437 data types in scope with a common field name.  For example:
1438 <programlisting>
1439 module M where
1440   data S = MkS { x :: Int, y :: Bool }
1441
1442 module Foo where
1443   import M
1444
1445   data T = MkT { x :: Int }
1446   
1447   ok1 (MkS { x = n }) = n+1   -- Unambiguous
1448   ok2 n = MkT { x = n+1 }     -- Unambiguous
1449
1450   bad1 k = k { x = 3 }  -- Ambiguous
1451   bad2 k = x k          -- Ambiguous
1452 </programlisting>
1453 Even though there are two <literal>x</literal>'s in scope,
1454 it is clear that the <literal>x</literal> in the pattern in the
1455 definition of <literal>ok1</literal> can only mean the field
1456 <literal>x</literal> from type <literal>S</literal>. Similarly for
1457 the function <literal>ok2</literal>.  However, in the record update
1458 in <literal>bad1</literal> and the record selection in <literal>bad2</literal>
1459 it is not clear which of the two types is intended.
1460 </para>
1461 <para>
1462 Haskell 98 regards all four as ambiguous, but with the
1463 <option>-XDisambiguateRecordFields</option> flag, GHC will accept
1464 the former two.  The rules are precisely the same as those for instance
1465 declarations in Haskell 98, where the method names on the left-hand side 
1466 of the method bindings in an instance declaration refer unambiguously
1467 to the method of that class (provided they are in scope at all), even
1468 if there are other variables in scope with the same name.
1469 This reduces the clutter of qualified names when you import two
1470 records from different modules that use the same field name.
1471 </para>
1472 <para>
1473 Some details:
1474 <itemizedlist>
1475 <listitem><para>
1476 Field disambiguation can be combined with punning (see <xref linkend="record-puns"/>). For exampe:
1477 <programlisting>
1478 module Foo where
1479   import M
1480   x=True
1481   ok3 (MkS { x }) = x+1   -- Uses both disambiguation and punning
1482 </programlisting>
1483 </para></listitem>
1484
1485 <listitem><para>
1486 With <option>-XDisambiguateRecordFields</option> you can use <emphasis>unqualifed</emphasis>
1487 field names even if the correponding selector is only in scope <emphasis>qualified</emphasis>
1488 For example, assuming the same module <literal>M</literal> as in our earlier example, this is legal:
1489 <programlisting>
1490 module Foo where
1491   import qualified M    -- Note qualified
1492
1493   ok4 (M.MkS { x = n }) = n+1   -- Unambiguous
1494 </programlisting>
1495 Since the constructore <literal>MkS</literal> is only in scope qualified, you must
1496 name it <literal>M.MkS</literal>, but the field <literal>x</literal> does not need
1497 to be qualified even though <literal>M.x</literal> is in scope but <literal>x</literal>
1498 is not.  (In effect, it is qualified by the constructor.)
1499 </para></listitem>
1500 </itemizedlist>
1501 </para>
1502
1503 </sect2>
1504
1505     <!-- ===================== Record puns ===================  -->
1506
1507 <sect2 id="record-puns">
1508 <title>Record puns
1509 </title>
1510
1511 <para>
1512 Record puns are enabled by the flag <literal>-XNamedFieldPuns</literal>.
1513 </para>
1514
1515 <para>
1516 When using records, it is common to write a pattern that binds a
1517 variable with the same name as a record field, such as:
1518
1519 <programlisting>
1520 data C = C {a :: Int}
1521 f (C {a = a}) = a
1522 </programlisting>
1523 </para>
1524
1525 <para>
1526 Record punning permits the variable name to be elided, so one can simply
1527 write
1528
1529 <programlisting>
1530 f (C {a}) = a
1531 </programlisting>
1532
1533 to mean the same pattern as above.  That is, in a record pattern, the
1534 pattern <literal>a</literal> expands into the pattern <literal>a =
1535 a</literal> for the same name <literal>a</literal>.  
1536 </para>
1537
1538 <para>
1539 Note that:
1540 <itemizedlist>
1541 <listitem><para>
1542 Record punning can also be used in an expression, writing, for example,
1543 <programlisting>
1544 let a = 1 in C {a}
1545 </programlisting>
1546 instead of 
1547 <programlisting>
1548 let a = 1 in C {a = a}
1549 </programlisting>
1550 The expansion is purely syntactic, so the expanded right-hand side
1551 expression refers to the nearest enclosing variable that is spelled the
1552 same as the field name.
1553 </para></listitem>
1554
1555 <listitem><para>
1556 Puns and other patterns can be mixed in the same record:
1557 <programlisting>
1558 data C = C {a :: Int, b :: Int}
1559 f (C {a, b = 4}) = a
1560 </programlisting>
1561 </para></listitem>
1562
1563 <listitem><para>
1564 Puns can be used wherever record patterns occur (e.g. in
1565 <literal>let</literal> bindings or at the top-level).  
1566 </para></listitem>
1567
1568 <listitem><para>
1569 A pun on a qualified field name is expanded by stripping off the module qualifier.
1570 For example:
1571 <programlisting>
1572 f (C {M.a}) = a
1573 </programlisting>
1574 means
1575 <programlisting>
1576 f (M.C {M.a = a}) = a
1577 </programlisting>
1578 (This is useful if the field selector <literal>a</literal> for constructor <literal>M.C</literal>
1579 is only in scope in qualified form.)
1580 </para></listitem>
1581 </itemizedlist>
1582 </para>
1583
1584
1585 </sect2>
1586
1587     <!-- ===================== Record wildcards ===================  -->
1588
1589 <sect2 id="record-wildcards">
1590 <title>Record wildcards
1591 </title>
1592
1593 <para>
1594 Record wildcards are enabled by the flag <literal>-XRecordWildCards</literal>.
1595 This flag implies <literal>-XDisambiguateRecordFields</literal>.
1596 </para>
1597
1598 <para>
1599 For records with many fields, it can be tiresome to write out each field
1600 individually in a record pattern, as in
1601 <programlisting>
1602 data C = C {a :: Int, b :: Int, c :: Int, d :: Int}
1603 f (C {a = 1, b = b, c = c, d = d}) = b + c + d
1604 </programlisting>
1605 </para>
1606
1607 <para>
1608 Record wildcard syntax permits a "<literal>..</literal>" in a record
1609 pattern, where each elided field <literal>f</literal> is replaced by the
1610 pattern <literal>f = f</literal>.  For example, the above pattern can be
1611 written as
1612 <programlisting>
1613 f (C {a = 1, ..}) = b + c + d
1614 </programlisting>
1615 </para>
1616
1617 <para>
1618 More details:
1619 <itemizedlist>
1620 <listitem><para>
1621 Wildcards can be mixed with other patterns, including puns
1622 (<xref linkend="record-puns"/>); for example, in a pattern <literal>C {a
1623 = 1, b, ..})</literal>.  Additionally, record wildcards can be used
1624 wherever record patterns occur, including in <literal>let</literal>
1625 bindings and at the top-level.  For example, the top-level binding
1626 <programlisting>
1627 C {a = 1, ..} = e
1628 </programlisting>
1629 defines <literal>b</literal>, <literal>c</literal>, and
1630 <literal>d</literal>.
1631 </para></listitem>
1632
1633 <listitem><para>
1634 Record wildcards can also be used in expressions, writing, for example,
1635 <programlisting>
1636 let {a = 1; b = 2; c = 3; d = 4} in C {..}
1637 </programlisting>
1638 in place of
1639 <programlisting>
1640 let {a = 1; b = 2; c = 3; d = 4} in C {a=a, b=b, c=c, d=d}
1641 </programlisting>
1642 The expansion is purely syntactic, so the record wildcard
1643 expression refers to the nearest enclosing variables that are spelled
1644 the same as the omitted field names.
1645 </para></listitem>
1646
1647 <listitem><para>
1648 The "<literal>..</literal>" expands to the missing 
1649 <emphasis>in-scope</emphasis> record fields, where "in scope"
1650 includes both unqualified and qualified-only.  
1651 Any fields that are not in scope are not filled in.  For example
1652 <programlisting>
1653 module M where
1654   data R = R { a,b,c :: Int }
1655 module X where
1656   import qualified M( R(a,b) )
1657   f a b = R { .. }
1658 </programlisting>
1659 The <literal>{..}</literal> expands to <literal>{M.a=a,M.b=b}</literal>,
1660 omitting <literal>c</literal> since it is not in scope at all.
1661 </para></listitem>
1662 </itemizedlist>
1663 </para>
1664
1665 </sect2>
1666
1667     <!-- ===================== Local fixity declarations ===================  -->
1668
1669 <sect2 id="local-fixity-declarations">
1670 <title>Local Fixity Declarations
1671 </title>
1672
1673 <para>A careful reading of the Haskell 98 Report reveals that fixity
1674 declarations (<literal>infix</literal>, <literal>infixl</literal>, and
1675 <literal>infixr</literal>) are permitted to appear inside local bindings
1676 such those introduced by <literal>let</literal> and
1677 <literal>where</literal>.  However, the Haskell Report does not specify
1678 the semantics of such bindings very precisely.
1679 </para>
1680
1681 <para>In GHC, a fixity declaration may accompany a local binding:
1682 <programlisting>
1683 let f = ...
1684     infixr 3 `f`
1685 in 
1686     ...
1687 </programlisting>
1688 and the fixity declaration applies wherever the binding is in scope.
1689 For example, in a <literal>let</literal>, it applies in the right-hand
1690 sides of other <literal>let</literal>-bindings and the body of the
1691 <literal>let</literal>C. Or, in recursive <literal>do</literal>
1692 expressions (<xref linkend="recursive-do-notation"/>), the local fixity
1693 declarations of a <literal>let</literal> statement scope over other
1694 statements in the group, just as the bound name does.
1695 </para>
1696
1697 <para>
1698 Moreover, a local fixity declaration *must* accompany a local binding of
1699 that name: it is not possible to revise the fixity of name bound
1700 elsewhere, as in
1701 <programlisting>
1702 let infixr 9 $ in ...
1703 </programlisting>
1704
1705 Because local fixity declarations are technically Haskell 98, no flag is
1706 necessary to enable them.
1707 </para>
1708 </sect2>
1709
1710 <sect2 id="package-imports">
1711   <title>Package-qualified imports</title>
1712
1713   <para>With the <option>-XPackageImports</option> flag, GHC allows
1714   import declarations to be qualified by the package name that the
1715     module is intended to be imported from.  For example:</para>
1716
1717 <programlisting>
1718 import "network" Network.Socket
1719 </programlisting>
1720   
1721   <para>would import the module <literal>Network.Socket</literal> from
1722     the package <literal>network</literal> (any version).  This may
1723     be used to disambiguate an import when the same module is
1724     available from multiple packages, or is present in both the
1725     current package being built and an external package.</para>
1726
1727   <para>Note: you probably don't need to use this feature, it was
1728     added mainly so that we can build backwards-compatible versions of
1729     packages when APIs change.  It can lead to fragile dependencies in
1730     the common case: modules occasionally move from one package to
1731     another, rendering any package-qualified imports broken.</para>
1732 </sect2>
1733
1734 <sect2 id="syntax-stolen">
1735 <title>Summary of stolen syntax</title>
1736
1737     <para>Turning on an option that enables special syntax
1738     <emphasis>might</emphasis> cause working Haskell 98 code to fail
1739     to compile, perhaps because it uses a variable name which has
1740     become a reserved word.  This section lists the syntax that is
1741     "stolen" by language extensions.
1742      We use
1743     notation and nonterminal names from the Haskell 98 lexical syntax
1744     (see the Haskell 98 Report).  
1745     We only list syntax changes here that might affect
1746     existing working programs (i.e. "stolen" syntax).  Many of these
1747     extensions will also enable new context-free syntax, but in all
1748     cases programs written to use the new syntax would not be
1749     compilable without the option enabled.</para>
1750
1751 <para>There are two classes of special
1752     syntax:
1753
1754     <itemizedlist>
1755       <listitem>
1756         <para>New reserved words and symbols: character sequences
1757         which are no longer available for use as identifiers in the
1758         program.</para>
1759       </listitem>
1760       <listitem>
1761         <para>Other special syntax: sequences of characters that have
1762         a different meaning when this particular option is turned
1763         on.</para>
1764       </listitem>
1765     </itemizedlist>
1766     
1767 The following syntax is stolen:
1768
1769     <variablelist>
1770       <varlistentry>
1771         <term>
1772           <literal>forall</literal>
1773           <indexterm><primary><literal>forall</literal></primary></indexterm>
1774         </term>
1775         <listitem><para>
1776         Stolen (in types) by: <option>-XExplicitForAll</option>, and hence by
1777             <option>-XScopedTypeVariables</option>,
1778             <option>-XLiberalTypeSynonyms</option>,
1779             <option>-XRank2Types</option>,
1780             <option>-XRankNTypes</option>,
1781             <option>-XPolymorphicComponents</option>,
1782             <option>-XExistentialQuantification</option>
1783           </para></listitem>
1784       </varlistentry>
1785
1786       <varlistentry>
1787         <term>
1788           <literal>mdo</literal>
1789           <indexterm><primary><literal>mdo</literal></primary></indexterm>
1790         </term>
1791         <listitem><para>
1792         Stolen by: <option>-XRecursiveDo</option>,
1793           </para></listitem>
1794       </varlistentry>
1795
1796       <varlistentry>
1797         <term>
1798           <literal>foreign</literal>
1799           <indexterm><primary><literal>foreign</literal></primary></indexterm>
1800         </term>
1801         <listitem><para>
1802         Stolen by: <option>-XForeignFunctionInterface</option>,
1803           </para></listitem>
1804       </varlistentry>
1805
1806       <varlistentry>
1807         <term>
1808           <literal>rec</literal>,
1809           <literal>proc</literal>, <literal>-&lt;</literal>,
1810           <literal>&gt;-</literal>, <literal>-&lt;&lt;</literal>,
1811           <literal>&gt;&gt;-</literal>, and <literal>(|</literal>,
1812           <literal>|)</literal> brackets
1813           <indexterm><primary><literal>proc</literal></primary></indexterm>
1814         </term>
1815         <listitem><para>
1816         Stolen by: <option>-XArrows</option>,
1817           </para></listitem>
1818       </varlistentry>
1819
1820       <varlistentry>
1821         <term>
1822           <literal>?<replaceable>varid</replaceable></literal>,
1823           <literal>%<replaceable>varid</replaceable></literal>
1824           <indexterm><primary>implicit parameters</primary></indexterm>
1825         </term>
1826         <listitem><para>
1827         Stolen by: <option>-XImplicitParams</option>,
1828           </para></listitem>
1829       </varlistentry>
1830
1831       <varlistentry>
1832         <term>
1833           <literal>[|</literal>,
1834           <literal>[e|</literal>, <literal>[p|</literal>,
1835           <literal>[d|</literal>, <literal>[t|</literal>,
1836           <literal>$(</literal>,
1837           <literal>$<replaceable>varid</replaceable></literal>
1838           <indexterm><primary>Template Haskell</primary></indexterm>
1839         </term>
1840         <listitem><para>
1841         Stolen by: <option>-XTemplateHaskell</option>,
1842           </para></listitem>
1843       </varlistentry>
1844
1845       <varlistentry>
1846         <term>
1847           <literal>[:<replaceable>varid</replaceable>|</literal>
1848           <indexterm><primary>quasi-quotation</primary></indexterm>
1849         </term>
1850         <listitem><para>
1851         Stolen by: <option>-XQuasiQuotes</option>,
1852           </para></listitem>
1853       </varlistentry>
1854
1855       <varlistentry>
1856         <term>
1857               <replaceable>varid</replaceable>{<literal>&num;</literal>},
1858               <replaceable>char</replaceable><literal>&num;</literal>,      
1859               <replaceable>string</replaceable><literal>&num;</literal>,    
1860               <replaceable>integer</replaceable><literal>&num;</literal>,    
1861               <replaceable>float</replaceable><literal>&num;</literal>,    
1862               <replaceable>float</replaceable><literal>&num;&num;</literal>,    
1863               <literal>(&num;</literal>, <literal>&num;)</literal>,         
1864         </term>
1865         <listitem><para>
1866         Stolen by: <option>-XMagicHash</option>,
1867           </para></listitem>
1868       </varlistentry>
1869     </variablelist>
1870 </para>
1871 </sect2>
1872 </sect1>
1873
1874
1875 <!-- TYPE SYSTEM EXTENSIONS -->
1876 <sect1 id="data-type-extensions">
1877 <title>Extensions to data types and type synonyms</title>
1878
1879 <sect2 id="nullary-types">
1880 <title>Data types with no constructors</title>
1881
1882 <para>With the <option>-fglasgow-exts</option> flag, GHC lets you declare
1883 a data type with no constructors.  For example:</para>
1884
1885 <programlisting>
1886   data S      -- S :: *
1887   data T a    -- T :: * -> *
1888 </programlisting>
1889
1890 <para>Syntactically, the declaration lacks the "= constrs" part.  The 
1891 type can be parameterised over types of any kind, but if the kind is
1892 not <literal>*</literal> then an explicit kind annotation must be used
1893 (see <xref linkend="kinding"/>).</para>
1894
1895 <para>Such data types have only one value, namely bottom.
1896 Nevertheless, they can be useful when defining "phantom types".</para>
1897 </sect2>
1898
1899 <sect2 id="infix-tycons">
1900 <title>Infix type constructors, classes, and type variables</title>
1901
1902 <para>
1903 GHC allows type constructors, classes, and type variables to be operators, and
1904 to be written infix, very much like expressions.  More specifically:
1905 <itemizedlist>
1906 <listitem><para>
1907   A type constructor or class can be an operator, beginning with a colon; e.g. <literal>:*:</literal>.
1908   The lexical syntax is the same as that for data constructors.
1909   </para></listitem>
1910 <listitem><para>
1911   Data type and type-synonym declarations can be written infix, parenthesised
1912   if you want further arguments.  E.g.
1913 <screen>
1914   data a :*: b = Foo a b
1915   type a :+: b = Either a b
1916   class a :=: b where ...
1917
1918   data (a :**: b) x = Baz a b x
1919   type (a :++: b) y = Either (a,b) y
1920 </screen>
1921   </para></listitem>
1922 <listitem><para>
1923   Types, and class constraints, can be written infix.  For example
1924   <screen>
1925         x :: Int :*: Bool
1926         f :: (a :=: b) => a -> b
1927   </screen>
1928   </para></listitem>
1929 <listitem><para>
1930   A type variable can be an (unqualified) operator e.g. <literal>+</literal>.
1931   The lexical syntax is the same as that for variable operators, excluding "(.)",
1932   "(!)", and "(*)".  In a binding position, the operator must be
1933   parenthesised.  For example:
1934 <programlisting>
1935    type T (+) = Int + Int
1936    f :: T Either
1937    f = Left 3
1938  
1939    liftA2 :: Arrow (~>)
1940           => (a -> b -> c) -> (e ~> a) -> (e ~> b) -> (e ~> c)
1941    liftA2 = ...
1942 </programlisting>
1943   </para></listitem>
1944 <listitem><para>
1945   Back-quotes work
1946   as for expressions, both for type constructors and type variables;  e.g. <literal>Int `Either` Bool</literal>, or
1947   <literal>Int `a` Bool</literal>.  Similarly, parentheses work the same; e.g.  <literal>(:*:) Int Bool</literal>.
1948   </para></listitem>
1949 <listitem><para>
1950   Fixities may be declared for type constructors, or classes, just as for data constructors.  However,
1951   one cannot distinguish between the two in a fixity declaration; a fixity declaration
1952   sets the fixity for a data constructor and the corresponding type constructor.  For example:
1953 <screen>
1954   infixl 7 T, :*:
1955 </screen>
1956   sets the fixity for both type constructor <literal>T</literal> and data constructor <literal>T</literal>,
1957   and similarly for <literal>:*:</literal>.
1958   <literal>Int `a` Bool</literal>.
1959   </para></listitem>
1960 <listitem><para>
1961   Function arrow is <literal>infixr</literal> with fixity 0.  (This might change; I'm not sure what it should be.)
1962   </para></listitem>
1963
1964 </itemizedlist>
1965 </para>
1966 </sect2>
1967
1968 <sect2 id="type-synonyms">
1969 <title>Liberalised type synonyms</title>
1970
1971 <para>
1972 Type synonyms are like macros at the type level, but Haskell 98 imposes many rules
1973 on individual synonym declarations.
1974 With the <option>-XLiberalTypeSynonyms</option> extension,
1975 GHC does validity checking on types <emphasis>only after expanding type synonyms</emphasis>.
1976 That means that GHC can be very much more liberal about type synonyms than Haskell 98. 
1977
1978 <itemizedlist>
1979 <listitem> <para>You can write a <literal>forall</literal> (including overloading)
1980 in a type synonym, thus:
1981 <programlisting>
1982   type Discard a = forall b. Show b => a -> b -> (a, String)
1983
1984   f :: Discard a
1985   f x y = (x, show y)
1986
1987   g :: Discard Int -> (Int,String)    -- A rank-2 type
1988   g f = f 3 True
1989 </programlisting>
1990 </para>
1991 </listitem>
1992
1993 <listitem><para>
1994 If you also use <option>-XUnboxedTuples</option>, 
1995 you can write an unboxed tuple in a type synonym:
1996 <programlisting>
1997   type Pr = (# Int, Int #)
1998
1999   h :: Int -> Pr
2000   h x = (# x, x #)
2001 </programlisting>
2002 </para></listitem>
2003
2004 <listitem><para>
2005 You can apply a type synonym to a forall type:
2006 <programlisting>
2007   type Foo a = a -> a -> Bool
2008  
2009   f :: Foo (forall b. b->b)
2010 </programlisting>
2011 After expanding the synonym, <literal>f</literal> has the legal (in GHC) type:
2012 <programlisting>
2013   f :: (forall b. b->b) -> (forall b. b->b) -> Bool
2014 </programlisting>
2015 </para></listitem>
2016
2017 <listitem><para>
2018 You can apply a type synonym to a partially applied type synonym:
2019 <programlisting>
2020   type Generic i o = forall x. i x -> o x
2021   type Id x = x
2022   
2023   foo :: Generic Id []
2024 </programlisting>
2025 After expanding the synonym, <literal>foo</literal> has the legal (in GHC) type:
2026 <programlisting>
2027   foo :: forall x. x -> [x]
2028 </programlisting>
2029 </para></listitem>
2030
2031 </itemizedlist>
2032 </para>
2033
2034 <para>
2035 GHC currently does kind checking before expanding synonyms (though even that
2036 could be changed.)
2037 </para>
2038 <para>
2039 After expanding type synonyms, GHC does validity checking on types, looking for
2040 the following mal-formedness which isn't detected simply by kind checking:
2041 <itemizedlist>
2042 <listitem><para>
2043 Type constructor applied to a type involving for-alls.
2044 </para></listitem>
2045 <listitem><para>
2046 Unboxed tuple on left of an arrow.
2047 </para></listitem>
2048 <listitem><para>
2049 Partially-applied type synonym.
2050 </para></listitem>
2051 </itemizedlist>
2052 So, for example,
2053 this will be rejected:
2054 <programlisting>
2055   type Pr = (# Int, Int #)
2056
2057   h :: Pr -> Int
2058   h x = ...
2059 </programlisting>
2060 because GHC does not allow  unboxed tuples on the left of a function arrow.
2061 </para>
2062 </sect2>
2063
2064
2065 <sect2 id="existential-quantification">
2066 <title>Existentially quantified data constructors
2067 </title>
2068
2069 <para>
2070 The idea of using existential quantification in data type declarations
2071 was suggested by Perry, and implemented in Hope+ (Nigel Perry, <emphasis>The Implementation
2072 of Practical Functional Programming Languages</emphasis>, PhD Thesis, University of
2073 London, 1991). It was later formalised by Laufer and Odersky
2074 (<emphasis>Polymorphic type inference and abstract data types</emphasis>,
2075 TOPLAS, 16(5), pp1411-1430, 1994).
2076 It's been in Lennart
2077 Augustsson's <command>hbc</command> Haskell compiler for several years, and
2078 proved very useful.  Here's the idea.  Consider the declaration:
2079 </para>
2080
2081 <para>
2082
2083 <programlisting>
2084   data Foo = forall a. MkFoo a (a -> Bool)
2085            | Nil
2086 </programlisting>
2087
2088 </para>
2089
2090 <para>
2091 The data type <literal>Foo</literal> has two constructors with types:
2092 </para>
2093
2094 <para>
2095
2096 <programlisting>
2097   MkFoo :: forall a. a -> (a -> Bool) -> Foo
2098   Nil   :: Foo
2099 </programlisting>
2100
2101 </para>
2102
2103 <para>
2104 Notice that the type variable <literal>a</literal> in the type of <function>MkFoo</function>
2105 does not appear in the data type itself, which is plain <literal>Foo</literal>.
2106 For example, the following expression is fine:
2107 </para>
2108
2109 <para>
2110
2111 <programlisting>
2112   [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]
2113 </programlisting>
2114
2115 </para>
2116
2117 <para>
2118 Here, <literal>(MkFoo 3 even)</literal> packages an integer with a function
2119 <function>even</function> that maps an integer to <literal>Bool</literal>; and <function>MkFoo 'c'
2120 isUpper</function> packages a character with a compatible function.  These
2121 two things are each of type <literal>Foo</literal> and can be put in a list.
2122 </para>
2123
2124 <para>
2125 What can we do with a value of type <literal>Foo</literal>?.  In particular,
2126 what happens when we pattern-match on <function>MkFoo</function>?
2127 </para>
2128
2129 <para>
2130
2131 <programlisting>
2132   f (MkFoo val fn) = ???
2133 </programlisting>
2134
2135 </para>
2136
2137 <para>
2138 Since all we know about <literal>val</literal> and <function>fn</function> is that they
2139 are compatible, the only (useful) thing we can do with them is to
2140 apply <function>fn</function> to <literal>val</literal> to get a boolean.  For example:
2141 </para>
2142
2143 <para>
2144
2145 <programlisting>
2146   f :: Foo -> Bool
2147   f (MkFoo val fn) = fn val
2148 </programlisting>
2149
2150 </para>
2151
2152 <para>
2153 What this allows us to do is to package heterogeneous values
2154 together with a bunch of functions that manipulate them, and then treat
2155 that collection of packages in a uniform manner.  You can express
2156 quite a bit of object-oriented-like programming this way.
2157 </para>
2158
2159 <sect3 id="existential">
2160 <title>Why existential?
2161 </title>
2162
2163 <para>
2164 What has this to do with <emphasis>existential</emphasis> quantification?
2165 Simply that <function>MkFoo</function> has the (nearly) isomorphic type
2166 </para>
2167
2168 <para>
2169
2170 <programlisting>
2171   MkFoo :: (exists a . (a, a -> Bool)) -> Foo
2172 </programlisting>
2173
2174 </para>
2175
2176 <para>
2177 But Haskell programmers can safely think of the ordinary
2178 <emphasis>universally</emphasis> quantified type given above, thereby avoiding
2179 adding a new existential quantification construct.
2180 </para>
2181
2182 </sect3>
2183
2184 <sect3 id="existential-with-context">
2185 <title>Existentials and type classes</title>
2186
2187 <para>
2188 An easy extension is to allow
2189 arbitrary contexts before the constructor.  For example:
2190 </para>
2191
2192 <para>
2193
2194 <programlisting>
2195 data Baz = forall a. Eq a => Baz1 a a
2196          | forall b. Show b => Baz2 b (b -> b)
2197 </programlisting>
2198
2199 </para>
2200
2201 <para>
2202 The two constructors have the types you'd expect:
2203 </para>
2204
2205 <para>
2206
2207 <programlisting>
2208 Baz1 :: forall a. Eq a => a -> a -> Baz
2209 Baz2 :: forall b. Show b => b -> (b -> b) -> Baz
2210 </programlisting>
2211
2212 </para>
2213
2214 <para>
2215 But when pattern matching on <function>Baz1</function> the matched values can be compared
2216 for equality, and when pattern matching on <function>Baz2</function> the first matched
2217 value can be converted to a string (as well as applying the function to it).
2218 So this program is legal:
2219 </para>
2220
2221 <para>
2222
2223 <programlisting>
2224   f :: Baz -> String
2225   f (Baz1 p q) | p == q    = "Yes"
2226                | otherwise = "No"
2227   f (Baz2 v fn)            = show (fn v)
2228 </programlisting>
2229
2230 </para>
2231
2232 <para>
2233 Operationally, in a dictionary-passing implementation, the
2234 constructors <function>Baz1</function> and <function>Baz2</function> must store the
2235 dictionaries for <literal>Eq</literal> and <literal>Show</literal> respectively, and
2236 extract it on pattern matching.
2237 </para>
2238
2239 </sect3>
2240
2241 <sect3 id="existential-records">
2242 <title>Record Constructors</title>
2243
2244 <para>
2245 GHC allows existentials to be used with records syntax as well.  For example:
2246
2247 <programlisting>
2248 data Counter a = forall self. NewCounter
2249     { _this    :: self
2250     , _inc     :: self -> self
2251     , _display :: self -> IO ()
2252     , tag      :: a
2253     }
2254 </programlisting>
2255 Here <literal>tag</literal> is a public field, with a well-typed selector
2256 function <literal>tag :: Counter a -> a</literal>.  The <literal>self</literal>
2257 type is hidden from the outside; any attempt to apply <literal>_this</literal>,
2258 <literal>_inc</literal> or <literal>_display</literal> as functions will raise a
2259 compile-time error.  In other words, <emphasis>GHC defines a record selector function
2260 only for fields whose type does not mention the existentially-quantified variables</emphasis>.
2261 (This example used an underscore in the fields for which record selectors
2262 will not be defined, but that is only programming style; GHC ignores them.)
2263 </para>
2264
2265 <para>
2266 To make use of these hidden fields, we need to create some helper functions:
2267
2268 <programlisting>
2269 inc :: Counter a -> Counter a
2270 inc (NewCounter x i d t) = NewCounter
2271     { _this = i x, _inc = i, _display = d, tag = t } 
2272
2273 display :: Counter a -> IO ()
2274 display NewCounter{ _this = x, _display = d } = d x
2275 </programlisting>
2276
2277 Now we can define counters with different underlying implementations:
2278
2279 <programlisting>
2280 counterA :: Counter String 
2281 counterA = NewCounter
2282     { _this = 0, _inc = (1+), _display = print, tag = "A" }
2283
2284 counterB :: Counter String 
2285 counterB = NewCounter
2286     { _this = "", _inc = ('#':), _display = putStrLn, tag = "B" }
2287
2288 main = do
2289     display (inc counterA)         -- prints "1"
2290     display (inc (inc counterB))   -- prints "##"
2291 </programlisting>
2292
2293 Record update syntax is supported for existentials (and GADTs):
2294 <programlisting>
2295 setTag :: Counter a -> a -> Counter a
2296 setTag obj t = obj{ tag = t }
2297 </programlisting>
2298 The rule for record update is this: <emphasis>
2299 the types of the updated fields may
2300 mention only the universally-quantified type variables
2301 of the data constructor.  For GADTs, the field may mention only types
2302 that appear as a simple type-variable argument in the constructor's result
2303 type</emphasis>.  For example:
2304 <programlisting>
2305 data T a b where { T1 { f1::a, f2::b, f3::(b,c) } :: T a b } -- c is existential
2306 upd1 t x = t { f1=x }   -- OK:   upd1 :: T a b -> a' -> T a' b
2307 upd2 t x = t { f3=x }   -- BAD   (f3's type mentions c, which is
2308                         --        existentially quantified)
2309
2310 data G a b where { G1 { g1::a, g2::c } :: G a [c] }
2311 upd3 g x = g { g1=x }   -- OK:   upd3 :: G a b -> c -> G c b
2312 upd4 g x = g { g2=x }   -- BAD (f2's type mentions c, which is not a simple
2313                         --      type-variable argument in G1's result type)
2314 </programlisting>
2315 </para>
2316
2317 </sect3>
2318
2319
2320 <sect3>
2321 <title>Restrictions</title>
2322
2323 <para>
2324 There are several restrictions on the ways in which existentially-quantified
2325 constructors can be use.
2326 </para>
2327
2328 <para>
2329
2330 <itemizedlist>
2331 <listitem>
2332
2333 <para>
2334  When pattern matching, each pattern match introduces a new,
2335 distinct, type for each existential type variable.  These types cannot
2336 be unified with any other type, nor can they escape from the scope of
2337 the pattern match.  For example, these fragments are incorrect:
2338
2339
2340 <programlisting>
2341 f1 (MkFoo a f) = a
2342 </programlisting>
2343
2344
2345 Here, the type bound by <function>MkFoo</function> "escapes", because <literal>a</literal>
2346 is the result of <function>f1</function>.  One way to see why this is wrong is to
2347 ask what type <function>f1</function> has:
2348
2349
2350 <programlisting>
2351   f1 :: Foo -> a             -- Weird!
2352 </programlisting>
2353
2354
2355 What is this "<literal>a</literal>" in the result type? Clearly we don't mean
2356 this:
2357
2358
2359 <programlisting>
2360   f1 :: forall a. Foo -> a   -- Wrong!
2361 </programlisting>
2362
2363
2364 The original program is just plain wrong.  Here's another sort of error
2365
2366
2367 <programlisting>
2368   f2 (Baz1 a b) (Baz1 p q) = a==q
2369 </programlisting>
2370
2371
2372 It's ok to say <literal>a==b</literal> or <literal>p==q</literal>, but
2373 <literal>a==q</literal> is wrong because it equates the two distinct types arising
2374 from the two <function>Baz1</function> constructors.
2375
2376
2377 </para>
2378 </listitem>
2379 <listitem>
2380
2381 <para>
2382 You can't pattern-match on an existentially quantified
2383 constructor in a <literal>let</literal> or <literal>where</literal> group of
2384 bindings. So this is illegal:
2385
2386
2387 <programlisting>
2388   f3 x = a==b where { Baz1 a b = x }
2389 </programlisting>
2390
2391 Instead, use a <literal>case</literal> expression:
2392
2393 <programlisting>
2394   f3 x = case x of Baz1 a b -> a==b
2395 </programlisting>
2396
2397 In general, you can only pattern-match
2398 on an existentially-quantified constructor in a <literal>case</literal> expression or
2399 in the patterns of a function definition.
2400
2401 The reason for this restriction is really an implementation one.
2402 Type-checking binding groups is already a nightmare without
2403 existentials complicating the picture.  Also an existential pattern
2404 binding at the top level of a module doesn't make sense, because it's
2405 not clear how to prevent the existentially-quantified type "escaping".
2406 So for now, there's a simple-to-state restriction.  We'll see how
2407 annoying it is.
2408
2409 </para>
2410 </listitem>
2411 <listitem>
2412
2413 <para>
2414 You can't use existential quantification for <literal>newtype</literal>
2415 declarations.  So this is illegal:
2416
2417
2418 <programlisting>
2419   newtype T = forall a. Ord a => MkT a
2420 </programlisting>
2421
2422
2423 Reason: a value of type <literal>T</literal> must be represented as a
2424 pair of a dictionary for <literal>Ord t</literal> and a value of type
2425 <literal>t</literal>.  That contradicts the idea that
2426 <literal>newtype</literal> should have no concrete representation.
2427 You can get just the same efficiency and effect by using
2428 <literal>data</literal> instead of <literal>newtype</literal>.  If
2429 there is no overloading involved, then there is more of a case for
2430 allowing an existentially-quantified <literal>newtype</literal>,
2431 because the <literal>data</literal> version does carry an
2432 implementation cost, but single-field existentially quantified
2433 constructors aren't much use.  So the simple restriction (no
2434 existential stuff on <literal>newtype</literal>) stands, unless there
2435 are convincing reasons to change it.
2436
2437
2438 </para>
2439 </listitem>
2440 <listitem>
2441
2442 <para>
2443  You can't use <literal>deriving</literal> to define instances of a
2444 data type with existentially quantified data constructors.
2445
2446 Reason: in most cases it would not make sense. For example:;
2447
2448 <programlisting>
2449 data T = forall a. MkT [a] deriving( Eq )
2450 </programlisting>
2451
2452 To derive <literal>Eq</literal> in the standard way we would need to have equality
2453 between the single component of two <function>MkT</function> constructors:
2454
2455 <programlisting>
2456 instance Eq T where
2457   (MkT a) == (MkT b) = ???
2458 </programlisting>
2459
2460 But <varname>a</varname> and <varname>b</varname> have distinct types, and so can't be compared.
2461 It's just about possible to imagine examples in which the derived instance
2462 would make sense, but it seems altogether simpler simply to prohibit such
2463 declarations.  Define your own instances!
2464 </para>
2465 </listitem>
2466
2467 </itemizedlist>
2468
2469 </para>
2470
2471 </sect3>
2472 </sect2>
2473
2474 <!-- ====================== Generalised algebraic data types =======================  -->
2475
2476 <sect2 id="gadt-style">
2477 <title>Declaring data types with explicit constructor signatures</title>
2478
2479 <para>GHC allows you to declare an algebraic data type by 
2480 giving the type signatures of constructors explicitly.  For example:
2481 <programlisting>
2482   data Maybe a where
2483       Nothing :: Maybe a
2484       Just    :: a -> Maybe a
2485 </programlisting>
2486 The form is called a "GADT-style declaration"
2487 because Generalised Algebraic Data Types, described in <xref linkend="gadt"/>, 
2488 can only be declared using this form.</para>
2489 <para>Notice that GADT-style syntax generalises existential types (<xref linkend="existential-quantification"/>).  
2490 For example, these two declarations are equivalent:
2491 <programlisting>
2492   data Foo = forall a. MkFoo a (a -> Bool)
2493   data Foo' where { MKFoo :: a -> (a->Bool) -> Foo' }
2494 </programlisting>
2495 </para>
2496 <para>Any data type that can be declared in standard Haskell-98 syntax 
2497 can also be declared using GADT-style syntax.
2498 The choice is largely stylistic, but GADT-style declarations differ in one important respect:
2499 they treat class constraints on the data constructors differently.
2500 Specifically, if the constructor is given a type-class context, that
2501 context is made available by pattern matching.  For example:
2502 <programlisting>
2503   data Set a where
2504     MkSet :: Eq a => [a] -> Set a
2505
2506   makeSet :: Eq a => [a] -> Set a
2507   makeSet xs = MkSet (nub xs)
2508
2509   insert :: a -> Set a -> Set a
2510   insert a (MkSet as) | a `elem` as = MkSet as
2511                       | otherwise   = MkSet (a:as)
2512 </programlisting>
2513 A use of <literal>MkSet</literal> as a constructor (e.g. in the definition of <literal>makeSet</literal>) 
2514 gives rise to a <literal>(Eq a)</literal>
2515 constraint, as you would expect.  The new feature is that pattern-matching on <literal>MkSet</literal>
2516 (as in the definition of <literal>insert</literal>) makes <emphasis>available</emphasis> an <literal>(Eq a)</literal>
2517 context.  In implementation terms, the <literal>MkSet</literal> constructor has a hidden field that stores
2518 the <literal>(Eq a)</literal> dictionary that is passed to <literal>MkSet</literal>; so
2519 when pattern-matching that dictionary becomes available for the right-hand side of the match.
2520 In the example, the equality dictionary is used to satisfy the equality constraint 
2521 generated by the call to <literal>elem</literal>, so that the type of
2522 <literal>insert</literal> itself has no <literal>Eq</literal> constraint.
2523 </para>
2524 <para>
2525 For example, one possible application is to reify dictionaries:
2526 <programlisting>
2527    data NumInst a where
2528      MkNumInst :: Num a => NumInst a
2529
2530    intInst :: NumInst Int
2531    intInst = MkNumInst
2532
2533    plus :: NumInst a -> a -> a -> a
2534    plus MkNumInst p q = p + q
2535 </programlisting>
2536 Here, a value of type <literal>NumInst a</literal> is equivalent 
2537 to an explicit <literal>(Num a)</literal> dictionary.
2538 </para>
2539 <para>
2540 All this applies to constructors declared using the syntax of <xref linkend="existential-with-context"/>.
2541 For example, the <literal>NumInst</literal> data type above could equivalently be declared 
2542 like this:
2543 <programlisting>
2544    data NumInst a 
2545       = Num a => MkNumInst (NumInst a)
2546 </programlisting>
2547 Notice that, unlike the situation when declaring an existential, there is 
2548 no <literal>forall</literal>, because the <literal>Num</literal> constrains the
2549 data type's universally quantified type variable <literal>a</literal>.  
2550 A constructor may have both universal and existential type variables: for example,
2551 the following two declarations are equivalent:
2552 <programlisting>
2553    data T1 a 
2554         = forall b. (Num a, Eq b) => MkT1 a b
2555    data T2 a where
2556         MkT2 :: (Num a, Eq b) => a -> b -> T2 a
2557 </programlisting>
2558 </para>
2559 <para>All this behaviour contrasts with Haskell 98's peculiar treatment of 
2560 contexts on a data type declaration (Section 4.2.1 of the Haskell 98 Report).
2561 In Haskell 98 the definition
2562 <programlisting>
2563   data Eq a => Set' a = MkSet' [a]
2564 </programlisting>
2565 gives <literal>MkSet'</literal> the same type as <literal>MkSet</literal> above.  But instead of 
2566 <emphasis>making available</emphasis> an <literal>(Eq a)</literal> constraint, pattern-matching
2567 on <literal>MkSet'</literal> <emphasis>requires</emphasis> an <literal>(Eq a)</literal> constraint!
2568 GHC faithfully implements this behaviour, odd though it is.  But for GADT-style declarations,
2569 GHC's behaviour is much more useful, as well as much more intuitive.
2570 </para>
2571
2572 <para>
2573 The rest of this section gives further details about GADT-style data
2574 type declarations.
2575
2576 <itemizedlist>
2577 <listitem><para>
2578 The result type of each data constructor must begin with the type constructor being defined.
2579 If the result type of all constructors 
2580 has the form <literal>T a1 ... an</literal>, where <literal>a1 ... an</literal>
2581 are distinct type variables, then the data type is <emphasis>ordinary</emphasis>;
2582 otherwise is a <emphasis>generalised</emphasis> data type (<xref linkend="gadt"/>).
2583 </para></listitem>
2584
2585 <listitem><para>
2586 As with other type signatures, you can give a single signature for several data constructors.
2587 In this example we give a single signature for <literal>T1</literal> and <literal>T2</literal>:
2588 <programlisting>
2589   data T a where
2590     T1,T2 :: a -> T a
2591     T3 :: T a
2592 </programlisting>
2593 </para></listitem>
2594
2595 <listitem><para>
2596 The type signature of
2597 each constructor is independent, and is implicitly universally quantified as usual. 
2598 In particular, the type variable(s) in the "<literal>data T a where</literal>" header 
2599 have no scope, and different constructors may have different universally-quantified type variables:
2600 <programlisting>
2601   data T a where        -- The 'a' has no scope
2602     T1,T2 :: b -> T b   -- Means forall b. b -> T b
2603     T3 :: T a           -- Means forall a. T a
2604 </programlisting>
2605 </para></listitem>
2606
2607 <listitem><para>
2608 A constructor signature may mention type class constraints, which can differ for
2609 different constructors.  For example, this is fine:
2610 <programlisting>
2611   data T a where
2612     T1 :: Eq b => b -> b -> T b
2613     T2 :: (Show c, Ix c) => c -> [c] -> T c
2614 </programlisting>
2615 When patten matching, these constraints are made available to discharge constraints
2616 in the body of the match. For example:
2617 <programlisting>
2618   f :: T a -> String
2619   f (T1 x y) | x==y      = "yes"
2620              | otherwise = "no"
2621   f (T2 a b)             = show a
2622 </programlisting>
2623 Note that <literal>f</literal> is not overloaded; the <literal>Eq</literal> constraint arising
2624 from the use of <literal>==</literal> is discharged by the pattern match on <literal>T1</literal>
2625 and similarly the <literal>Show</literal> constraint arising from the use of <literal>show</literal>.
2626 </para></listitem>
2627
2628 <listitem><para>
2629 Unlike a Haskell-98-style 
2630 data type declaration, the type variable(s) in the "<literal>data Set a where</literal>" header 
2631 have no scope.  Indeed, one can write a kind signature instead:
2632 <programlisting>
2633   data Set :: * -> * where ...
2634 </programlisting>
2635 or even a mixture of the two:
2636 <programlisting>
2637   data Bar a :: (* -> *) -> * where ...
2638 </programlisting>
2639 The type variables (if given) may be explicitly kinded, so we could also write the header for <literal>Foo</literal>
2640 like this:
2641 <programlisting>
2642   data Bar a (b :: * -> *) where ...
2643 </programlisting>
2644 </para></listitem>
2645
2646
2647 <listitem><para>
2648 You can use strictness annotations, in the obvious places
2649 in the constructor type:
2650 <programlisting>
2651   data Term a where
2652       Lit    :: !Int -> Term Int
2653       If     :: Term Bool -> !(Term a) -> !(Term a) -> Term a
2654       Pair   :: Term a -> Term b -> Term (a,b)
2655 </programlisting>
2656 </para></listitem>
2657
2658 <listitem><para>
2659 You can use a <literal>deriving</literal> clause on a GADT-style data type
2660 declaration.   For example, these two declarations are equivalent
2661 <programlisting>
2662   data Maybe1 a where {
2663       Nothing1 :: Maybe1 a ;
2664       Just1    :: a -> Maybe1 a
2665     } deriving( Eq, Ord )
2666
2667   data Maybe2 a = Nothing2 | Just2 a 
2668        deriving( Eq, Ord )
2669 </programlisting>
2670 </para></listitem>
2671
2672 <listitem><para>
2673 The type signature may have quantified type variables that do not appear
2674 in the result type:
2675 <programlisting>
2676   data Foo where
2677      MkFoo :: a -> (a->Bool) -> Foo
2678      Nil   :: Foo
2679 </programlisting>
2680 Here the type variable <literal>a</literal> does not appear in the result type
2681 of either constructor.  
2682 Although it is universally quantified in the type of the constructor, such
2683 a type variable is often called "existential".  
2684 Indeed, the above declaration declares precisely the same type as 
2685 the <literal>data Foo</literal> in <xref linkend="existential-quantification"/>.
2686 </para><para>
2687 The type may contain a class context too, of course:
2688 <programlisting>
2689   data Showable where
2690     MkShowable :: Show a => a -> Showable
2691 </programlisting>
2692 </para></listitem>
2693
2694 <listitem><para>
2695 You can use record syntax on a GADT-style data type declaration:
2696
2697 <programlisting>
2698   data Person where
2699       Adult :: { name :: String, children :: [Person] } -> Person
2700       Child :: Show a => { name :: !String, funny :: a } -> Person
2701 </programlisting>
2702 As usual, for every constructor that has a field <literal>f</literal>, the type of
2703 field <literal>f</literal> must be the same (modulo alpha conversion).
2704 The <literal>Child</literal> constructor above shows that the signature
2705 may have a context, existentially-quantified variables, and strictness annotations, 
2706 just as in the non-record case.  (NB: the "type" that follows the double-colon
2707 is not really a type, because of the record syntax and strictness annotations.
2708 A "type" of this form can appear only in a constructor signature.)
2709 </para></listitem>
2710
2711 <listitem><para> 
2712 Record updates are allowed with GADT-style declarations, 
2713 only fields that have the following property: the type of the field
2714 mentions no existential type variables.
2715 </para></listitem>
2716
2717 <listitem><para> 
2718 As in the case of existentials declared using the Haskell-98-like record syntax 
2719 (<xref linkend="existential-records"/>),
2720 record-selector functions are generated only for those fields that have well-typed
2721 selectors.  
2722 Here is the example of that section, in GADT-style syntax:
2723 <programlisting>
2724 data Counter a where
2725     NewCounter { _this    :: self
2726                , _inc     :: self -> self
2727                , _display :: self -> IO ()
2728                , tag      :: a
2729                }
2730         :: Counter a
2731 </programlisting>
2732 As before, only one selector function is generated here, that for <literal>tag</literal>.
2733 Nevertheless, you can still use all the field names in pattern matching and record construction.
2734 </para></listitem>
2735 </itemizedlist></para>
2736 </sect2>
2737
2738 <sect2 id="gadt">
2739 <title>Generalised Algebraic Data Types (GADTs)</title>
2740
2741 <para>Generalised Algebraic Data Types generalise ordinary algebraic data types 
2742 by allowing constructors to have richer return types.  Here is an example:
2743 <programlisting>
2744   data Term a where
2745       Lit    :: Int -> Term Int
2746       Succ   :: Term Int -> Term Int
2747       IsZero :: Term Int -> Term Bool   
2748       If     :: Term Bool -> Term a -> Term a -> Term a
2749       Pair   :: Term a -> Term b -> Term (a,b)
2750 </programlisting>
2751 Notice that the return type of the constructors is not always <literal>Term a</literal>, as is the
2752 case with ordinary data types.  This generality allows us to 
2753 write a well-typed <literal>eval</literal> function
2754 for these <literal>Terms</literal>:
2755 <programlisting>
2756   eval :: Term a -> a
2757   eval (Lit i)      = i
2758   eval (Succ t)     = 1 + eval t
2759   eval (IsZero t)   = eval t == 0
2760   eval (If b e1 e2) = if eval b then eval e1 else eval e2
2761   eval (Pair e1 e2) = (eval e1, eval e2)
2762 </programlisting>
2763 The key point about GADTs is that <emphasis>pattern matching causes type refinement</emphasis>.  
2764 For example, in the right hand side of the equation
2765 <programlisting>
2766   eval :: Term a -> a
2767   eval (Lit i) =  ...
2768 </programlisting>
2769 the type <literal>a</literal> is refined to <literal>Int</literal>.  That's the whole point!
2770 A precise specification of the type rules is beyond what this user manual aspires to, 
2771 but the design closely follows that described in
2772 the paper <ulink
2773 url="http://research.microsoft.com/%7Esimonpj/papers/gadt/">Simple
2774 unification-based type inference for GADTs</ulink>,
2775 (ICFP 2006).
2776 The general principle is this: <emphasis>type refinement is only carried out 
2777 based on user-supplied type annotations</emphasis>.
2778 So if no type signature is supplied for <literal>eval</literal>, no type refinement happens, 
2779 and lots of obscure error messages will
2780 occur.  However, the refinement is quite general.  For example, if we had:
2781 <programlisting>
2782   eval :: Term a -> a -> a
2783   eval (Lit i) j =  i+j
2784 </programlisting>
2785 the pattern match causes the type <literal>a</literal> to be refined to <literal>Int</literal> (because of the type
2786 of the constructor <literal>Lit</literal>), and that refinement also applies to the type of <literal>j</literal>, and
2787 the result type of the <literal>case</literal> expression.  Hence the addition <literal>i+j</literal> is legal.
2788 </para>
2789 <para>
2790 These and many other examples are given in papers by Hongwei Xi, and
2791 Tim Sheard. There is a longer introduction
2792 <ulink url="http://www.haskell.org/haskellwiki/GADT">on the wiki</ulink>,
2793 and Ralf Hinze's
2794 <ulink url="http://www.informatik.uni-bonn.de/~ralf/publications/With.pdf">Fun with phantom types</ulink> also has a number of examples. Note that papers
2795 may use different notation to that implemented in GHC.
2796 </para>
2797 <para>
2798 The rest of this section outlines the extensions to GHC that support GADTs.   The extension is enabled with 
2799 <option>-XGADTs</option>.  The <option>-XGADTs</option> flag also sets <option>-XRelaxedPolyRec</option>.
2800 <itemizedlist>
2801 <listitem><para>
2802 A GADT can only be declared using GADT-style syntax (<xref linkend="gadt-style"/>); 
2803 the old Haskell-98 syntax for data declarations always declares an ordinary data type.
2804 The result type of each constructor must begin with the type constructor being defined,
2805 but for a GADT the arguments to the type constructor can be arbitrary monotypes.  
2806 For example, in the <literal>Term</literal> data
2807 type above, the type of each constructor must end with <literal>Term ty</literal>, but
2808 the <literal>ty</literal> need not be a type variable (e.g. the <literal>Lit</literal>
2809 constructor).
2810 </para></listitem>
2811
2812 <listitem><para>
2813 It is permitted to declare an ordinary algebraic data type using GADT-style syntax.
2814 What makes a GADT into a GADT is not the syntax, but rather the presence of data constructors
2815 whose result type is not just <literal>T a b</literal>.
2816 </para></listitem>
2817
2818 <listitem><para>
2819 You cannot use a <literal>deriving</literal> clause for a GADT; only for
2820 an ordinary data type.
2821 </para></listitem>
2822
2823 <listitem><para>
2824 As mentioned in <xref linkend="gadt-style"/>, record syntax is supported.
2825 For example:
2826 <programlisting>
2827   data Term a where
2828       Lit    { val  :: Int }      :: Term Int
2829       Succ   { num  :: Term Int } :: Term Int
2830       Pred   { num  :: Term Int } :: Term Int
2831       IsZero { arg  :: Term Int } :: Term Bool  
2832       Pair   { arg1 :: Term a
2833              , arg2 :: Term b
2834              }                    :: Term (a,b)
2835       If     { cnd  :: Term Bool
2836              , tru  :: Term a
2837              , fls  :: Term a
2838              }                    :: Term a
2839 </programlisting>
2840 However, for GADTs there is the following additional constraint: 
2841 every constructor that has a field <literal>f</literal> must have
2842 the same result type (modulo alpha conversion)
2843 Hence, in the above example, we cannot merge the <literal>num</literal> 
2844 and <literal>arg</literal> fields above into a 
2845 single name.  Although their field types are both <literal>Term Int</literal>,
2846 their selector functions actually have different types:
2847
2848 <programlisting>
2849   num :: Term Int -> Term Int
2850   arg :: Term Bool -> Term Int
2851 </programlisting>
2852 </para></listitem>
2853
2854 <listitem><para>
2855 When pattern-matching against data constructors drawn from a GADT, 
2856 for example in a <literal>case</literal> expression, the following rules apply:
2857 <itemizedlist>
2858 <listitem><para>The type of the scrutinee must be rigid.</para></listitem>
2859 <listitem><para>The type of the entire <literal>case</literal> expression must be rigid.</para></listitem>
2860 <listitem><para>The type of any free variable mentioned in any of
2861 the <literal>case</literal> alternatives must be rigid.</para></listitem>
2862 </itemizedlist>
2863 A type is "rigid" if it is completely known to the compiler at its binding site.  The easiest
2864 way to ensure that a variable a rigid type is to give it a type signature.
2865 For more precise details see <ulink url="http://research.microsoft.com/%7Esimonpj/papers/gadt">
2866 Simple unification-based type inference for GADTs
2867 </ulink>. The criteria implemented by GHC are given in the Appendix.
2868
2869 </para></listitem>
2870
2871 </itemizedlist>
2872 </para>
2873
2874 </sect2>
2875 </sect1>
2876
2877 <!-- ====================== End of Generalised algebraic data types =======================  -->
2878
2879 <sect1 id="deriving">
2880 <title>Extensions to the "deriving" mechanism</title>
2881
2882 <sect2 id="deriving-inferred">
2883 <title>Inferred context for deriving clauses</title>
2884
2885 <para>
2886 The Haskell Report is vague about exactly when a <literal>deriving</literal> clause is
2887 legal.  For example:
2888 <programlisting>
2889   data T0 f a = MkT0 a         deriving( Eq )
2890   data T1 f a = MkT1 (f a)     deriving( Eq )
2891   data T2 f a = MkT2 (f (f a)) deriving( Eq )
2892 </programlisting>
2893 The natural generated <literal>Eq</literal> code would result in these instance declarations:
2894 <programlisting>
2895   instance Eq a         => Eq (T0 f a) where ...
2896   instance Eq (f a)     => Eq (T1 f a) where ...
2897   instance Eq (f (f a)) => Eq (T2 f a) where ...
2898 </programlisting>
2899 The first of these is obviously fine. The second is still fine, although less obviously. 
2900 The third is not Haskell 98, and risks losing termination of instances.
2901 </para>
2902 <para>
2903 GHC takes a conservative position: it accepts the first two, but not the third.  The  rule is this:
2904 each constraint in the inferred instance context must consist only of type variables, 
2905 with no repetitions.
2906 </para>
2907 <para>
2908 This rule is applied regardless of flags.  If you want a more exotic context, you can write
2909 it yourself, using the <link linkend="stand-alone-deriving">standalone deriving mechanism</link>.
2910 </para>
2911 </sect2>
2912
2913 <sect2 id="stand-alone-deriving">
2914 <title>Stand-alone deriving declarations</title>
2915
2916 <para>
2917 GHC now allows stand-alone <literal>deriving</literal> declarations, enabled by <literal>-XStandaloneDeriving</literal>:
2918 <programlisting>
2919   data Foo a = Bar a | Baz String
2920
2921   deriving instance Eq a => Eq (Foo a)
2922 </programlisting>
2923 The syntax is identical to that of an ordinary instance declaration apart from (a) the keyword
2924 <literal>deriving</literal>, and (b) the absence of the <literal>where</literal> part.
2925 Note the following points:
2926 <itemizedlist>
2927 <listitem><para>
2928 You must supply an explicit context (in the example the context is <literal>(Eq a)</literal>), 
2929 exactly as you would in an ordinary instance declaration.
2930 (In contrast, in a <literal>deriving</literal> clause 
2931 attached to a data type declaration, the context is inferred.) 
2932 </para></listitem>
2933
2934 <listitem><para>
2935 A <literal>deriving instance</literal> declaration
2936 must obey the same rules concerning form and termination as ordinary instance declarations,
2937 controlled by the same flags; see <xref linkend="instance-decls"/>.
2938 </para></listitem>
2939
2940 <listitem><para>
2941 Unlike a <literal>deriving</literal>
2942 declaration attached to a <literal>data</literal> declaration, the instance can be more specific
2943 than the data type (assuming you also use 
2944 <literal>-XFlexibleInstances</literal>, <xref linkend="instance-rules"/>).  Consider
2945 for example
2946 <programlisting>
2947   data Foo a = Bar a | Baz String
2948
2949   deriving instance Eq a => Eq (Foo [a])
2950   deriving instance Eq a => Eq (Foo (Maybe a))
2951 </programlisting>
2952 This will generate a derived instance for <literal>(Foo [a])</literal> and <literal>(Foo (Maybe a))</literal>,
2953 but other types such as <literal>(Foo (Int,Bool))</literal> will not be an instance of <literal>Eq</literal>.
2954 </para></listitem>
2955
2956 <listitem><para>
2957 Unlike a <literal>deriving</literal>
2958 declaration attached to a <literal>data</literal> declaration, 
2959 GHC does not restrict the form of the data type.  Instead, GHC simply generates the appropriate
2960 boilerplate code for the specified class, and typechecks it. If there is a type error, it is
2961 your problem. (GHC will show you the offending code if it has a type error.) 
2962 The merit of this is that you can derive instances for GADTs and other exotic
2963 data types, providing only that the boilerplate code does indeed typecheck.  For example:
2964 <programlisting>
2965   data T a where
2966      T1 :: T Int
2967      T2 :: T Bool
2968
2969   deriving instance Show (T a)
2970 </programlisting>
2971 In this example, you cannot say <literal>... deriving( Show )</literal> on the 
2972 data type declaration for <literal>T</literal>, 
2973 because <literal>T</literal> is a GADT, but you <emphasis>can</emphasis> generate
2974 the instance declaration using stand-alone deriving.
2975 </para>
2976 </listitem>
2977
2978 <listitem>
2979 <para>The stand-alone syntax is generalised for newtypes in exactly the same
2980 way that ordinary <literal>deriving</literal> clauses are generalised (<xref linkend="newtype-deriving"/>).
2981 For example:
2982 <programlisting>
2983   newtype Foo a = MkFoo (State Int a)
2984
2985   deriving instance MonadState Int Foo
2986 </programlisting>
2987 GHC always treats the <emphasis>last</emphasis> parameter of the instance
2988 (<literal>Foo</literal> in this example) as the type whose instance is being derived.
2989 </para></listitem>
2990 </itemizedlist></para>
2991
2992 </sect2>
2993
2994
2995 <sect2 id="deriving-typeable">
2996 <title>Deriving clause for extra classes (<literal>Typeable</literal>, <literal>Data</literal>, etc)</title>
2997
2998 <para>
2999 Haskell 98 allows the programmer to add "<literal>deriving( Eq, Ord )</literal>" to a data type 
3000 declaration, to generate a standard instance declaration for classes specified in the <literal>deriving</literal> clause.  
3001 In Haskell 98, the only classes that may appear in the <literal>deriving</literal> clause are the standard
3002 classes <literal>Eq</literal>, <literal>Ord</literal>, 
3003 <literal>Enum</literal>, <literal>Ix</literal>, <literal>Bounded</literal>, <literal>Read</literal>, and <literal>Show</literal>.
3004 </para>
3005 <para>
3006 GHC extends this list with several more classes that may be automatically derived:
3007 <itemizedlist>
3008 <listitem><para> With <option>-XDeriveDataTypeable</option>, you can derive instances of the classes
3009 <literal>Typeable</literal>, and <literal>Data</literal>, defined in the library
3010 modules <literal>Data.Typeable</literal> and <literal>Data.Generics</literal> respectively.
3011 </para>
3012 <para>An instance of <literal>Typeable</literal> can only be derived if the
3013 data type has seven or fewer type parameters, all of kind <literal>*</literal>.
3014 The reason for this is that the <literal>Typeable</literal> class is derived using the scheme
3015 described in
3016 <ulink url="http://research.microsoft.com/%7Esimonpj/papers/hmap/gmap2.ps">
3017 Scrap More Boilerplate: Reflection, Zips, and Generalised Casts
3018 </ulink>.
3019 (Section 7.4 of the paper describes the multiple <literal>Typeable</literal> classes that
3020 are used, and only <literal>Typeable1</literal> up to
3021 <literal>Typeable7</literal> are provided in the library.)
3022 In other cases, there is nothing to stop the programmer writing a <literal>TypableX</literal>
3023 class, whose kind suits that of the data type constructor, and
3024 then writing the data type instance by hand.
3025 </para>
3026 </listitem>
3027
3028 <listitem><para> With <option>-XDeriveFunctor</option>, you can derive instances of 
3029 the class <literal>Functor</literal>,
3030 defined in <literal>GHC.Base</literal>.
3031 </para></listitem>
3032
3033 <listitem><para> With <option>-XDeriveFoldable</option>, you can derive instances of 
3034 the class <literal>Foldable</literal>,
3035 defined in <literal>Data.Foldable</literal>.
3036 </para></listitem>
3037
3038 <listitem><para> With <option>-XDeriveTraversable</option>, you can derive instances of 
3039 the class <literal>Traversable</literal>,
3040 defined in <literal>Data.Traversable</literal>.
3041 </para></listitem>
3042 </itemizedlist>
3043 In each case the appropriate class must be in scope before it 
3044 can be mentioned in the <literal>deriving</literal> clause.
3045 </para>
3046 </sect2>
3047
3048 <sect2 id="newtype-deriving">
3049 <title>Generalised derived instances for newtypes</title>
3050
3051 <para>
3052 When you define an abstract type using <literal>newtype</literal>, you may want
3053 the new type to inherit some instances from its representation. In
3054 Haskell 98, you can inherit instances of <literal>Eq</literal>, <literal>Ord</literal>,
3055 <literal>Enum</literal> and <literal>Bounded</literal> by deriving them, but for any
3056 other classes you have to write an explicit instance declaration. For
3057 example, if you define
3058
3059 <programlisting>
3060   newtype Dollars = Dollars Int 
3061 </programlisting>
3062
3063 and you want to use arithmetic on <literal>Dollars</literal>, you have to
3064 explicitly define an instance of <literal>Num</literal>:
3065
3066 <programlisting>
3067   instance Num Dollars where
3068     Dollars a + Dollars b = Dollars (a+b)
3069     ...
3070 </programlisting>
3071 All the instance does is apply and remove the <literal>newtype</literal>
3072 constructor. It is particularly galling that, since the constructor
3073 doesn't appear at run-time, this instance declaration defines a
3074 dictionary which is <emphasis>wholly equivalent</emphasis> to the <literal>Int</literal>
3075 dictionary, only slower!
3076 </para>
3077
3078
3079 <sect3> <title> Generalising the deriving clause </title>
3080 <para>
3081 GHC now permits such instances to be derived instead, 
3082 using the flag <option>-XGeneralizedNewtypeDeriving</option>,
3083 so one can write 
3084 <programlisting>
3085   newtype Dollars = Dollars Int deriving (Eq,Show,Num)
3086 </programlisting>
3087
3088 and the implementation uses the <emphasis>same</emphasis> <literal>Num</literal> dictionary
3089 for <literal>Dollars</literal> as for <literal>Int</literal>. Notionally, the compiler
3090 derives an instance declaration of the form
3091
3092 <programlisting>
3093   instance Num Int => Num Dollars
3094 </programlisting>
3095
3096 which just adds or removes the <literal>newtype</literal> constructor according to the type.
3097 </para>
3098 <para>
3099
3100 We can also derive instances of constructor classes in a similar
3101 way. For example, suppose we have implemented state and failure monad
3102 transformers, such that
3103
3104 <programlisting>
3105   instance Monad m => Monad (State s m) 
3106   instance Monad m => Monad (Failure m)
3107 </programlisting>
3108 In Haskell 98, we can define a parsing monad by 
3109 <programlisting>
3110   type Parser tok m a = State [tok] (Failure m) a
3111 </programlisting>
3112
3113 which is automatically a monad thanks to the instance declarations
3114 above. With the extension, we can make the parser type abstract,
3115 without needing to write an instance of class <literal>Monad</literal>, via
3116
3117 <programlisting>
3118   newtype Parser tok m a = Parser (State [tok] (Failure m) a)
3119                          deriving Monad
3120 </programlisting>
3121 In this case the derived instance declaration is of the form 
3122 <programlisting>
3123   instance Monad (State [tok] (Failure m)) => Monad (Parser tok m) 
3124 </programlisting>
3125
3126 Notice that, since <literal>Monad</literal> is a constructor class, the
3127 instance is a <emphasis>partial application</emphasis> of the new type, not the
3128 entire left hand side. We can imagine that the type declaration is
3129 "eta-converted" to generate the context of the instance
3130 declaration.
3131 </para>
3132 <para>
3133
3134 We can even derive instances of multi-parameter classes, provided the
3135 newtype is the last class parameter. In this case, a ``partial
3136 application'' of the class appears in the <literal>deriving</literal>
3137 clause. For example, given the class
3138
3139 <programlisting>
3140   class StateMonad s m | m -> s where ... 
3141   instance Monad m => StateMonad s (State s m) where ... 
3142 </programlisting>
3143 then we can derive an instance of <literal>StateMonad</literal> for <literal>Parser</literal>s by 
3144 <programlisting>
3145   newtype Parser tok m a = Parser (State [tok] (Failure m) a)
3146                          deriving (Monad, StateMonad [tok])
3147 </programlisting>
3148
3149 The derived instance is obtained by completing the application of the
3150 class to the new type:
3151
3152 <programlisting>
3153   instance StateMonad [tok] (State [tok] (Failure m)) =>
3154            StateMonad [tok] (Parser tok m)
3155 </programlisting>
3156 </para>
3157 <para>
3158
3159 As a result of this extension, all derived instances in newtype
3160  declarations are treated uniformly (and implemented just by reusing
3161 the dictionary for the representation type), <emphasis>except</emphasis>
3162 <literal>Show</literal> and <literal>Read</literal>, which really behave differently for
3163 the newtype and its representation.
3164 </para>
3165 </sect3>
3166
3167 <sect3> <title> A more precise specification </title>
3168 <para>
3169 Derived instance declarations are constructed as follows. Consider the
3170 declaration (after expansion of any type synonyms)
3171
3172 <programlisting>
3173   newtype T v1...vn = T' (t vk+1...vn) deriving (c1...cm) 
3174 </programlisting>
3175
3176 where 
3177  <itemizedlist>
3178 <listitem><para>
3179   The <literal>ci</literal> are partial applications of
3180   classes of the form <literal>C t1'...tj'</literal>, where the arity of <literal>C</literal>
3181   is exactly <literal>j+1</literal>.  That is, <literal>C</literal> lacks exactly one type argument.
3182 </para></listitem>
3183 <listitem><para>
3184   The <literal>k</literal> is chosen so that <literal>ci (T v1...vk)</literal> is well-kinded.
3185 </para></listitem>
3186 <listitem><para>
3187   The type <literal>t</literal> is an arbitrary type.
3188 </para></listitem>
3189 <listitem><para>
3190   The type variables <literal>vk+1...vn</literal> do not occur in <literal>t</literal>, 
3191   nor in the <literal>ci</literal>, and
3192 </para></listitem>
3193 <listitem><para>
3194   None of the <literal>ci</literal> is <literal>Read</literal>, <literal>Show</literal>, 
3195                 <literal>Typeable</literal>, or <literal>Data</literal>.  These classes
3196                 should not "look through" the type or its constructor.  You can still
3197                 derive these classes for a newtype, but it happens in the usual way, not 
3198                 via this new mechanism.  
3199 </para></listitem>
3200 </itemizedlist>
3201 Then, for each <literal>ci</literal>, the derived instance
3202 declaration is:
3203 <programlisting>
3204   instance ci t => ci (T v1...vk)
3205 </programlisting>
3206 As an example which does <emphasis>not</emphasis> work, consider 
3207 <programlisting>
3208   newtype NonMonad m s = NonMonad (State s m s) deriving Monad 
3209 </programlisting>
3210 Here we cannot derive the instance 
3211 <programlisting>
3212   instance Monad (State s m) => Monad (NonMonad m) 
3213 </programlisting>
3214
3215 because the type variable <literal>s</literal> occurs in <literal>State s m</literal>,
3216 and so cannot be "eta-converted" away. It is a good thing that this
3217 <literal>deriving</literal> clause is rejected, because <literal>NonMonad m</literal> is
3218 not, in fact, a monad --- for the same reason. Try defining
3219 <literal>>>=</literal> with the correct type: you won't be able to.
3220 </para>
3221 <para>
3222
3223 Notice also that the <emphasis>order</emphasis> of class parameters becomes
3224 important, since we can only derive instances for the last one. If the
3225 <literal>StateMonad</literal> class above were instead defined as
3226
3227 <programlisting>
3228   class StateMonad m s | m -> s where ... 
3229 </programlisting>
3230
3231 then we would not have been able to derive an instance for the
3232 <literal>Parser</literal> type above. We hypothesise that multi-parameter
3233 classes usually have one "main" parameter for which deriving new
3234 instances is most interesting.
3235 </para>
3236 <para>Lastly, all of this applies only for classes other than
3237 <literal>Read</literal>, <literal>Show</literal>, <literal>Typeable</literal>, 
3238 and <literal>Data</literal>, for which the built-in derivation applies (section
3239 4.3.3. of the Haskell Report).
3240 (For the standard classes <literal>Eq</literal>, <literal>Ord</literal>,
3241 <literal>Ix</literal>, and <literal>Bounded</literal> it is immaterial whether
3242 the standard method is used or the one described here.)
3243 </para>
3244 </sect3>
3245 </sect2>
3246 </sect1>
3247
3248
3249 <!-- TYPE SYSTEM EXTENSIONS -->
3250 <sect1 id="type-class-extensions">
3251 <title>Class and instances declarations</title>
3252
3253 <sect2 id="multi-param-type-classes">
3254 <title>Class declarations</title>
3255
3256 <para>
3257 This section, and the next one, documents GHC's type-class extensions.
3258 There's lots of background in the paper <ulink
3259 url="http://research.microsoft.com/~simonpj/Papers/type-class-design-space/">Type
3260 classes: exploring the design space</ulink> (Simon Peyton Jones, Mark
3261 Jones, Erik Meijer).
3262 </para>
3263 <para>
3264 All the extensions are enabled by the <option>-fglasgow-exts</option> flag.
3265 </para>
3266
3267 <sect3>
3268 <title>Multi-parameter type classes</title>
3269 <para>
3270 Multi-parameter type classes are permitted, with flag <option>-XMultiParamTypeClasses</option>. 
3271 For example:
3272
3273
3274 <programlisting>
3275   class Collection c a where
3276     union :: c a -> c a -> c a
3277     ...etc.
3278 </programlisting>
3279
3280 </para>
3281 </sect3>
3282
3283 <sect3 id="superclass-rules">
3284 <title>The superclasses of a class declaration</title>
3285
3286 <para>
3287 In Haskell 98 the context of a class declaration (which introduces superclasses)
3288 must be simple; that is, each predicate must consist of a class applied to 
3289 type variables.  The flag <option>-XFlexibleContexts</option> 
3290 (<xref linkend="flexible-contexts"/>)
3291 lifts this restriction,
3292 so that the only restriction on the context in a class declaration is 
3293 that the class hierarchy must be acyclic.  So these class declarations are OK:
3294
3295
3296 <programlisting>
3297   class Functor (m k) => FiniteMap m k where
3298     ...
3299
3300   class (Monad m, Monad (t m)) => Transform t m where
3301     lift :: m a -> (t m) a
3302 </programlisting>
3303
3304
3305 </para>
3306 <para>
3307 As in Haskell 98, The class hierarchy must be acyclic.  However, the definition
3308 of "acyclic" involves only the superclass relationships.  For example,
3309 this is OK:
3310
3311
3312 <programlisting>
3313   class C a where {
3314     op :: D b => a -> b -> b
3315   }
3316
3317   class C a => D a where { ... }
3318 </programlisting>
3319
3320
3321 Here, <literal>C</literal> is a superclass of <literal>D</literal>, but it's OK for a
3322 class operation <literal>op</literal> of <literal>C</literal> to mention <literal>D</literal>.  (It
3323 would not be OK for <literal>D</literal> to be a superclass of <literal>C</literal>.)
3324 </para>
3325 </sect3>
3326
3327
3328
3329
3330 <sect3 id="class-method-types">
3331 <title>Class method types</title>
3332
3333 <para>
3334 Haskell 98 prohibits class method types to mention constraints on the
3335 class type variable, thus:
3336 <programlisting>
3337   class Seq s a where
3338     fromList :: [a] -> s a
3339     elem     :: Eq a => a -> s a -> Bool
3340 </programlisting>
3341 The type of <literal>elem</literal> is illegal in Haskell 98, because it
3342 contains the constraint <literal>Eq a</literal>, constrains only the 
3343 class type variable (in this case <literal>a</literal>).
3344 GHC lifts this restriction (flag <option>-XConstrainedClassMethods</option>).
3345 </para>
3346
3347
3348 </sect3>
3349 </sect2>
3350
3351 <sect2 id="functional-dependencies">
3352 <title>Functional dependencies
3353 </title>
3354
3355 <para> Functional dependencies are implemented as described by Mark Jones
3356 in &ldquo;<ulink url="http://citeseer.ist.psu.edu/jones00type.html">Type Classes with Functional Dependencies</ulink>&rdquo;, Mark P. Jones, 
3357 In Proceedings of the 9th European Symposium on Programming, 
3358 ESOP 2000, Berlin, Germany, March 2000, Springer-Verlag LNCS 1782,
3359 .
3360 </para>
3361 <para>
3362 Functional dependencies are introduced by a vertical bar in the syntax of a 
3363 class declaration;  e.g. 
3364 <programlisting>
3365   class (Monad m) => MonadState s m | m -> s where ...
3366
3367   class Foo a b c | a b -> c where ...
3368 </programlisting>
3369 There should be more documentation, but there isn't (yet).  Yell if you need it.
3370 </para>
3371
3372 <sect3><title>Rules for functional dependencies </title>
3373 <para>
3374 In a class declaration, all of the class type variables must be reachable (in the sense 
3375 mentioned in <xref linkend="flexible-contexts"/>)
3376 from the free variables of each method type.
3377 For example:
3378
3379 <programlisting>
3380   class Coll s a where
3381     empty  :: s
3382     insert :: s -> a -> s
3383 </programlisting>
3384
3385 is not OK, because the type of <literal>empty</literal> doesn't mention
3386 <literal>a</literal>.  Functional dependencies can make the type variable
3387 reachable:
3388 <programlisting>
3389   class Coll s a | s -> a where
3390     empty  :: s
3391     insert :: s -> a -> s
3392 </programlisting>
3393
3394 Alternatively <literal>Coll</literal> might be rewritten
3395
3396 <programlisting>
3397   class Coll s a where
3398     empty  :: s a
3399     insert :: s a -> a -> s a
3400 </programlisting>
3401
3402
3403 which makes the connection between the type of a collection of
3404 <literal>a</literal>'s (namely <literal>(s a)</literal>) and the element type <literal>a</literal>.
3405 Occasionally this really doesn't work, in which case you can split the
3406 class like this:
3407
3408
3409 <programlisting>
3410   class CollE s where
3411     empty  :: s
3412
3413   class CollE s => Coll s a where
3414     insert :: s -> a -> s
3415 </programlisting>
3416 </para>
3417 </sect3>
3418
3419
3420 <sect3>
3421 <title>Background on functional dependencies</title>
3422
3423 <para>The following description of the motivation and use of functional dependencies is taken
3424 from the Hugs user manual, reproduced here (with minor changes) by kind
3425 permission of Mark Jones.
3426 </para>
3427 <para> 
3428 Consider the following class, intended as part of a
3429 library for collection types:
3430 <programlisting>
3431    class Collects e ce where
3432        empty  :: ce
3433        insert :: e -> ce -> ce
3434        member :: e -> ce -> Bool
3435 </programlisting>
3436 The type variable e used here represents the element type, while ce is the type
3437 of the container itself. Within this framework, we might want to define
3438 instances of this class for lists or characteristic functions (both of which
3439 can be used to represent collections of any equality type), bit sets (which can
3440 be used to represent collections of characters), or hash tables (which can be
3441 used to represent any collection whose elements have a hash function). Omitting
3442 standard implementation details, this would lead to the following declarations: 
3443 <programlisting>
3444    instance Eq e => Collects e [e] where ...
3445    instance Eq e => Collects e (e -> Bool) where ...
3446    instance Collects Char BitSet where ...
3447    instance (Hashable e, Collects a ce)
3448               => Collects e (Array Int ce) where ...
3449 </programlisting>
3450 All this looks quite promising; we have a class and a range of interesting
3451 implementations. Unfortunately, there are some serious problems with the class
3452 declaration. First, the empty function has an ambiguous type: 
3453 <programlisting>
3454    empty :: Collects e ce => ce
3455 </programlisting>
3456 By "ambiguous" we mean that there is a type variable e that appears on the left
3457 of the <literal>=&gt;</literal> symbol, but not on the right. The problem with
3458 this is that, according to the theoretical foundations of Haskell overloading,
3459 we cannot guarantee a well-defined semantics for any term with an ambiguous
3460 type.
3461 </para>
3462 <para>
3463 We can sidestep this specific problem by removing the empty member from the
3464 class declaration. However, although the remaining members, insert and member,
3465 do not have ambiguous types, we still run into problems when we try to use
3466 them. For example, consider the following two functions: 
3467 <programlisting>
3468    f x y = insert x . insert y
3469    g     = f True 'a'
3470 </programlisting>
3471 for which GHC infers the following types: 
3472 <programlisting>
3473    f :: (Collects a c, Collects b c) => a -> b -> c -> c
3474    g :: (Collects Bool c, Collects Char c) => c -> c
3475 </programlisting>
3476 Notice that the type for f allows the two parameters x and y to be assigned
3477 different types, even though it attempts to insert each of the two values, one
3478 after the other, into the same collection. If we're trying to model collections
3479 that contain only one type of value, then this is clearly an inaccurate
3480 type. Worse still, the definition for g is accepted, without causing a type
3481 error. As a result, the error in this code will not be flagged at the point
3482 where it appears. Instead, it will show up only when we try to use g, which
3483 might even be in a different module.
3484 </para>
3485
3486 <sect4><title>An attempt to use constructor classes</title>
3487
3488 <para>
3489 Faced with the problems described above, some Haskell programmers might be
3490 tempted to use something like the following version of the class declaration: 
3491 <programlisting>
3492    class Collects e c where
3493       empty  :: c e
3494       insert :: e -> c e -> c e
3495       member :: e -> c e -> Bool
3496 </programlisting>
3497 The key difference here is that we abstract over the type constructor c that is
3498 used to form the collection type c e, and not over that collection type itself,
3499 represented by ce in the original class declaration. This avoids the immediate
3500 problems that we mentioned above: empty has type <literal>Collects e c => c
3501 e</literal>, which is not ambiguous. 
3502 </para>
3503 <para>
3504 The function f from the previous section has a more accurate type: 
3505 <programlisting>
3506    f :: (Collects e c) => e -> e -> c e -> c e
3507 </programlisting>
3508 The function g from the previous section is now rejected with a type error as
3509 we would hope because the type of f does not allow the two arguments to have
3510 different types. 
3511 This, then, is an example of a multiple parameter class that does actually work
3512 quite well in practice, without ambiguity problems.
3513 There is, however, a catch. This version of the Collects class is nowhere near
3514 as general as the original class seemed to be: only one of the four instances
3515 for <literal>Collects</literal>
3516 given above can be used with this version of Collects because only one of
3517 them---the instance for lists---has a collection type that can be written in
3518 the form c e, for some type constructor c, and element type e.
3519 </para>
3520 </sect4>
3521
3522 <sect4><title>Adding functional dependencies</title>
3523
3524 <para>
3525 To get a more useful version of the Collects class, Hugs provides a mechanism
3526 that allows programmers to specify dependencies between the parameters of a
3527 multiple parameter class (For readers with an interest in theoretical
3528 foundations and previous work: The use of dependency information can be seen
3529 both as a generalization of the proposal for `parametric type classes' that was
3530 put forward by Chen, Hudak, and Odersky, or as a special case of Mark Jones's
3531 later framework for "improvement" of qualified types. The
3532 underlying ideas are also discussed in a more theoretical and abstract setting
3533 in a manuscript [implparam], where they are identified as one point in a
3534 general design space for systems of implicit parameterization.).
3535
3536 To start with an abstract example, consider a declaration such as: 
3537 <programlisting>
3538    class C a b where ...
3539 </programlisting>
3540 which tells us simply that C can be thought of as a binary relation on types
3541 (or type constructors, depending on the kinds of a and b). Extra clauses can be
3542 included in the definition of classes to add information about dependencies
3543 between parameters, as in the following examples: 
3544 <programlisting>
3545    class D a b | a -> b where ...
3546    class E a b | a -> b, b -> a where ...
3547 </programlisting>
3548 The notation <literal>a -&gt; b</literal> used here between the | and where
3549 symbols --- not to be
3550 confused with a function type --- indicates that the a parameter uniquely